Lecturer	Bob Coecke
Degrees	Schedule S1(3rd years) — Computer Science Schedule B1 — Computer Science Schedule B1(M&CS) — Mathematics and Computer Science
Term	Hilary Term 2012  (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 across a variety of areas. Students are also introduced to techniques such as amortised complexity analysis. As in the first-year course, the style of the presentation is rigorous but not formal.

Learning outcomes

On successful completion of the course students will:

• Be able to carry out amortised analysis of data structures, including meggable heaps and disjoint sets.
• Understand the implementation, complexity analysis and applications of algorithms including RSA and primality testing, max flow and the discrete Fourier transform.
• Have an idea of applications of algorithms in a variety of areas.

Synopsis

• Amortised analysis 
• Mergeable heaps 
• Disjoint sets / union-find 
• Number theoretic algorithms
• RSA key encryption
• Primality testing: Miller-Rabin algorithm 
• Fast Fourier transform
• Linear programming 
• Max flow in networks 
• Quantum Fourier transform 

Syllabus

• Amortised analysis 
• Mergeable heaps 
• Disjoint sets / union-find 
• Number theoretic algorithms
• RSA key encryption
• Primality testing: Miller-Rabin algorithm 
• Fast Fourier transform
• Linear programming 
• Max flow in networks 
• Quantum Fourier transform

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).

For the lectures later in the course the following text may be useful.

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, Mcgraw-Hill, 2006. 

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

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.