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.
  1. Kleene Recursion theorem -- Chapter 23 of Kozen.
  2. Gap and Speedup theorems --- Chapter 32 of Kozen
  3. Post Correspondence Problem
  4. Busy Beaver function
  5. NP hardness of planar Clustering
  6. March Madness is NP hard
  7. Time vs Space and related problems
  8. Structure of the class Delta2p
  9. Bounded query machines: On NP and PSPACE