Thursday 10:00-11:00For location see Datanose. The first lecture is on Tuesday, September 1 at 9:00 am in room SP A1.04.
Exercises will be handed out on Thursday and have to be handed in on Thursday one week later. 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 be a final exam. 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 average between the grade for the exercises and the final exam.
If you want to take the resit exam, please send an email to Jeroen Zuiddam.
|1 Sep. 9-11||SP904 A1.04||Introduction to computational complexitySlidesHomework 1, due 8 Sep. 9:00 am. Handing in via email is encouraged.|
|3 Sep. 10-11||SP904 G3.02||Exercise session on asymptotic notations.Exercises, solutionsBook: 0.3|
|3 Sep. 11-13||SP904 C1.112||P, NP, reductions, co-NPBook: 1.1–1.4, 1.6, 1.7, 2.1, 2.2|
|8 Sep. 9-11||SP904 A1.04||Cook-Levin Thm: 3-SAT is NP-complete, Decision vs SearchBook: 2.3, 2.5Homework 2 (updated 15 Sep.), due Thursday 17 Sep. 10:00 am.|
|10 Sep. 10-11||SP123 CWI L016||Exercise session on homework.|
|10 Sep. 11-13||SP123 CWI L016||Diagonalization, time hierarchiesBook: 3.1, 3.2|
|15 Sep. 9-11||SP904 A1.04||RelativizationBook: 3.4|
|17 Sep. 10-11||SP904 G2.02||Exercise session on homework 2.Homework 3 (updated 22 Sep.), due Thursday 24 Sep. 10:00 am.|
|17 Sep. 11-13||SP904 B0.201||Space complexity, PSPACE, L, NLBook: Chapter 4|
|22 Sep. 9-11||SP904 G3.02||Immerman-Szelepcsényi theorem, the polynomial hierarchyBook: 4.3.2, Chapter 5|
|24 Sep. 10-11||SP904 G0.05||Exercise session on homework 3.Homework 4, due Thursday 1 Oct. 11:00 am.|
|24 Sep. 11-13||SP904 G5.29||Circuit complexity, the Karp-Lipton TheoremBook: Chapter 6|
|29 Sep. 9-11||SP904 A1.04||Parity not in AC^0Book: 14.2|
|1 Oct. 9-11||SP123 CWI L016||Probabilistic algorithmsBook: 7.1–7.3|
|1 Oct. 10-11||SP123 CWI L016||Exercise session on homework 4.Homework 5, due Thursday 8 Oct. 10:00 am.|
|6 Oct. 9-11||SP904 A1.04||BPP, circuits and polynomial hierarchyBook: 7.3–7.5|
|8 Oct. 10-11||SP904 G3.02||Exercise session on homework 5.Homework 6, due Thursday 15 Oct. 10:00 am.|
|8 Oct. 11-13||SP904 G4.15||Interactive proofs, Graph-Isomorphism problemBook: 8.1–8.2|
|13 Oct. 9-11||SP904 A1.04||IP = PSPACEBook: 8.3|
|15 Oct. 10-11||SP123 CWI L016||Exercise session on homework 6.|
|15 Oct. 11-13||No lecture|
|19 Oct. 11-13||SP123 CWI L016||Question sessionHomework 6 will have been graded.|
|21 Oct. 9-12||SP912 H0.08||ExamYou are allowed to bring books and notes, but no electronic devices.Old exam|
|5 Jan. 18-21||SP904 D1.160||Resit examPlease register by sending an email to Jeroen Zuiddam.|
See also the website of the 2013/2014 course.