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.
|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|