Course AC: Algorithms and Complexity
(LNMB, Fall 2017)
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);
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)
The Complexity of Theorem-Proving Procedures
from 1971 contains the proof that SAT is NP-complete
of Cook's theorem by Richard Lipton
Reducibility Among Combinatorial Problems
showed that 21 diverse combinatorial and graph theoretical problems are NP-complete.
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
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?
lecture notes by Lex Schrijver on matchings
lecture notes by David Williamson on Approximation Algorithms.
That's old stuff from Fall'1998, but it still does read well.
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.
NP-complete Problems and Physical Reality
Updated on November 14, 2017
by Jesper Nederlof (based on a previous version by G.J. Woeginger)