# Computer Laboratory

Course pages 2016–17

Principal lecturer: Dr Thomas Sauerwald
Taken by: Part II
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. [CLRS2, Chapter 27]

• Parallel Algorithms. Dynamic multithreading. Modelling framework: work and span. Greedy scheduler. [CLRS3, Chapter 27]

• Matrix Multiplication. Strassen’s algorithm. Parallel Matrix Multiplication. [CLRS3, Chapters 4, 27 and 28]

• 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-CNF problem, Weighted Vertex Cover, Weighted Set Cover. [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.

* 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

• © 2017 Computer Laboratory, University of Cambridge
Information provided by Dr Thomas Sauerwald