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