Lecture 9: 02/03/2012

A little bit on Fibonacci heaps today at the beginning. We covered Cascading cuts in a Fibonacci tree.

The real meat of the lecture was supposed to be on Kruskal’s Algorithm and the Union-Find algorithm.

We described the Ackermann function, as well as the inverse Ackermann function, in motivation of deriving the run-time of Union-Find, which runs in O(n*a(n)). We didn’t get very far into describing Kruskal’s algorithm so we’ll the algorithm, as well as the analysis of Union-Find next time.

Please make sure to read over Kruskal’s Algorithm, as well as the Union-Find chapters in Kozen before the next lecture.