Courses:

Theory of Computation >> Content Detail



Calendar / Schedule



Calendar

SES #TOPICSKEY DATES
1Introduction, Finite Automata, Regular Expressions
2Nondeterminism, Closure Properties, Regular Expressions ↔ FA
3Regular Pumping Lemma, Context Free Languages
4Pushdown Automata, CFG ↔ PDA
5CF Pumping Lemma, Turing MachinesHomework 1 due
6TM Variants, Church-Turing Thesis
7Decision Problems for Automata and Grammars
8Undecidability
9ReducibilityHomework 2 due
10Linearly Bounded Automata, PCP
11Recursion Theorem and Logic
12Time ComplexityHomework 3 due
13Midterm Exam
14P and NP, SAT, Poly-time Reducibility
15NP-Completeness
16Cook-Levin TheoremHomework 4 due
17Space Complexity
18PSPACE, TQBF, Savitch's Theorem
19Games, Generalized Geography
20L and NL, NL= coNLHomework 5 due
21Hierarchy Theorems
22Provably Intractable Problems, Oracles
23Probabilistic Computation, BPP
24Probabilistic Computation (cont.)
25Interactive Proof Systems, IPHomework 6 due
26Topic
27Final Exam

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.