For each algorithm assigned, provide pseudocode, including formal description of inputs and outputs, and work out the algorithm on an example of your own devising.
Topics | |||
---|---|---|---|
Fibonacci Heaps | Li&Shorter | Present as abstract data type (data+algorithms), use in graph algorithms, unique properties and decrease-key algorithm with example. Explain “amortized” runtime complexity and show this is O(1) | CLRS Ch. 19; focus on 19.1 and 19.3 |
Disjoint Sets | Broadnax&Johnson | Present as abstract data type (data+algorithms), runtime complexity, and use in graph algorithms | DPV Section 3.4/CLRS Ch. 21 |
Huffman Encoding | Harvey&Kayitare | Present algorithm with example and runtime complexity | DPV Sec. 5.2 and/or Real-World Algorithms Sec 3.3 |
Network Flow | Not Assigned | | CLRS Chapter 25 |