Computer Laboratory

Course pages 2015–16

Advanced Algorithms

Lecture handout

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


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.


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)