Course AC: Algorithms and Complexity
(LNMB, Fall 2021)

This basic course explains the basics of algorithms and complexity. It assumes only knowledge of basic mathematics (set and logic notation, linear algebra, proof by induction, probability theory, big-O notation).

LNMB page: http://www.lnmb.nl/pages/courses/phdcourses/AC.html

Lecturers: Marie Schmidt (schmidt2@rsm.nl) and Tom van der Zanden  (T.vanderZanden@maastrichtuniversity.nl)

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

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

Important: comments on the homework

• Exercises, first series (deadline 4-Oct-2021): pdf
• Exercises, second series (deadline 18-Oct-2021): pdf
• Exercises, third series (deadline 1-Nov-2021): pdf
• Exercises, fourth series (deadline 15-Nov-2021): pdf

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

If you are not yet familiar with "graphs" or want to refresh your knowledge, please watch this video (slides) before the first lecture on September 13.

Summary of lectures

• 13-Sep-2021: (Introduction, basic concepts, P versus NP): recording - slides
  Bonus material (not mandatory) on Turing machines: recording - slides
  
• 20-Sep-2021: (NP-complete problems): recording - slides
  
  • Extra slides NP-completeness proofs
  • SAT to ILP
  • SAT to 3-SAT
  • SAT to Clique: see lecture 2
  • Clique to Independent Set
  • Independent Set to Exact Cover
  • Independent Set to Vertex Cover
  • Vertex Cover to Hamiltonian Cycle
  • Hamiltonian Cycle to TSP: see lecture 2
  • Proof (sketch) of the Cook-Levin Theorem (non-madatory)
• 27-Sep-2021: (Strong/ weak NP-hardness, co-NP): recording - slides - undecidable problem (not mandatory)
  
• 4-Oct-2021: (Approximation algorithms): recording - slides
  
• 11-Oct-2021: (More on approximation algorithms): recording - slides
  
• 18-Oct-2021: (Exact algorithms for NP-hard problems): video lecture - lecture notes + exercises - slides
  
• 25-Oct-2021: (More exact algorithms for NP-hard problems): video lecture - lecture notes + exercises - slides - SubsetSum.xls
• 1-Nov-2021: (Treewidth): video lecture - lecture notes + exercises - slides
• 8-Nov-2021: (Randomized Algorithms): video lecture - slides - (no lecture notes)
• 15-Nov-2021: No Lecture!!

• 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
• Famous book on NP-completeness by Garey and Johson:Computers and Intractability: A Guide to the Theory of NP-Completeness
• 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