Theoretical Computer Science
Texts
Grading

Midterm: 40%

H.W.: 10%

Presentation : 10%

Final: 40%
Couse Content & Work
We will cover the first 7 chapters of the CC book. Every student will also have to make a presentation on one of the other chapters in the book. These presentations will be at the end of the semester.
There will be homework every single week. You must hand in the H.W. at the beginning of the next class. The midterm and final questions will be similar to the H.W. questions.
Learning Outcomes

Show equivalence of different kinds of Turing Machines

Prove undecidability of computational problems

Classify decision problems into appropriate complexity classes, including P, NP, PSPACE and complexity classes based on randomized machine models and use this information effectively.

State precisely what it means to reduce one problem to another, and construct reductions for simple examples. Prove NPcompleteness, PSPACEcompleteness, and NLcompleteness results through reductions

Prove results that involve relativization and randomization

Classify optimisation problems into appropriate approximation complexity classes and use this information effectively.

Use the concept of interactive proofs in the analysis of optimisation problems.

Explain the notions of interactive proofs, lower bounds, cryptosystems, etc.