Course pages 2014–15

# Advanced Algorithms

**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

## 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