David Gusfield · Computer Science

Theory of Computation

UC Davis · 22 free video lectures

Free video course from David Gusfield, taught by UC Davis. Listed under Computer Science in Open Culture's directory of free online courses.

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. L1: Introduction to Finite-State Machines and Regular Languages
  2. L2: Regular Languages and Non-Deterministic FSMs
  3. L4: Regular Expressions
  4. L5: Regular Expressions, Regular Languages and Non-Regular Languages
  5. L6: The Pumping Lemma and Introduction to CFLs
  6. L7: Contex-Free Grammars and Push-Down Automata
  7. L8: Introduction to Turing Machines and Computations
  8. L9: More TM Design and Introduction to Non-Determinstic TMs
  9. L10: Equivalence of Non-Deterministic and Deterministic TMs
  10. L11: Church-Turing Thesis and Examples of Decidable Languages
  11. L12: Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable
  12. L13: Diagonalization, Countability and Uncountability
  13. L14: More Diagonalization; Proof that Turing Machines are Countable
  14. L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable
  15. L16: Unrecognizable Languages and Reductions
  16. L17: Using Reductions to Prove Language Undecidable
  17. L18: More Complex Reductions
  18. L19: Uncomputable Functions, and Introduction to Complexity
  19. L20: P, NP and Polynomial-Time Reductions
  20. L21: NP-Completeness
  21. L25: Minimizing Finite State Machines
  22. L26: Minimizing the Number of States in a DFA

From The original publisher (listed by Open Culture). More from David Gusfield.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights