**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

File translated from T

On 8 May 2009, 09:09.