Requirements/prerequisites:

Duration: Michaelmas term, 11 weeks

Number of lectures per week: 3 lectures including tutorials per week

Assessment: 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.

Description:

(Preliminary draft.)

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