Lecture 17 Union Find (1)

Today, we talked about union find, data structure that supports find and union operation. We gave an implementation that has cost O(log n) for both operations. We also explain the idea of how to modify the find  function to improve the running time to log* n.

If you are interested in the reference of total number of atoms in the universe, here is a wiki page:
http://en.wikipedia.org/wiki/Observable_universe

change of Siddharth's office hour

The office hour of our TA, Siddharth,  is  now 10:30-12:30 at Thu.

Lecture 16 Fibonacci heap (3)

Today, we finished the Fibonacci heap and proved that it has O(1) amortized cost for insertion, merge, find_min, decrease_key. The only expensive work is delete_min which takes O(log n).

As an application, we show how to use Fibonacci heap in Prim's algorithm for Minimum Spanning Tree.

Hint on homework 2

Some student asked me hint for problem 2 of homework 2.  The suggestion is that prove your claim with simple examples. For example, can you prove you claim on trees of size 3?

Lecture 15. Fibonacci Heap (2)

Today we talked about how to implement a decrease_key. This implementation will give us tree that is no longer binomial tree. But it will still have the property that suppose the children of a node is sorted according to its degree, then the i-th  has degree at least i-2. (An alternative definition of binomial tree is that its ith child has degree exact i-1).  We call any tree of above property Fibonacci Tree.

Lecture 14 Binomial Heap and Fibonacci Heap

Today, we talked about Binomial Heap and why it takes an amortized running time of O(log n) for the deletion and O(1) for all the other operations. We also (try to) motivate Fibonacci Heap which also support decrease_key in O(1) time.

If you are confused by the Dijkstra's algorithm I described in the end,  take a look at the wiki description.

lecture 13 Binomial Heaps (2)

Today, we talked about how to implement the merge operation of Binomial heap in O(log n) time. This will give us insertion, delete_min, merge all in O(log n).

Surprisingly, if we are a little bit lazier in the implementation, we can make all the operations O(1) except for the delete_min operation.