ECS 120: Theory of Computation

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. 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.


Lecture 01 - Introduction to Finite-State Machines and Regular Languages
Lecture 02 - Regular Languages and Non-Deterministic FSMs
Lecture 03
Lecture 04 - Regular Expressions
Lecture 05 - Regular Expressions, Regular Languages and Non-Regular Languages
Lecture 06 - The Pumping Lemma and Introduction to CFLs
Lecture 07 - Context-Free Grammars and Push-Down Automata
Lecture 08 - Introduction to Turing Machines and Computations
Lecture 09 - More TM Design and Introduction to Non-Deterministic TMs
Lecture 10 - Equivalence of Non-Deterministic and Deterministic TMs
Lecture 11 - Church-Turing Thesis and Examples of Decidable Languages
Lecture 12 - Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable
Lecture 13 - Diagonalization, Countability and Uncountability
Lecture 14 - More Diagonalization; Proof that Turing Machines are Countable
Lecture 15 - Proof by Diagonalization that ATM (Halting Problem) is Not Decidable
Lecture 16 - Unrecognizable Languages and Reductions
Lecture 17 - Using Reductions to Prove Language Undecidable
Lecture 18 - More Complex Reductions
Lecture 19 - Uncomputable Functions, and Introduction to Complexity
Lecture 20 - P, NP and Polynomial-Time Reductions
Lecture 21 - NP-Completeness
Lecture 22 - A More Informal Introduction to NP-Completeness, Supplemental Lecture 1
Lecture 23 - NP-Completeness, Supplemental Lecture 2
Lecture 24 - NP-Completeness, Supplemental Lecture 3
Lecture 25 - Minimizing Finite State Machines
Lecture 26 - Minimizing the Number of States in a DFA