Created by:

Profile Photo

Last updated:

September 25, 2023


Unlimited Duration


This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration


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.

Course Curriculum

  • 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

About the instructor

5 5

Instructor Rating







Profile Photo
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.