News
- Dec 22: The final exam is over
- Nov 30: Assignment 6 is now posted
- Nov 15: Assignment 5 is now posted
- Nov 1: The midterm exam is over
- Nov 1: Assignment 4 is now posted
- Oct 18: The midterm exam will be postponed to Nov 1
- Oct 13: Class today is canceled due to Typhoon Kampasu
- Oct 11: Assignment 3 is now posted
- Sep 27: Assignment 2 is now posted
- Sep 13: Assignment 1 is now posted
- Sep 6: Live Zoom lectures are provided to mirror the actual lectures for students not in Hong Kong. See below for details.
Information
- Lectures
-
- Mon 4:30-6:15pm (ERB LT)
- Wed 5:30-6:15pm (ERB LT)
Live Zoom lectures: 996 9145 4382
(CUHK-authenticated Zoom account required) - Tutorials
-
- Tue 10:30-11:15am (LSK 210)
- Tue 11:30am-12:15pm (LSK LT1) (live Zoom 996 9145 4382)
- Tue 4:30-5:15pm (ELB 405)
- Tue 5:30-6:15pm (ELB 405)
- Instructor
- Siu On CHAN Office hours: Tue 3:30-5:30pm
- Teaching assistants
-
-
Shuqing LI
sqli21@cseSHB101A Mon 9:00-10:00 -
Jinyang LIU
jyliu@cseSHB101A Wed 10:00-11:00 -
Jiahui PAN
jhpan21@cseSHB902 Fri 2:30-3:30 -
Tianyu WANG
wangty@cseSHB902 Fri 3:30-4:30
-
- Prerequisites
- Discrete math CSCI2110 or ENGG2440
- Reference book
- Introduction to the Theory of Computation, Michael Sipser, 3rd ed
(older editions also work and are much cheaper) - Forum
- Please sign up on Piazza
- Grading
-
Homework (30%) Midterm exam (30%) Final exam (40%)
Lectures
| Date | Topic | Readings | Lectures | Tutorials | Homework | |
|---|---|---|---|---|---|---|
| 1 | Sep 6 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 8 | Nondeterministic finite automata | §1.2 | |||
| 3 | Sep 13 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2† | Asg 1 | |
| 4 | Sep 15 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 20 | Text search, closure properties | §1.1-1.3 | week 3‡ | ||
| Sep 22 | Holiday: Day after Mid-Autumn Festival | |||||
| 6 | Sep 27 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | week 4† | Asg 2 | |
| 7 | Sep 29 | DFA minimization, pumping lemma | §1.4 | |||
| 8 | Oct 4 | Context-free grammars | §2.1 | week 5‡ | ||
| 9 | Oct 6 | Parsing | §2.1, 7.2 | |||
| 10 | Oct 11 | Pushdown automata | §2.2 | week 6† | Asg 3 | |
| Oct 13 | Class canceled due to Typhoon Kampasu | |||||
| 11 | Oct 18 | PDA and CFG conversions | §2.3 | week 7‡ | ||
| 12 | Oct 20 | Pumping lemma for CFGs | §2.4 | |||
| 13 | Oct 25 | LR(0) parser | §2.4 | week 8† | ||
| 14 | Oct 27 | Church–Turing Thesis | §3.1 | |||
| Nov 1 | Midterm exam | no tutorial | Asg 4 | |||
| 15 | Nov 3 | Turing machines | §3.2, 3.3 | |||
| 16 | Nov 8 | Turing machines and their variants | §3.2, 3.3 | week 10‡ | ||
| 17 | Nov 10 | Decidability | §4.1, 4.2 | |||
| 18 | Nov 15 | Undecidability and reductions | §5.1 | week 11† | Asg 5 | |
| 19 | Nov 17 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 20 | Nov 22 | Efficient Turing machines | §7.1, 7.2 | week 12‡ | ||
| 21 | Nov 24 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 22 | Nov 29 | NP-completeness | §7.4, 7.5 | week 13† | Asg 6 | |
| 23 | Dec 1 | Cook–Levin theorem | §7.4, 7.5 |
Lecture recordings can be found at Piazza → Resources
† Morning sessions: Shuqing LI; Afternoon sessions: Jinyang LIU
‡ Morning sessions: Jiahui PAN; Afternoon sessions: Tianyu WANG
| Date | Topic | Readings | Lectures | Tutorials | Homework | |
|---|---|---|---|---|---|---|
| 1 | Sep 6 | Introduction, finite automata | §1.1 | no tutorial | ||
| 2 | Sep 8 | Nondeterministic finite automata | §1.2 | |||
| 3 | Sep 13 | NFA to DFA, regular expressions | §1.2, 1.3 | week 2 | Asg 1 | |
| 4 | Sep 15 | Equivalence of DFA and regular expressions | §1.2, 1.3 | |||
| 5 | Sep 20 | Text search, closure properties | §1.1-1.3 | week 3 | ||
| Sep 22 | Holiday: Day after Mid-Autumn Festival | |||||
| 6 | Sep 27 | Irregular languages (Myhill–Nerode theorem) | Exercise 1.48 | week 4 | Asg 2 | |
| 7 | Sep 29 | DFA minimization, pumping lemma | §1.4 | |||
| 8 | Oct 4 | Context-free grammars | §2.1 | week 5 | ||
| 9 | Oct 6 | Parsing | §2.1, 7.2 | |||
| 10 | Oct 11 | Pushdown automata | §2.2 | week 6 | Asg 3 | |
| 11 | Oct 13 | PDA and CFG conversions | §2.3 | |||
| 12 | Oct 18 | Pumping lemma for CFGs | §2.4 | week 7 | ||
| 13 | Oct 20 | LR(0) parser | §2.4 | |||
| Midterm exam (Postponed to Nov 1) | no tutorial | |||||
| 14 | Oct 27 | Church–Turing Thesis | §3.1 | |||
| 15 | Nov 1 | Turing machines and their variants | §3.2, 3.3 | week 9 | Asg 4 | |
| 16 | Nov 3 | Decidability | §4.1, 4.2 | |||
| 17 | Nov 8 | Undecidability and reductions | §5.1 | week 10 | ||
| 18 | Nov 10 | Undecidable problems for CFGs | §5.1, 5.2 | |||
| 19 | Nov 15 | Efficient Turing machines | §7.1, 7.2 | week 11 | Asg 5 | |
| 20 | Nov 17 | Nondeterministic polynomial time | §7.3, 7.4 | |||
| 21 | Nov 22 | NP-completeness | §7.4, 7.5 | week 12 | ||
| 22 | Nov 24 | Cook–Levin theorem | §7.4, 7.5 | |||
| 23 | Nov 29 | Space complexity | §8.1, 8.5, 9.1 | week 13 | Asg 6 | |
| 24 | Dec 1 | Zero knowledge proofs | §10.4 |
Tutorials
Tutorial solutions and videos can be found at Piazza → Resources after Tue tutorial sessions
Homework
Homework assignments are typically posted on Mondays every other week and due on Thursdays the following week
Submit your solution as a single PDF file via Blackboard by 11:59pm on Thursday
If you typeset your solution, Graphviz or LaTeX TikZ may help you draw automata: Example 1 and Example 2
Your lowest homework grade (out of 6 assignments) will be dropped
Collaboration on homework is encouraged, but you must write up your own solutions, and list your collaborators on the solution sheet
Homework solutions can be found on Piazza
- Assignment 1 due Thu Sep 23
- Assignment 2 due Thu Oct 7 (Updated on Oct 4: Fix the clarification for Q4(b))
- Assignment 3 due Thu Oct 21
- Assignment 4 due Thu Nov 11
- Assignment 5 due Thu Nov 25
- Assignment 6 due Thu Dec 9