Department of Computer Science and Technology

Lecture handout

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

Lectures

All slides combined PDF

I. Sorting Networks, Counting Networks (Slides PDF)

• 27/04/2018: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
• 30/04/2018: Lecture 2 (Sorting Networks continued, Glimpse at the AKS Sorting Network, Counting Networks), References: see additional references below, Additional Notes from the Lecture PDF

II. Matrix Multiplication (Slides PDF)

• 02/05/2018: 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)

III. Linear Progamming (Slides PDF)

• 04/05/2018: Lecture 4 (Linear Programming (Conversion into Standard and Slack Form, Geometry and Structure of Optimal Solutions)), References: CLRS (3rd edition), Chapter 29
• A more detailed version of the proof on slide 21 (which is non-examinable) can be found here PDF.
• 07/05/2018: Lecture 5 (Linear Programming (Simplex Algorithm), References: CLRS (3rd edition) Chapter 29
• 09/05/2018: Lecture 6 (Linear Programming (Finding an Initial Solution), Introduction to Approximation Algorithms), References: CLRS (3rd edition) Chapter 29

IV. Approximation Algorithms: Covering Problems PDF

• 11/05/2018: Lecture 7 (Covering Problems (Vertex Cover, Set Cover)), References: CLRS (3rd edition), Chapter 35.1
• Slide 22: "|X|=u_0" should be replaced by "|S|=u_0"

V. Approximation Algorithms via Exact Algorithms PDF

• 14/05/2018: 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

• 16/05/2018: Demonstration: Solving TSP exactly via Linear Programming, Slides (Many thanks to Andrej Ivaskovic and Petar Velickovic) PDF, Solution Progress PDF (Remark: These slides are from a previous year and show a slightly different progress.)
• Any material presented on 16/05/2018 is not examinable.
• 18/05/2018: Lecture 10 (Travelling Salesman Problem (Metric TSP: MST-Approximation, Christofides Algorithm), References: CLRS (3rd edition), Chapter 35.2

VII. Approximation Algorithms: Randomisation and Rounding PDF

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

Exercises (complete solution notes are available to the supervisors)

• [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)
• © 2018 Department of Computer Science and Technology, University of Cambridge
Information provided by Dr Thomas Sauerwald