Course pages 2015–16

Advanced Algorithms

Lecture handout

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

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

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.

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

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

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.

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..."

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.

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.

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.

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)