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

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

Lecturer: Marie Schmidt (schmidt2@rsm.nl) and 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 30-Sep-2019): pdf
• Exercises, second series (deadline 14-Oct-2019): pdf
• Exercises, third series (deadline 28-Oct-2019): pdf
• Exercises, fourth series (deadline 11-Nov-2019): 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

Summary of lectures

• 9-Sep-2019: (Introduction, basic concepts, P versus NP) slides
  
• 16-Sep-2019: (NP-complete problems)
  
• 23-Sep-2019: (Strong/ weak NP-hardness, co-NP) slides
  
• 30-Oct-2019: (Approximation algorithms) slides
  
• 7-Oct-2019: (More on approximation algorithms slides
  
• 14-Oct-2019: (Exact algorithms for NP-hard problems) slides, lecture notes, solutions
  
• 21-Oct-2019: (More exact algorithms for NP-hard problems) slides, lecture notes, SubsetSum.xls, solutions
• 28-Oct-2019: (Treewidth) slides, lecture notes
• 4-Nov-2019: (Randomized Algorithms) slides
• 11-Nov-2019: 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