Introduction to the Theory of Computation 2023
Chih-Jen Lin, Room 413, CSIE building.
- TAs: Sheng-Wei Chen, He-Zhe Lin, Guan-Ting Chen, and Jie-Jyun Liu
- TA email: D09944003 AT ntu DOT edu DOT tw, R11922027 AT ntu DOT edu DOT tw
, R11922155 AT csie DOT ntu DOT edu DOT tw, and D11922012 AT ntu DOT edu DOT tw
- TA hour : (a) 2pm ~ 3pm Mon. (b) 1pm ~ 2pm Fri., Room 530, CSIE building.
Your HW and exam scores, with solutions to exams
- Time: Monday 10:20am to 1pm.
We will do two 10-minute breaks at around 11:10am and 12:10pm. The class
ends at 1pm.
Note: no class on October 23, 2023 (in UK for a conference; cannot run an online session due to the time difference
Note: we will do an online class on September 23.
- Place: Room 102, CSIE building
This course will be taught in English.
- Textbook: Michael Sipser,
Introduction to the Theory of Computation, third edition, Cengage Learning, 2012
We will mainly teach Chapters 1-4, part of Chapter 5, and part of Chapter 7.
FAQ of this course is here
We have pre-recorded all lectures and will broadcast them in the class.
In the class I will give additional comments while the video is being played.
- Automata and Languages
Mathematical models of computation
- Computability Theory
Problems CAN and CANNOT be solved by computers
- Complexity Theory
Why some problems are hard but some are easy?
Why taking this course?
From authors of the textbook
- Theoretical CS has some fancy/big ideas
- Relevant to practice (e.g., modern cryptography)
- Abstract way of thinking the computers. Help you
to design more beautiful ones
Chapter 0 (
Once every two weeks. Please write your homework/reports in English and do NOT submit lately. See
FAQ about how to submit your homework.
- HW1: Please see NTU COOL, due on 13:00, September 18th.
Weights of three exams will be decided at the end of
(Sample exam questions: 1,
- Midterm 1: October 2 (week 5)
- Midterm 2: November 13 (week 11)
- Final: December 18 (week 16)
For midterms, discussions will be in the following week.
30% homework, 70% Exam. (tentative)
Some (usually 10%) may fail if they don't work hard.