# Computer Laboratory

Course pages 2015–16

## 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]"
VIII. MAX-CUT Problem was not covered and is not examinable.

## Exercises

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

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