Course pages 2015–16

**Subsections**

##

Advanced Algorithms

*Lecturer: Dr T.M. Sauerwald*

*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