Course pages 2014–15
Principal lecturer: Dr Thomas Sauerwald
Taken by: Part II
Past exam questions
Information for supervisors (contact lecturer for access permission)
The final lecture will be held on Tuesday May 19 from 11-12 in LT2 (instead of Wednesday May 20)
No. of lectures: 12
Suggested hours of supervisions: 3
Prerequisite courses: Algorithms
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.
- 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]
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
* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein,
C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN