# Course AC: Algorithms and Complexity (LNMB, Fall 2017)

LNMB page: http://www.lnmb.nl/pages/courses/phdcourses/AC.html
Lecturer: Jesper Nederlof  (j.nederlof@tue.nl)

Acknowledgement: Much of the material used in this course was previously developed by Gerhard Woeginger.

Exercises (four series)
(If you have questions, send me an email or ask me on Monday)

Important: comments on the homework

• Exercises, first series (deadline 9-Oct-2017): pdf
• Exercises, second series (deadline 23-Oct-2017): pdf UPDATE (18-Oct): In 3b, `feasible' should be `optimal'. This is updated in the pdf.
• Exercises, third series (deadline 6-Nov-2017):  pdf
• Exercises, fourth series (deadline 20-Nov-2017): pdf Mail your solutions. I will reply the mail with the reviewed assignment and all grades.

Note: For those lacking background in algorithms design, I recommend to (at least) browse through the first 3 chapters of `Introduction to Algorithms’ by Cormen, Leiserson, Rivest and Stein

Summary of lectures

• 11-Sep-2017: (Introduction, basic concepts, P versus NP) pdf slides week 1&2; pdf handout week 1&2
problems; instances & size; algorithm & running time & polynomiality;
examples of some basic algorithms;
P & NP; certificates; P versus NP; reductions; NP-completeness; SAT is NP-complete
For further reading, I can recommend `Introduction to Algorithms’ by Cormen, Leiserson, Rivest and Stein: Chapter 1-3 (on the basics), Chapter 23 (on minimum spanning tree) and Chapter 34 (on NP-completeness)

• 18-Sep-2017: (NP-complete problems)
Catalogue of NP-complete problems: 3-SAT; integer programming; clique; independent set;
vertex cover; directed Hamiltonian cycle; undirected Hamiltonian cycle; TSP

For the presented reductions, see
J.K. Lenstra, A.H.G. Rinnooy Kan. Computational complexity of discrete optimization problems.
Annals of Discrete Mathematics 4 (pp 121-140), 1979. Here is an electronic copy.
Chapter 34 of the aforementioned book by Cormen, Leiserson, Rivest and Stein contains a lot of information on NP-completeness, but the wikipedia page is also a good (and less heavy) start.

• 25-Sep-2017: (Strong/ weak NP-hardness, co-NP) pdf, excel sheet
More NP-complete problems: Exact cover; Subset sum; Partition;
pseudo-polynomial time; strong NP-hardness; weak NP-hardness; Three-partition;
co-NP; co-NP versus NP
; Halting problem

• 2-Oct-2017: No lecture!!

• 9-Oct-2017: (Approximation algorithms)  pdf slides week 4&5
Vertex cover (matching; LP); Makespan (greedy); TSP (double-tree; tree+matching);
communication delay scheduling (pp 7-11 in this pdf-file)

• 16-Oct-2017: (More on approximation algorithms)
Approximation schemes; Inapproximability
(pp 7-45 in this pdf-file for more information)

• 23-Oct-2017: (Exact algorithms for NP-hard problems) Slides (pptx) Lecture notes (pdf)

• 30-Oct-2017: (More exact algorithms for NP-hard problems) Slides (pptx) Lecture notes (pdf)

• 6-Nov-2017: (Treewidth) Slides (pptx) Lecture notes (pdf)

• 13-Nov-2017: (Randomized Algorithms) Slides (pptx)

Extra material
• Stephen Cook's paper The Complexity of Theorem-Proving Procedures from 1971 contains the proof that SAT is NP-complete
• Another proof of Cook's theorem by Richard Lipton
• Richard Karp's landmark paper Reducibility Among Combinatorial Problems showed that 21 diverse combinatorial and graph theoretical problems are NP-complete.
• Richard Lipton: Is P=NP an Ill Posed Problem?
• Gerhard Woeginger's "P-versus-NP" page
• Nice movie on Youtube explaining P-versus-NP in very accessible way
• The game that led to Hamiltonian cycles
• Lots of information on the TSP.
• A nice instance of SUBSET-SUM (where items can be used multiple times). Can you help the waiter?
• Some lecture notes by Lex Schrijver on matchings
• Some lecture notes by David Williamson on Approximation Algorithms. That's old stuff from Fall'1998, but it still does read well.
• The book of Vijay Vazirani on Approximation Algorithms. Chapter 16 contains some nice LP-rounding results for Max-Satisfiability.
• The book of Rod Downey and Mike Fellows on Parameterized Complexity. The first three chapters provide a very nice and gentle introduction into the field.
• Scott Aaronson's Complexity Zoo
• Scott Aaronson: NP-complete Problems and Physical Reality

Updated on November 14, 2017
by Jesper Nederlof (based on a previous version by G.J. Woeginger)