1
ECS 120: Theory of Computation (Fall 2011, UC Davis). Instructor: Professor Dan Gusfield. This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser.
694 years, 4 months
25
The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines. There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's theorem that NP-complete problems exist. In addition to these major results, and other results, a central goal of the course is to increase student's skill level in understanding and writing rigorous mathematical proofs.
Course Currilcum
- Lecture 01 – Introduction to Finite-State Machines and Regular Languages Unlimited
- Lecture 02 – Regular Languages and Non-Deterministic FSMs Unlimited
- Lecture 04 – Regular Expressions Unlimited
- Lecture 05 – Regular Expressions, Regular Languages and Non-Regular Languages Unlimited
- Lecture 06 – The Pumping Lemma and Introduction to CFLs Unlimited
- Lecture 07 – Context-Free Grammars and Push-Down Automata Unlimited
- Lecture 08 – Introduction to Turing Machines and Computations Unlimited
- Lecture 09 – More TM Design and Introduction to Non-Deterministic TMs Unlimited
- Lecture 10 – Equivalence of Non-Deterministic and Deterministic TMs Unlimited
- Lecture 11 – Church-Turing Thesis and Examples of Decidable Languages Unlimited
- Lecture 12 – Universal Turing Machines; The Halting Problem is Recognizable but … Unlimited
- Lecture 13 – Diagonalization, Countability and Uncountability Unlimited
- Lecture 14 – More Diagonalization; Proof that Turing Machines are Countable Unlimited
- Lecture 15 – Proof by Diagonalization that ATM (Halting Problem) is Not Decidable Unlimited
- Lecture 16 – Unrecognizable Languages and Reductions Unlimited
- Lecture 17 – Using Reductions to Prove Language Undecidable Unlimited
- Lecture 18 – More Complex Reductions Unlimited
- Lecture 19 – Uncomputable Functions, and Introduction to Complexity Unlimited
- Lecture 20 – P, NP and Polynomial-Time Reductions Unlimited
- Lecture 21 – NP-Completeness Unlimited
- Lecture 22 – A More Informal Introduction to NP-Completeness, Supplemental Lecture 1 Unlimited
- Lecture 23 – NP-Completeness, Supplemental Lecture 2 Unlimited
- Lecture 24 – NP-Completeness, Supplemental Lecture 3 Unlimited
- Lecture 25 – Minimizing Finite State Machines Unlimited
- Lecture 26 – Minimizing the Number of States in a DFA Unlimited
