Course pages 2019–20
Advanced Algorithms
I. Course Intro, Sorting Networks, Counting Networks
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (2nd edition), Chapter 27 PDF
II. Linear Programming
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (3rd edition), Chapter 29
III. Approximation Algorithms: Intro and Covering Problems
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (3rd edition), Chapter 35.1, 35.3
IV. Approximation Algorithms: Approximation via Exact Algorithms
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (3rd edition), Chapter 35.5, Problems 35-5
V. Approximation Algorithms: Travelling Salesman Problem
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (3rd edition), Chapter 35.2
VI. Approximation Algorithms: Randomisation and Rounding, Course Summary
- Slides (everything incl. animations) PDF
- Slides (Handout excl. animations) PDF
- Reference: CLRS (3rd edition), Chapter 35.4
VII. Demo: Solving the Travelling Salesman Problem using Linear/Integer Programming (special thanks to Andrej Ivaskovic and Petar Velickovic)
- Slides of the Lecture (by Andrej Ivaskovic) PDF
- Diagram of the Solution Progress of Demo PDF
- More detailed Slides (slightly different demo though) PDF
- Reference: CLRS (3rd edition), Chapter 35.2, article by Dantzig, Fulkerson and Johnson mentioned below
- For Recordings of Lecture and Demo, please see the Recordings page
Exercises (complete solution notes are available to the supervisors)
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)