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 9Oct2017): pdf
 Exercises, second series (deadline 23Oct2017): pdf UPDATE (18Oct): In 3b, `feasible' should be `optimal'. This is updated in the pdf.
 Exercises, third series (deadline 6Nov2017): pdf
 Exercises, fourth series (deadline 20Nov2017): 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

11Sep2017: (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; NPcompleteness; SAT is NPcomplete
For further reading, I can recommend `Introduction to Algorithms’ by Cormen, Leiserson, Rivest and Stein: Chapter 13 (on the basics), Chapter 23 (on minimum spanning tree) and Chapter 34 (on NPcompleteness)

18Sep2017: (NPcomplete problems)
Catalogue of NPcomplete problems: 3SAT; 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 121140), 1979. Here is an electronic copy.
Chapter 34 of the aforementioned book by Cormen, Leiserson, Rivest and Stein contains a lot of information on NPcompleteness, but the wikipedia page is also a good (and less heavy) start.

25Sep2017: (Strong/ weak NPhardness, coNP) pdf, excel sheet
More NPcomplete problems: Exact cover; Subset sum; Partition;
pseudopolynomial time; strong NPhardness; weak NPhardness; Threepartition;
coNP; coNP versus NP; Halting problem

2Oct2017: No lecture!!

9Oct2017: (Approximation algorithms) pdf slides week 4&5
Vertex cover (matching; LP);
Makespan (greedy);
TSP (doubletree; tree+matching);
communication delay scheduling
(pp 711 in this pdffile)

16Oct2017: (More on approximation algorithms)
Approximation schemes; Inapproximability
(pp 745 in this pdffile for more information)

23Oct2017: (Exact algorithms for NPhard problems) Slides (pptx) Lecture notes (pdf)

30Oct2017: (More exact algorithms for NPhard problems) Slides (pptx) Lecture notes (pdf)

6Nov2017: (Treewidth) Slides (pptx) Lecture notes (pdf)

13Nov2017: (Randomized Algorithms) Slides (pptx)
Extra material

Stephen Cook's
paper
The Complexity of TheoremProving Procedures
from 1971 contains the proof that SAT is NPcomplete

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

Richard Lipton:
Is P=NP an Ill Posed Problem?
 Gerhard Woeginger's "PversusNP" page
 Nice movie on Youtube explaining PversusNP in very accessible way

The
game that led to Hamiltonian cycles

Lots of information on the TSP.

A nice instance of SUBSETSUM (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 LProunding results for MaxSatisfiability.
 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:
NPcomplete Problems and Physical Reality
Updated on November 14, 2017
by Jesper Nederlof (based on a previous version by G.J. Woeginger)