Computer Laboratory

Course pages 2016–17

Advanced Algorithms

Lecture handout

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

Lectures

I. Sorting Networks, Counting Networks (Slides PDF)

  • 28/04/2017: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
  • 01/05/2017: Lecture 2 (Sorting Networks continued, Glimpse at the AKS Sorting Network, Counting Networks), References: see additional references below
  • Slide 23: "compares inputs i and n-i" should be replaced by "compares inputs i and n-i+1" (thanks to Dimitrios Los for pointing this out)

II. Matrix Multiplication (Slides PDF)

  • 03/05/2017: 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)
  • Slides 25-26 were skipped and are not examinable.

III. Linear Progamming (Slides PDF)

  • 05/05/2017: Lecture 4 (Linear Programming (Conversion into Standard and Slack Form, Geometry and Structure of Optimal Solutions)), References: CLRS (3rd edition), Chapter 29
  • The proof on slide 21.1/21.2 is not examinable, since only a sketch was presented in the lecture. However, for the sake of completeness, a more detailed version of the proof can be found here PDF.
  • 08/05/2017: Lecture 5 (Linear Programming (Formulating Problems as Linear Programs, Simplex Algorithm)), References: CLRS (3rd edition) Chapter 29
  • 10/05/2017: Lecture 6 (Linear Programming (Simplex Algorithm, Finding an Initial Solution)), References: CLRS (3rd edition), Chapter 29
  • Slide 37, line 2 of code: "new vector of length $n$" should be replaced by "new vector of length $m$" (thanks to a student for pointing this out)
  • Slide 47, the objective function "2*x_1+2*x_2" should be replaced by "2*x_1+x_2" (thanks to Devan Kuleindiren for pointing this out)
  • Slide 49: "Initialize-Simplex calls Simplex" should be replaced by "Initialize-Simplex followed by Simplex"

IV. Approximation Algorithms: Covering Problems PDF

  • 12/05/2017: Lecture 7 (Covering Problems (Vertex Cover, Set Cover)), References: CLRS (3rd edition), Chapter 35.1
  • Slide 19: "\sum_{i=1}^k \frac{1}{k}" should be replaced by "\sum_{i=1}^k \frac{1}{i}"(thanks to a student for pointing this out)

V. Approximation Algorithms via Exact Algorithms PDF

  • 15/05/2017: 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

  • 17/05/2017: Demonstration: Solving TSP exactly via Linear Programming, Slides PDF, Solving Progress PDF (Remark: These slides are from previous year and show a slightly different progress.)
  • Any material presented on 17/05/2017 is not examinable.
  • 19/05/2017: Lecture 10 (Travelling Salesman Problem (General TSP, Metric TSP), References: CLRS (3rd edition), Chapter 35.2

VII. Approximation Algorithms: Randomisation and Rounding PDF

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

VIII. Approximation Algorithms: MAX-CUT Problem (Outlook) PDF

  • All slides on MAX-CUT are not examinable.

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.

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)