Course pages 2018–19
Advanced Algorithms
Principal lecturer: Dr Thomas Sauerwald
Taken by: Part II CST 50%, Part II CST 75%
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, linear programming and approximation algorithms.
Lectures
- Sorting Networks. Zero-one principle. Merging Network, Bitonic
Sorter. Counting Networks. [CLRS2, Chapter 27]
- Linear Programming. Definitions and Applications. Formulating
Linear Programs. The Simplex Algorithm. Finding Initial Solutions.
[CLRS3, Chapter 29]
- Approximation Algorithms. (Fully) Polynomial-Time Approximation
Schemes. Design Techniques. Applications: Vertex Cover, Subset-Sum, Parallel
Machine Scheduling, Travelling Salesman Problem (including a practical
demonstration how to solve a TSP instance exactly using linear programming),
Hardness of Approximation. [CLRS3, Chapter 35]
- Randomised Approximation Algorithms. Randomised Approximation
Schemes. Linearity of Expectations and Randomised Rounding of Linear Programs.
Applications: MAX3-SAT problem, Weighted Vertex Cover, Weighted Set Cover.
Summary: MAX-SAT problem and discussion of various approximation algorithms.
[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