Theory of Computation (Automata, Computability, and Complexity)

IMPORTANT MESSAGES:

  • We are back to classroom teaching/learning, although part of the lectures will still be provided remotely
  • Each week, slides and/or videos will be uploaded
  • Grading will be based on three (3) quiz and one (1) final exam

Learning Objectives:

  • Study mathematical models of computation: automata, Turing machines;
  • learn the limit of computation: computability theory;
  • analyze the efficiency of computation: complexity theory.

Instructor:

  • Prof. Kai Cai (Engineering Building F-610)
  • Email: [email protected]
  • Office hour: anytime appointment by email

Lecture Schedule:

  • Period: Sep. 2022 -- Feb. 2023
  • Day and Time: Tuesdays 15:00-16:30

Textbook / Reference:

There is no textbook. Lecture notes will cover all contents. Two excellent references are:

  1. M. Sipser, "Introduction to the Theory of Computation", Course Technology, 2013. (Available in our library; there is Japanese translation for this book.)
  2. J.E. Hopcroft, R. Motwani, J.D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison Wesley, 2006. (Available in our library)

Prerequisites:

None

Course Outline:

    Dates              Topics
  1. 2022.09.27 Introduction, finite automata
  2. 2022.10.04 Strings, languages
  3. 2022.10.11 Nondeterministic finite automata
  4. 2022.10.18 Regular operations, regular expressions
  5. 2022.10.25 Tutorial 1
  6. 2022.11.08 Quiz 1, nonregular languages, pumping lemma
  7. 2022.11.15 Context-free grammars, context-free languages, pushdown automata
  8. 2022.11.22 Non-context-free languages, pumping lemma
  9. 2022.11.29 Turing machines
  10. 2022.12.06 Turing-recognizable languages, Turing-decidable languages, variants of Turing machines
  11. 2022.12.13 Tutorial 2
  12. 2022.12.20 Quiz 2, Algorithms, decidable problems, undecidability
  13. 2023.01.10 Time complexity, P and NP
  14. 2023.01.17 Tutorial 3
  15. 2023.01.24 Quiz 3, NP completeness
  16. 2023.01.31 Exam, NP complete languages