Lecturer	James Worrell
Degrees	Schedule S1(3rd years) — Computer Science Schedule B1 — Computer Science Schedule B1(M&CS) — Mathematics and Computer Science ECS Part II — MEng Engineering and Computing Science
Term	Hilary Term 2009  (16 lectures)

Overview

This course continues where the core course on Design and Analysis of Algorithms left off. The course introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems such as primality testing, optimisation, hashing and string matching. Students are also introduced to randomised algorithms and to techniques of amortised complexity analysis. As in the core course, the style of the presentation is rigorous but high-level and informal.

Learning outcomes

At the end of the course students will:

• Understand how to implement dictionaries and priority queues using sophisticated data structures such as splay trees and mergeable heaps 
• Know how to carry out amortised complexity analysis of algorithms
• Understand how to efficiently calculate the max flow through a network and the discrete Fourier transform of a polynomial
• Understand how to generate random prime numbers, and how these are used in hashing and string matching

Synopsis

• Amortised analysis (1 Lecture)
• Mergeable heaps (2 Lectures) - Binomial and Fibonacci heaps
• Disjoint sets (1 Lecture) - Disjoint-set forests, Complexity
• Analysis using Ackermann's function
• Splay trees (2 Lectures)
• Hashing (2 Lectures) - Universal hashing, Perfect hashing
• Fast Fourier transform (1 Lecture)
• String matching (2 Lectures) - Rabin-Karp algorithm,
• Knuth-Morris-Pratt algorithm
• Primality testing and RSA cryptosystem (3 Lectures) - Miller-Rabin algorithm
• Network flow and matching (2 Lectures) - Edmunds-Karp algorithm

Reading list

The main text used in the course is:

• Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001 (second edition).

The following texts provide useful background. In particular, Kozen's book covers much of the course in a succinct fashion.

• Dexter Kozen, The Design and Analysis of Algorithms, Springer 1992.
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, CUP, 1995.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.