Course pages 2015–16

# Advanced Algorithms

## Lecture handout

Distributed during the first lecture. An electronic copy of the handout can be found here.

## Lectures

### I. Sorting Networks, Counting Networks and Load Balancing PDF

- 22/04/2016: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
- 25/04/2016: Lecture 2 (Sorting Networks continued: Glimpse at the AKS Sorting Network, Counting Networks)
- 27/04/2016: Lecture 3 (Load Balancing on Graphs, Serial Matrix Multiplication), References: CLRS (3rd edition), Chapter 4

### II. Matrix Multiplication PDF

- 29/04/2016: Lecture 4 (Serial Matrix Multiplication, Linear Programming (Intro, Conversion into Standard Form), References: CLRS (3rd edition), Chapter 4 and 28 (Matrix Mult.), Chapter 29 (Linear Programming)
- Slides 11-25 have been skipped and are not examinable.

### III. Linear Progamming PDF

- 02/05/2016: Lecture 5 (Linear Programming (Conversion into Slack Form, Formulating Problems as Linear Programs)), References: CLRS (3rd edition),
Chapter 29

The proof on slide 21.1/21.2 is not examinable. - 04/05/2016: Lecture 6 (Linear Programming (Simplex Algorithm, Finding an Initial Solution)), References: CLRS (3rd edition), Chapter 29

### IV. Approximation Algorithms: Covering Problems PDF

- 06/05/2016: Lecture 7 (Covering Problems (Vertex Cover)), References: CLRS (3rd edition), Chapter 35.1
- 10/05/2016: Lecture 8 (Covering Problems (Set Cover), Approximation Algorithms via Exact Algorithms (Subset-Sum)), References: CLRS (3rd edition), Chapter 35.3, Chapter 35.5

### V. Approximation Algorithms via Exact Algorithms PDF

- 11/05/2016: Lecture 9 (Approximation Algorithms via Exact Algorithms (Subset-Sum, Parallel Machine Scheduling)), References: CLRS (3rd edition), Chapter 35.5
- Slides 21-22 have been skipped and are not examinable.

### Demonstration: Solving TSP exactly via Linear Programming, Slides PDF, Solving Progress PDF

- 13/05/2016: Lecture 10, References: (see below)
- Not examinable.

### VI. Approximation Algorithms: Travelling Salesman Problem PDF

- 16/05/2016: Lecture 11 (Approximation Algorithms: Travelling Salesman Problem), References: CLRS (3rd edition), Chapter 35.2
- Correction on Slide 8: "All instances with cost >= rho * k" should be replaced by "All instances with cost > rho * k"
- Correction on Slide 12.1-12.3: remove "therefore" in "yields a spanning tree T and therefore..."

### VII. Approximation Algorithms: Randomisation and Rounding PDF

- 18/05/2016: Lecture 12 (Approximation Algorithms: Randomisation and Rounding), References: CLRS (3rd edition), Chapter 35.3
- Correction on Slide 8: "One of the two conditional expectations is greater than E[Y]" should be replaced by "One of the two conditional expectations is at least E[Y]"

## Exercises

## Recommended Reading

- [CLRS] Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2009).
*Introduction to Algorithms. MIT Press (3rd ed.)*

## Additional References

### Sorting and Counting Networks

- Miklos Ajtai, Janos Komlos, Endre Szemeredi.
*Sorting in c log n parallel steps*, Combinatorica 3(1):1-19, 1983. - James Aspnes, Maurice Herlihy, Nir Shavit.
*Counting Networks*, Journal of the ACM 41(5):1020-1048, 1994. - Costas Busch, Maurice Herlihy.
*A Survey on Counting Networks*, Proceedings of the 1st Workshop on Distributed Data and Structures, pages 13-20, 1998. - Vasek Chvatal.
*Lecture Notes on the AKS Sorting Network*, PDF - Shlomo Hoory, Nathan Linial, Avi Wigderson.
*Expander Graphs and their Applications*, Bulletin of the American Mathematical Society, 43(4):439-561, 2006.

### Simplex Algorithm

- Robert G. Bland.
*New finite pivoting rules for the simplex method*, Mathematics of Operations Research 2, (2):103-107, 1977. - Daniel A. Spielman and Shang-Hua Teng.
*Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time*, Journal of the ACM, 51(3):385-463, 2004.

### Approximation Algorithms

- Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson.
*Solution of a Large-Scale Traveling-Salesman Problem*, 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7-28, 2010. - G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson,
*Solution of a Large-Scale Traveling-Salesman Problem*, Operation Research 2:393-410, 1954. - David P. Williamson and David B. Shmoys.
*The Design of Approximation Algorithms*, Cambridge University Press, 2011. (electronic version available here)