Week of Sept. 23

We finished up dynamic trees today, with the exception that there's a little more to say about the proof that the number of splices done during m operations is O(m log n).  Thanks, James, for your presentation today.

On Thursday, we will start looking at Henzinger and King's decremental connectivity algorithm, which is in Chapter 5.  Read Chapter 5, up through at least page 66.  I've put a link to the original HK article on the E-reserves page.

Week of Sept. 16

A careful look at dynamic trees, which are in the book in Chapter 3.

Week of Sept. 9

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.

Thursday, Sept. 4

Today's class discussed:

  • The runtime analysis of Dijkstra's algorithm based on three implementations: one using a simple list of nodes that are marked with the info required for the algorithm, one using a heap, and one using a Fibonacci heap.
  • Amortization
  • A short introduction to Fibonacci heaps.

You should read about these things before the next class: amortization (pp. 5 and 6) and Fibonacci heaps (see your CS 31 text).  Tuesday's class will move quickly through Fibonacci heaps, so come prepared to discuss them.  We are also likely to begin discussing splay trees (pp. 6-11).  A journal article on splay trees (Sleator and Tarjan, 1985) is available on the E-reserves page.  It contains the full proof that the potential is maintained at each rotation.

 

Tuesday, Sept. 2

Today's class discussed:

  • The problem of determining connectivity in an undirected graph, depth-first search, and basic approaches to the dynamic version of the problem.
  • The problem of finding a shortest path in a directed graph.  We reviewed Dijkstra's algorithm and why it works.

Coming up:

  • Analyzing the running time of Dijkstra's algorithm
  • Amortization
  • Fibonacci heaps
  • Later next week: minimum spanning forests. 

Things to read:

  • In my manuscript: chapter 1 through section 1.4.
  • In your algorithms textbook: section on Fibonacci heaps.  It isn't essential that you read this before Thursday, but I'd like you to read it soon.