Activities
Exams
- Quiz 1: 04 SEP
- Quiz 2: 16 OCT
- End Sem: 14 NOV
Problem Sets
- PS 1: Given on 17 AUG. Deadline 31st AUG
- PS 2: To be given on 24 SEP. Deadline 09 Oct
- PS 3: To be given on 07 Oct (tentative). Deadline 21 Oct
- PS 4: To be given on 22 Oct (tentative). Deadline 02 Nov
- PS 5 (Optional): Given on 02 Nov (tentative). Deadline 10 NOV
Presentations
A list of topics will be announced during the last week of Septemeber. Presentations will be held in early November in extra slots.
- Kleene Recursion theorem -- Chapter 23 of Kozen.
- Gap and Speedup theorems --- Chapter 32 of Kozen
- Post Correspondence Problem
- Busy Beaver function
- NP hardness of planar Clustering
- March Madness is NP hard
- Time vs Space and related problems
- Structure of the class Delta2p
- Bounded query machines: On NP and PSPACE