Computer Laboratory

Course pages 2014–15

Advanced Algorithms

Lecture handout

Distributed during the first lecture. An electronic copy of the handout can be found here, with minor corrections included. For the sake of completeness, the print (original) version is here.

Lectures

  • All annotated slides from Lecture 1-12 (excluding Case Study) in one single PDF
  • 24/04/2015: Lecture 1 PDF (Sorting Networks: Introduction, Batcher's Sorting Network), References: CLRS (2nd edition), Chapter 27 PDF
  • 27/04/2015: Lecture 2 PDF (Sorting Networks continued: Glimpse at the AKS Sorting Network, Counting Networks), Asynchronous Execution PDF
  • 29/04/2015: Lecture 3 PDF (Load Balancing, Serial Matrix Multiplication), References: CLRS (3rd edition), Chapter 4
  • 01/05/2015: Lecture 4 PDF (Serial Matrix Multiplication (continued), Multithreading, Multithreaded Matrix Multiplication), Reference: CLRS (3rd edition), Chapter 4, Chapter 27, Chapter 28
  • 04/05/2015: Lecture 5 PDF (Linear Programming: Introduction, Standard and Slack Forms), References: CLRS (3rd edition), Chapter 29.1
    • Please change the statement of the Theorem on Slide 21 to: If there exists an optimal solution, one of them occurs at a vertex of the polygon. Please also note the corrections on Slides 14, 15 and 17 replacing ≥ by ≤, which are highlighted in the annotated slides.
  • 06/05/2015: Lecture 6 PDF (Linear Programming: Formulating Problems as Linear Programs, Simplex Algorithm), References: CLRS (3rd edition), Chapter 29.2, 29.3
  • 08/05/2015: Lecture 7 PDF (Linear Programming: Finding Initial Solutions, Fundamental Theorem of Linear Programming, Approximation Algorithms: Vertex Cover), References: CLRS (3rd edition), Chapter 29.3, 29.5, Chapter 35.1
  • 11/05/2015: Lecture 8 PDF (Approximation Algorithms: Vertex Cover (continued), Set Cover), References: CLRS (3rd edition), Chapter 35.1, 35.3
    • Algorithm on Slide 15 was incomplete and has been corrected (thanks to those for pointing this out)
  • 13/05/2015: Lecture 9 PDF (Approximation Algorithms: Subset Sum, Parallel Machine Scheduling), References: CLRS (3rd edition), Chapter 35.5, Problem 35-5
    • Slides 18-22 had to be skipped and are not examinable
  • 15/05/2015: Lecture 10 PDF (Travelling Salesman Problem, Case Study: Solving a classic TSP Instance with Linear Programming and Branch & Bound), not part of the handout References: CLRS (3rd edition), Chapter 35.2
    • not examinable
  • 18/05/2015: Lecture 11 PDF (Approximation Algorithms: Travelling Salesman Problem), References: CLRS (3rd edition), Chapter 35.2
  • 20/05/2015: Lecture 12 PDF (Approximation Algorithms: Randomisation and Rounding Linear Programs), References: CLRS (3rd edition), Chapter 35.3
    • Slides 24-26 had to be skipped and are not examinable, as well as all slides on MAX-CUT

Exercises

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.

Load Balancing

  • S. Muthukrishnan, Bhaskar Ghosh, Martin H. Schultz. First- and Second-Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing, Theory of Computing Systems, 31(4):331-354, 1998.

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)