# Computer Laboratory

Course pages 2016–17

# 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 (Slides PDF)

• 28/04/2017: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
• 01/05/2017: Lecture 2 (Sorting Networks continued, Glimpse at the AKS Sorting Network, Counting Networks), References: see additional references below
• Slide 23: "compares inputs i and n-i" should be replaced by "compares inputs i and n-i+1" (thanks to Dimitrios Los for pointing this out)

### II. Matrix Multiplication (Slides PDF)

• 03/05/2017: Lecture 3 (Matrix Multiplication, Dynamic Multithreading, Parallel Matrix Multiplication) References: CLRS (3rd edition), Chapter 4 and 28 (Serial and Parallel Matrix Multiplication), Chapter 27 (Multithreading)
• Slides 25-26 were skipped and are not examinable.

### III. Linear Progamming (Slides PDF)

• 05/05/2017: Lecture 4 (Linear Programming (Conversion into Standard and Slack Form, Geometry and Structure of Optimal Solutions)), References: CLRS (3rd edition), Chapter 29
• The proof on slide 21.1/21.2 is not examinable, since only a sketch was presented in the lecture. However, for the sake of completeness, a more detailed version of the proof can be found here PDF.
• 08/05/2017: Lecture 5 (Linear Programming (Formulating Problems as Linear Programs, Simplex Algorithm)), References: CLRS (3rd edition) Chapter 29
• 10/05/2017: Lecture 6 (Linear Programming (Simplex Algorithm, Finding an Initial Solution)), References: CLRS (3rd edition), Chapter 29
• Slide 37, line 2 of code: "new vector of length $n$" should be replaced by "new vector of length $m$" (thanks to a student for pointing this out)
• Slide 47, the objective function "2*x_1+2*x_2" should be replaced by "2*x_1+x_2" (thanks to Devan Kuleindiren for pointing this out)
• Slide 49: "Initialize-Simplex calls Simplex" should be replaced by "Initialize-Simplex followed by Simplex"

### IV. Approximation Algorithms: Covering Problems PDF

• 12/05/2017: Lecture 7 (Covering Problems (Vertex Cover, Set Cover)), References: CLRS (3rd edition), Chapter 35.1
• Slide 19: "\sum_{i=1}^k \frac{1}{k}" should be replaced by "\sum_{i=1}^k \frac{1}{i}"(thanks to a student for pointing this out)

### V. Approximation Algorithms via Exact Algorithms PDF

• 15/05/2017: Lecture 8 (Approximation Algorithms via Exact Algorithms (Subset-Sum, Machine Scheduling)), References: CLRS (3rd edition), Chapter 35.3, Chapter 35.5
• Slides 21-22 dealing with the PTAS for Parallel Machine Scheduling were skipped and are not examinable.

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

• 17/05/2017: Demonstration: Solving TSP exactly via Linear Programming, Slides PDF, Solving Progress PDF (Remark: These slides are from previous year and show a slightly different progress.)
• Any material presented on 17/05/2017 is not examinable.
• 19/05/2017: Lecture 10 (Travelling Salesman Problem (General TSP, Metric TSP), References: CLRS (3rd edition), Chapter 35.2

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

• 22/05/2016: Lecture 11 (Randomised Approximation Algorithms, MAX3-CNF, Vertex Cover), References: CLRS (3rd edition), Chapter 35.3
• 24/06/2016: Lecture 12 (Randomised Approximation Algorithms cntd., Set Cover), References: CLRS (3rd edition), Chapter 35.3

### VIII. Approximation Algorithms: MAX-CUT Problem (Outlook) PDF

• All slides on MAX-CUT are not examinable.

## 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)
• © 2017 Computer Laboratory, University of Cambridge
Information provided by Dr Thomas Sauerwald