School of Mathematics School of Mathematics
Module MA3467 - Algorithms 2009-10 (JS & SS Mathematics, JS & SS Two-subject Moderatorship )
Lecturer: Dr. Colm Ó Dúnlaing


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.


(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 TEX by TTH, version 2.70.
On 8 May 2009, 09:09.