In Easter Term 2020, I supervised Complexity Theory and Introduction to Probability at the University of Cambridge.
Here are the exercise sheets I prepared for Complexity Theory, lectured by the awesome Prof. Anuj Dawar. Each was originally also accompanied by a few extra exercises from the lecturer’s problem sheet.
- Supervision 1: Algorithms and problems, Time and space, Time complexity, Non-determinism, Reductions, NP-completeness
- Supervision 2: More on NP-completeness, co-NP
- Supervision 3: Function classes, Space complexity, Hierarchy theorems