Experimentální srovnání decrease-key hald
| Thesis title in Czech: | Experimentální srovnání decrease-key hald |
|---|---|
| Thesis title in English: | Experimantal comparisons of decrease-key heaps |
| Key words: | haldy (prioritní fronty) |
| English key words: | heaps (priority queues) |
| Academic year of topic announcement: | 2022/2023 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | Mgr. Vladan Majerech, Dr. |
| Author: |
| Guidelines |
| Implementation of different variants of decrease-key heaps will be the main part of the thesis.
There should be implemented Fibonacci heaps, Rank-pairing heaps, Padovan heaps and Strict Fibonacci heaps. Implementation of the Fredman-Tarjan algorithm computing minimum spannig tree (on big random graphs) is a recommended experiment. Comparison criteria should include not only measured times, but also counts of elementary operations made. |
| References |
| Michael~L. Fredman and Robert~Endre Tarjan: "Fibonacci heaps and their uses in improved network optimization algorithms.", J. ACM, 34(3):596--615, July 1987.
Bernhard Haeupler, Siddhartha Sen, and Robert~E. Tarjan: "Rank-pairing heaps.", SIAM J. Comput., 40:1463--1485, 2011. Vladan Majerech: "Padovan heaps", https://arxiv.org/abs/1902.10812, 2019 Vladan Majerech: "Fast DecreaseKey Heaps with worst-case variants", https://arxiv.org/abs/2010.02507 Stølting Brodal, Gerth and Lagogiannis, George and Tarjan, Robert? "Strict Fibonacci heaps", Proceedings of the Annual ACM Symposium on Theory of Computing, May 2012 Haim Kaplan and Robert E. Tarjan and Uri Zwick: "Fibonacci Heaps Revisited", https://arxiv.org/abs/1407.5750, 2014 |
| Preliminary scope of work |
| Existuje několik implementací Decrease-key hald, neboli struktur podporujících Insert, FindMin, DeleteMin, DecreaseKey operace v optimálních amortizovaných časech (O(1),O(1),O(log n),O(1)).
Nejznámější jsou Fibonacciho haldy. Standardní implementace Fibonacciho hald nezachycuje výsledky některých porovnávání. Padovan haldy a Strict Fibonacci haldy (a jejich varianty) jsou v tomto ohledu opatrnější. Cílem je změřit, jak se změna strategií projeví v experimentech. Strict Fibonacci heaps implementují operace tak, že zmíněné časy platí v nejhorším případě jednotlivých operací. Kolik za to zaplatíme v multiplikativních konstantách? |
| Preliminary scope of work in English |
| There exists several implementations of Decrease-key heaps, ie data structures supporting Insert, FindMin, DeleteMin, DecreaseKey operations in amortized optimal times (O(1), O(1), O(log n),O(1)).
The most known are Fibonacci heaps. Standard implementation of Fibonacci heaps does not remember results of some comparisons. Padovan heaps and Strict Fibonacci heaps (and their variants) are more cautious in this respect. The goal of the thesis is to measure, how much the strategy changes show in experiments. Strict Fibonacci heaps implement the operations such that the mentioned times are worst case of individual operations. What is it's cost in multiplication factors? |