Department of Computer Science and Technology

Course pages 2018–19

Advanced Algorithms

  • There will be an example class on Thursday 23 May from 16.15-17.30 in LT2. Tentative List of Topics: Knapsack Problem (Greedy, LP, PTAS) plus selection of supervision questions.
  • The questions for the example sheet: PDF
  • Solutions will be available after class: PDF

    • Lecture handout

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

    Lectures

    I. Course Intro, Sorting Networks, Counting Networks (Slides PDF)

    • 26/04/2019: Lecture 1 (Course Intro, Sorting Networks), References: CLRS (2nd edition), Chapter 27 PDF
    • 29/04/2019: Lecture 2 (Sorting Networks continued, Glimpse at the AKS Sorting Network), References: see additional references below
    • 01/05/2019: Lecture 3 (Counting Networks), References: see additional references below

    II. Linear Progamming (Slides PDF)

    • 01/05/2019: Lecture 3 (Linear Programming: Intro), 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.
    • 03/05/2019: Lecture 4 (Linear Programming: Standard and Slack Form, Simplex Algorithm, References: CLRS (3rd edition) Chapter 29
    • 06/05/2019: Lecture 5 (Linear Programming: Simplex Algorithm (cntd.), Termination, Finding an Initial Solution), Introduction to Approximation Algorithms), References: CLRS (3rd edition) Chapter 29

    IV. Approximation Algorithms: Covering Problems (Slides PDF)

    • 08/05/2019: Lecture 6 (Covering Problems (Vertex Cover)), References: CLRS (3rd edition), Chapter 35.1
    • 10/05/2019: Lecture 7 (Covering Problems (Set Cover)), References: CLRS (3rd edition), Chapter 35.1
    • Addition to Slide 15: (computing $G_u$ or $G_v$ itself could take $Theta(E)$ time)
    • Correction on Slide 19 and 23: one of the two occurences of |S| should be replaced by S.
    • Correction on Slide 23: The cost function should map from F to the positive reals.

    V. Approximation Algorithms via Exact Algorithms (Slides PDF)

    • 13/05/2019: Lecture 8 (Approximation Algorithms via Exact Algorithms (Subset-Sum, Machine Scheduling)), References: CLRS (3rd edition), Chapter 35.3, Chapter 35.5
    • Slides 17-22 were not covered and are not examinable.

    VI. Approximation Algorithms: Travelling Salesman Problem (Slides PDF)

    • 15/05/2019: Demonstration: Solving TSP exactly via Linear Programming, Slides (Many thanks to Andrej Ivaskovic and Petar Velickovic) PDF, PDF 4up, Solution Progress PDF (Remark: The slides on the solution progress are from a previous year and show a slightly different progress.) An overview of the progress towards the solution in the lecture is here: PDF
    • Any material presented on 15/05/2018 is not examinable.
    • 17/05/2019: Lecture 10 (Travelling Salesman Problem (Metric TSP: MST-Approximation, Christofides Algorithm), References: CLRS (3rd edition), Chapter 35.2

    VII. Approximation Algorithms: Randomisation and Rounding (Slides PDF)

    • 20/05/2019: Lecture 11 (Randomised Approximation Algorithms, MAX3-CNF, Vertex Cover), References: CLRS (3rd edition), Chapter 35.3
    • 22/05/2019: Lecture 12 (Randomised Approximation Algorithms cntd., Set Cover, MAX-CNF), References: CLRS (3rd edition), Chapter 35.3
    • Slides 33-34 were not covered and are not examinable.

    Exercises (complete solution notes are available to the supervisors)

    • PDF
      • Please ignore the Exercise Questions 10-13, which are on a topic that is no longer covered.

    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)