We discussed the analysis of Fibonacci heaps (see an algorithms text for more details) and talked about the analysis of splay trees. The important ideas on splay trees are in my text in section 1.5.

We began consideration of the minimum-spanning forest problem, including Prim's algorithm and the Blue and Red rules.

You should read Chapter 2, skimming through the sections with tables, although you can get the idea of the kind of improvements that have been achieved in recent years.

You should look carefully at section 2.8 on Red and Blue rules. Make sure that you understand why the red rule works, and take note of the fact that the correctness of Prim's algorithm follows from the blue rule. Look also at theorem 2.1. This cool little theorem is important to the correctness of many dynamic algorithms.

Read section 2.9 carefully. It describes a decremental connectivity algorithm that is different in flavor from other algorithms that you are likely to have studied. We'll talk briefly about this algorithm on Tuesday and will then proceed forward to the material in chapter 3. You must read chapter 3 by Thursday, Sept. 18.