Fall 2026 · CUHK-Shenzhen · 3 units
CSC 6011: Theory of Computation
Course overview
What are the fundamental capabilities and limitations of computers? This course introduces the foundations of computability and computational complexity, and how to classify computational problems by the resources needed to solve them.
We begin with automata and formal languages, then study Turing machines, decidability, and reductions. Complexity topics include P versus NP, NP-completeness, time and space complexity, randomized computation, interactive proofs, and hardness of approximation. The course also covers communication complexity and connections between Transformers and EXPSPACE-completeness.
Prerequisites: No formal prerequisites. Students should be comfortable with mathematical reasoning, proofs, and basic discrete mathematics.
Class information
- Lectures: Monday and Wednesday, 4:00–5:20 PM, Teaching A, Room 107.
- Instructor: Tao Lin (林涛), lintao@cuhk.edu.cn.
- Office hour: Thursday, 5:00–6:00 PM, Daoyuan Building (道远楼), Room 420c.
- Teaching assistant: Yefan Gao (高叶繁), 226040008@link.cuhk.edu.cn.
- Office hour: Friday, 10:00–11:00 AM, Zhixin Building (知新楼), Room 410.
Syllabus and slides
The dated teaching plan below follows the updated course syllabus. All dates are in 2026. The schedule is subject to adjustment. Further slides will be added as they become available.
Midterm update: The midterm is scheduled for November 9, 2026 (Week 9).
| Week | Dates | Topics | Slides |
|---|---|---|---|
| 1 | Sep 7, 9 | Introduction. Finite automata (DFA and NFA). Regular languages. | Lecture 1 (PDF) Lecture 2 (PDF) |
| 2 | Sep 14, 16 | Nonregular languages, pumping lemma. Context-free languages, pushdown automata. | Lecture 3 (PDF) Lecture 4 (PDF) |
| 3 | Sep 21, 23 | Turing machines, Church–Turing thesis. | Lecture 5 (PDF) Lecture 6 (PDF) |
| 4 | Sep 28, 29 | Decidability, diagonalization. Reduction. | Not yet posted |
| — | Oct 5, 7 | National Day holiday — no classes. | — |
| 5 | Oct 12, 14 | Time complexity. | Not yet posted |
| 6 | Oct 19, 21 | P and NP, NP-completeness. | Not yet posted |
| 7 | Oct 26, 28 | Cook–Levin theorem. | Not yet posted |
| 8 | Nov 2, 4 | Space complexity, PSPACE, L, NL, Savitch’s theorem. | Not yet posted |
| 9 | Nov 9, 11 | Midterm exam: Nov 9. More on space complexity. | Not yet posted |
| 10 | Nov 16, 18 | Formal language and modern AI models: [ICLR’26 oustanding paper “Transformers are Inherently Succinct”] |
Not yet posted |
| 11 | Nov 23, 25 | Randomized computation, RP, BPP. | Not yet posted |
| 12 | Nov 30, Dec 2 | Interactive proofs, IP = PSPACE. | Not yet posted |
| 13 | Dec 7, 9 | Approximation algorithms, hardness of approximation, PCP theorem. | Not yet posted |
| 14 | Dec 14, 16 | Communication complexity. | Not yet posted |
Learning outcomes
By the end of the course, students will be able to:
- Formalize problems using standard models of computation, analyze their capabilities and limitations, and prove results about decidability, reducibility, and complexity.
- Classify problems into major complexity classes and construct rigorous reductions and impossibility arguments.
- Apply theoretical computer science concepts to the analysis of algorithms and data science problems.
Assessment
| Component | Weight |
|---|---|
| Homework | 30% |
| Midterm exam (Nov 9, Week 9) | 30% |
| Final exam | 40% |
Exams: The midterm and final are open-book. Text materials are allowed; digital devices and AI tools are not. Students must complete exams independently.
Homework and AI: AI tools may be used, but students must write their own solutions and explain how they used AI. Direct submission of AI output is not allowed.
Reading
There is no required textbook. Recommended references are:
- Michael Sipser, Introduction to the Theory of Computation, 3rd edition. Cengage Learning.
- John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation. Pearson.
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. Cambridge University Press.
- Eyal Kushilevitz and Noam Nisan, Communication Complexity. Cambridge University Press.