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 2010  (16 lectures)

Overview

This course builds on the first-year Design and Analysis of Algorithms course. It introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems such as primality testing, linear optimisation, 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 not formal.

Learning outcomes

On successful completion of the course students will:

• Be able to determine the time complexity of algorithms using amortised analysis
• Be able to design and analyse simple randomised algorithms
• Understand the implementation, complexity analysis and some applications of classical algorithms for string matching, primality testing, and the Discrete Fourier transform
• Be able to formulate and solve max-flow problems
• Be able to formulate and solve linear programs
• Understand the implementation, complexity analysis and some applications of splay trees, binomial heaps, Fibonacci heaps and disjoint sets

Synopsis

• Amortised analysis (1 lecture)
• Binomial and Fibonacci heaps (1.5  lectures)
• Disjoint sets / Union-find (2  lectures)
• Splay trees (1.5 lectures)
• Fast Fourier transform (1.5 lectures)
• String matching: Rabin-Karp and Knuth-Morris-Pratt algorithms (2 lectures)
• Primality testing: Miller-Rabin algorithm (2 lectures) 
• Network flow: Edmonds-Karp algorithm (2 lectures)
• Linear programming (2.5 lectures)

Syllabus

Amortised analysis. 

Splay trees. 

Mergable heaps.  

Disjoint sets / Union-find: complexity analysis and applications

Primality testing: the Miller-Rabin algorithm and its probabilistic correctness

String matching: the Rabin-Karp and Knuth-Morris-Pratt  algorithms

Max-flow: the Edmonds-Karp algorithm; some applications in optimisation and graph theory

Linear programming: formulating optimisation problems as linear programs; the simplex method; duality.

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 text is a useful alternative.

• Dexter Kozen, The Design and Analysis of Algorithms, Springer 1992

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.