Computer Laboratory

Course pages 2015–16

Advanced Algorithms

Principal lecturer: Dr Thomas Sauerwald
Taken by: Part II
Past exam questions

No. of lectures: 12
Suggested hours of supervisions: 3
Prerequisite courses: Algorithms

Aims

The aim of this course is to introduce advanced techniques for the design and analysis of algorithms that arise in a variety of applications. A particular focus will be on parallel algorithms and approximation algorithms.

Lectures

  • Sorting networks. Building blocks of sorting networks. Zero-one principle. Merging network. Bitonic sorter. AKS Network.

  • Load balancing. Basic approaches including diffusion, first order and second order scheme. Performance measures. Spectral analysis and convergence rate.

  • Matrix multiplication. Strassen’s algorithm. Matrix inversion vs. matrix multiplication. Parallel matrix multiplication. [CLRS3, Chapters 4, 27 and 28]

  • Linear programming. Definitions and applications. Formulating linear programs. The simplex algorithm. Finding initial solutions. Fundamental theorem of linear programming. [CLRS3, Chapter 29]

  • Approximation algorithms. (Fully) Polynomial-time approximation schemes. Design techniques. Applications: Vertex cover, Travelling Salesman Problem, parallel machine scheduling. Hardness of approximation. [CLRS3, Chapter 35]

  • Randomised approximation algorithms. Randomised approximation achemes. Linearity of expectations and randomised rounding of linear programs. Applications: MAX3-CNF problem, weighted vertex cover, MAX-CUT. [CLRS3, Chapter 35]

Objectives

At the end of the course students should

  • have an understanding of algorithm design for parallel computers

  • be able to formulate, analyse and solve linear programs

  • have learned a variety of tools to design efficient (approximation) algorithms

Recommended reading

* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8