Duration: Michaelmas term, 11 weeks
Number of lectures per week: 3 lectures including tutorials per week
Coursework and final exam. The coursework
will be agreed by consultation before the course
begins or in the first week.
End-of-year Examination: This module will be examined jointly with MA3468 in a 3-hour examination in Trinity term, except that those taking just one of the two modules will have a 2 hour examination.
We begin with binary search trees, with average-case analysis, including recent work on node deletion. Heaps and heapsort. Mergesort. W(nlogn) lower bound. Red-black search trees for lookup, add, remove, join, and split. Splay trees. Hash tables.
Union-find and union-split-find.
Knuth-Morris-Pratt pattern matching. Extension to Tries, boolean combinations of matches. Algebra of strings and the Boyer-Moore algorithm.
Graph connectivity, acyclicity, biconnectivity, strong connectivity, the Floyd-Warshall algorithm and irreducible matrices.
The Jordan Curve Theorem - a digression.
Planar graphs. The Hopcroft-Tarjan planarity algorithm. A constructive version of Kuratowski's Theorem. Triangulating planar graphs. Barycentric embeddings.
May 8, 2009