Introduction to the Theory of Computation 2024
- Instructor:
Chih-Jen Lin, Room 413, CSIE building.
- TAs: Sheng-Wei Chen, Zhi-Bao Lu, Jie-Jyun Liu, Zih-Syuan Huang, and Hung-Chih Chiang
- TA email: D09944003 AT ntu DOT edu DOT tw, R12922196 AT ntu DOT edu DOT tw, D11922012 AT ntu DOT edu DOT tw,
R11922210 AT ntu DOT edu DOT tw, and R13922189 AT ntu DOT edu DOT tw
- TA hour : (a) 3pm ~ 4pm Tue. (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.
No course on Oct. 14 (attending a conference). We make it up by slightly reducing the break time
- 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.
Course Outline
- 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
Slides are based on contents in the textbook though we add some extra materials.
-
Chapter 0 (
part 1:
slides
video
)
-
Chapter 1
-
Chapter 2
-
Chapter 3
-
Chapter 4
-
Chapter 5
-
Chapter 7
Homework
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 16th.
- HW2: Please see NTU COOL, due on 23:59, September 30th.
- HW3: Please see NTU COOL, due on 13:00, October 14th.
- HW4: Please see NTU COOL, due on 13:00, November 4th.
Exams
Weights of three exams will be decided at the end of
the semester.
- Midterm 1: September 30 (week 5)
- Midterm 2: November 11 (week 11)
- Final: December 16 (week 16)
(Sample exam questions: 1,
2,
3)
For midterms, discussions will be in the following week.
Grading
30% homework, 70% Exam. (tentative)
Some (usually 10%) may fail if they don't work hard.
Last modified: