Here is the rough coverage plan.
Brief review: of Regular Languages, DFA. Nondetermism, NFA
Minimization, Myhill-Nerode theorem.Computability: Turing Machines, Enumeration of Turing Machines, Undecidability. Rice-Myhill-Shapiro theorem.
Resource bounded computation. Notion of a computational resource. Tape reduction, Speedup theorems.Time Complexity: Crossing Sequences and their applications. Hierarchy theorems. P vs NP. Time Complexity classes and their relationships. Notion of completeness, reductions. Cook-Levin Theorem.
Space Complexity: Space as a resource. Savitch's theorem, Inductive Counting. PSPACE, L and NL.
Last updated on Sat Nov 26 13:32:00 IST 2011