Requirements/prerequisites:

Duration: 11 weeks

Number of lectures per week: 3 including tutorials

Assessment: 10% coursework and 90% exam.

ECTS credits: 5

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. However there will be separate results for MA3467 and MA3468.

Description:

• Sorting: merge, quick, radix, heaps and heapsort
• Lookup as a recurrent theme; sequential, lists.
• Searching: binary search trees; average cost of insertion;
• Michaela Heyer's scheme for randomising deletions (if time permits)
• Red-black trees: find, insert, delete, join, split
• Splay trees: ditto
• Union-find schemes.
• Union-split-find: van Emde Boas et al.
• Davenport-Schinzel sequences (if time permits)
• Knuth-Morris-Pratt string matching
• Boyer-Moore string matching
• Hashing (mostly concerned with rehashing strategies). Chaining, uniform (and double), linear rehashing.
• Rabin-Karp (string search through fingerprinting?) (if time permits)
• Bloom filters
• Directed graphs: acyclicity and topological sort; dfs and ditto; strong components.
• Floyd-Warshall all-pairs shortest path algorithm. Dijkstra. (if time permits)
• Network flows: Edmonds and Karp. (if time permits)

Aug 8, 2011