Lecturer: Harry Buhrman
Teaching assistant: Florian Speelman
Email: firstname.lastname@cwi.nl
You can find your grades on blackboard. Most of you made it, good job! Please send us an e-mail if you do not find your grade there, or have trouble accessing blackboard.
There will be a resit, date and time: Wednesday July 9th, 14:00-17:00 at Science Park B0.209.
Please send us an e-mail if you want to participate in the resit.
Monday 17-19 at D1.162
Wednesday 13-15 at D1.115
Wednesday 15-17 at D1.115
Exercises will be handed out every week, they should be handed in at the start of the Monday lecture of the next week. The solutions should either be handed in by paper (handwritten is fine), or sent by email to Florian. You are allowed to cooperate, but everyone has to write down their solution in their own words. When computing the average grade for the exercises, the lowest score will be dropped.
Besides the exercises there will also be a final exam on May 26th. The exam will be open book, which means you are allowed to bring the book and any notes you made - digital equipment is not allowed. The final grade for the course will be the calculated as the average between the grade for the exercises and the final exam.
Previous year's exam is available online. Don't forget that the exact topics tested (and exam size) will not necessarily be the same this year!
| Monday, Mar 31 |
Introduction to computational complexity Slides Homework #1 (Exercise 4 updated on April 2! Also slight rewording of Exercise 3 on April 3.) |
|---|---|
| Wednesday, April 2 | P, NP, reductions, co-NP Book 1.1-1.4, 1.6, 1.7, 2.1, 2.2 Exercises to solve in class |
| Monday, April 7 |
Cook-Levin Thm: 3-SAT is NP-complete, Decision vs Search Book 2.3, 2.5 Homework #2 |
| Wednesday, Apr 9 |
Diagonalization, time hierarchies Book 3.1, 3.2 |
| Monday, April 14 |
Relativization Book 3.4 Homework #3 (Clarification of definition 1.(II) on April 17.) |
| Wednesday, April 16 |
Space complexity, PSPACE, L, NL Book chapter 4 |
| Monday, Apr 21 | No class |
| Wednesday, April 23 |
Immerman-Szelepcsényi theorem The polynomial hierarchy Book 4.3.2, chapter 5 Homework #4 |
| Monday, April 28 | Circuit complexity, the Karp-Lipton Theorem Book chapter 6 Homework #5 |
| Wednesday, April 30 |
Parity not in AC^0 Book 14.2 |
| Monday, May 5 | No class |
| Wednesday, May 7 |
Probabilistic algorithms Book 7.1 - 7.3 Homework #6 |
| Monday, May 12 |
BPP, circuits and polynomial hierarchy Book 7.3 - 7.5 Homework #7 |
| Wednesday, May 14 |
Interactive proofs, Graph-Isomorphism problem Book 8.1 - 8.2 |
| Monday, May 19 |
IP = PSPACE Book 8.3 |
| Wednesday, May 21 |
Final exercise session & any questions you might have (Florian) Class starts at 13:00, which means we'll finish a bit earlier than normal. |
| Monday, May 26 |
Final exam 15-18 at Science Park D1.115. |
| Wednesday, July 9 |
Exam resit 14-17 at Science Park B0.209. |