Course pages 2020–21 (these pages are still being updated)

# 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