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 were quite easy to understand by just going through the lecture notes.
The most interesting part of the course was the second half of the lectures. We dove into the theory of computation and complexity. The materials included Turing Machines, reductions, decidability, undecidability, NP-completeness, and space complexity. These were the essential knowledge for theoretical computer science so that all computer science students should at least have some basic understandings of them. However, these theoretical topics can get quite confusing sometimes in the sense that even if you study hard, you may not totally grasp the grand idea behind. So, try your best. At least for me, this course taught me about the limitations of not only computing models but also my brain.