Monday September 5th. Holiday: No Lecture.
Wednesday September 7tt. Recurrences: understanding the master theorem; merge-sort.
Monday September 12th. Recurrences: randomised selection.
Wednesday September 14th. Recurrences: using recurrence trees; deterministic selection.
Monday September 19th. Recurrences: domain transformation; quicksort; lower bounds on sorting.
Wednesday September 21st. Heaps: heapsort.
Monday September 26th. Heaps: minimum spanning trees.
Wednesday September 28th. Binary Search Trees.
Monday October 3rd. Binary Search Trees: randomly built BSTs. Linear time sorting.
Wednesday October 5th. Red-Black Trees: insertions.
Monday October 10th. Holiday: No Lecture.
Wednesday October 12th. Red-Black Trees: deletions and joins.
Monday October 17th. Red-Black Trees: line segment intersection.
Wednesday October 19th. Hashing: chaining, open addressing.
Monday October 24th. No Lecture.
Wednesday October 26th. Amortized Analysis.
Monday October 31st. Splay Trees.
Wednesday November 2nd. Binomial Trees.
Monday November 7th. Fibonacci Heaps: Dijkstra's algorithm.
Wednesday November 9th. Skip Lists; Matrix Muliplication.
Monday November 14th. Weight Balanced Trees; Probabilistic Checking.
Wednesday November 16th. Treaps.
Monday November 21st. Data Structures for Disjoint Sets: Kruskals algorithm.
Wednesday November 23rd. Leftist Heaps.
Monday November 28th. Minimum Cut: randomised algorithm.
Wednesday November 30th. Fast Fourier Transforms.
Thursday December 1st. The Last Lecture.
Thursday December 8th. Final Exam.