Term Taken: 2019 Fall

Instructor: Prof. Chan Siu On

# Grading Scheme

**Original Scheme:**

- Homework (30%)
- Midterm Exam (30%)
- Final Exam (40%)

**Scheme for 2019 Course Cancellation:**

- Homework (50%)
- Midterm Exam (50%)

# Textbook

Introduction to the Theory of Computation, Michael Sipser, 3rd ed

# Topics Covered

- Finite Automata (DFA, NFA).
- Regular Expressions.
- Context-Free Grammar.
- Pushdown Automata.
- Pumping Lemma.
- LR(0) Parser.
- Church-Turing Thesis.
- Reductions.
- Decidability and Undecidability.
- NP-completeness.
- Cook-Levin Theorem.
- Space Complexity.
- Zero Knowledge Proofs.

# Review

In my opinion, this subject along with algorithms are the core of computer science. In the first half of the lectures, Prof. Chan went through some basic automaton models and formal languages such as DFA, NFA, Regular Language, CFG, PDA. These materials are easy to understand if you make some effort.

The most interesting part of the course is the second half of the lectures. It dives into the theory of computation and complexity. The materials include Turing Machines, reductions, decidability, undecidability, NP-completeness, and space complexity. These are essential knowledge for theoretical computer science and all computer science students should at least have some basic understanding of those topics. However, these theoretical topics can get quite confusing sometimes, even if you study hard, you may not totally grasp the idea behind the logic. So, try your best.

Prof. Chan is extremely clever and knowledgeable on theoretical computer science subjects. He is willing to help every student, and welcome everyone to visit his office to ask questions. I highly recommend this course for all computer science related majors and those who enjoy logical reasoning.