Time: Mondays, 13-16

Place: Dan David 110

It is possible to submit homework 4 by Thursday 10/6.

Homework 5 is dues on Friday June 26.

Have a nice summer !

Tentative topics

- Amortized analysis, red-black trees, 2-4 trees.
- weight balance trees, range searching
- The algorithm of Garsia and Wachs for finding optimal alphabetic trees.
- Biased search trees.
- Splay trees.
- Data compression via Splay trees.
- Dynamic trees, and their applications.
- Finger search trees and their applications
- Maintaining order in a list.
- Binomial heaps, binomial heaps with lazy delete, Fibonacci heaps, Fat heaps.
- Use of heaps in algorithms for finding a minimum spanning tree, and in implementations of Dijkstra's single source shortest path algorithm.
- Persistent data structures.

- Binomial heaps & Fibonacci Heaps
- Finding a minimum spanning tree in O(m log (&beta(m,n))) time
- Fat Heaps
- Red black trees
- 2-4 trees
- Finger search trees
- Sorting Jordan sequences
- Dynamic graph connectivity
- Euler tour trees
- Splay trees
- Dinic's algorithm for maximum flow
- Dynamic trees
- Range searching with priorities
- Kinetic heaps
- Maintaining order
- Persistent data structures 1
- Persistent data structures 2
- Persistent queues

- Homework 0 (in postscript)
- Homework 1 (in postscript)
- Homework 2 (in postscript)
- Homework 3 (in postscript)
- Homework 4 (in postscript)
- Homework 5 (in postscript)

- R. E. Tarjan. Amortized computational complexity. SIAM J. Algebraic Discrete Methods, 6(2):306-- 318, 1985.
- Chapter 18 (amortized analysis) of Algorithms by Cormen, Leiserson, and Rivest (CLR)
- Self-adjusting binary search trees, Sleator and Tarjan, JACM, 1985 (in pdf).