Courses:

Automata, Computability, and Complexity >> Content Detail



Calendar / Schedule



Calendar

The calendar below provides information on the course's lecture (L), recitation (R) sessions and quizzes.


SES #TOPICSKEY DATES
Introduction and Review
L1IntroductionHomework 1 out
R1Math Review
Finite Automata, Regular Languages, Regular Expressions
L2Deterministic Finite Automata (DFA)
L3Nondeterministic Finite Automata (NFA)Homework 1 due

Homework 2 out
R2DFAs and NFAs
L4Regular Expressions
L5Non-Regular LanguagesHomework 2 due

Practice homework 2.5 out
R3Regular Expressions and Non-Regular Languages
L6Algorithms for Automata
L7Quiz 1Homework 3 out
R4Quiz Questions and Automata Wrap-up
Computability Theory
L8Turing Machines
L9Nondeterministic Turing MachinesHomework 3 due

Homework 4 out
R5Turing Machines
L10Undecidability
L11PCPHomework 4 due

Homework 5 out
R6Undecidability
L12Counter and Stack Machines
L13ReducibilityHomework 5 due

Practice homework 5.5 out
R7Counter and Stack Machines, Reducibility, Rice's Theorem
L14Recursion Theorem
L15Quiz 2Homework 6 out
R8Quiz 2 Questions and Computability Wrap-up
Complexity Theory
L16Time Complexity
L17Nondeterministic Time ComplexityHomework 6 due

Homework 7 out
R9P and NP
L18NP-Completeness
L19Cook-Levin TheoremHomework 7 due

Homework 8 out
R10Poly-Time Reductions
L20NP-Completeness IIHomework 8 due

Practice homework 8.5 out
R11NP-Completeness
L21Advanced Time Complexity
L22Quiz 3Homework 9 out
R12Quiz 3 Questions and End of Time Complexity
L23Space Complexity
L24Space Complexity IIHomework 9 due

Practice homework 10 out
R13Space Complexity III
L25Probabilistic Complexity
L26Probabilistic Complexity (cont.)Practice homework 10.5 out
R14Probabilistic Complexity and Interactive Proofs
Final Exam Review Session (Optional)
Final Exam

 








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