Introduction to the Theory of Computation
Chih-Jen Lin, Room 413, CSIE building.
- TA (official ones): Chuan-Yao Su (r05922081 at ntu.edu.tw), Hung-Yi Chou (s1243221 at gmail.com). TA hour:
Monday 14:00-16:00 and Thursday 14:00-16:00 in room 528
TA (undergraduate helper): Hsin-Yuan Huang (momohuang at gmail.com), TA hour Wed. 10:00-12:00 in B1 of CSIE or by email appointments
- Time: Thursday 10:20am to 1pm.
We have a 20-minute break at around 11:30am. So the class
will end at 1pm (rather than the 1:10pm).
No course on Nov 9 and Nov 16 (out of the country). To make it up, we will reduce the 20-minute break to 10 minutes
Place: room 104
This course will be taught in English.
You are assumed to take notes.
- Textbook: Michael Sipser,
Introduction to the Theory of Computation, third edition, Cengage Learning, 2012
We will mainly teach Chapters 1-4 and 7.
FAQ of this course is here
- 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?
Why you are forced to study this theoretical and maybe
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
Once every two weeks. Please write your homework/reports in English.
For late homework, the score will be exponentially decreased. See
FAQ about how to submit your
- HW1: 0.13, 1.3, 1.4f, due on September 28. (problem description as you may not have the book yet)
- HW2: 1.10b, 1.16b, 1.21b, due on October 12.
- HW3: 1.29b, 1.46c, 1.62, due on October 26.
- HW4: 2.1(d), 2.9, 2.10, due on November 23.
- HW5: 2.47, 3.1(c), 3.12, due on December 7.
- HW6: 3.21, 4.13, 4.21, due on December 28.
- HW7: 7.1(e), 7.2(b), 7.9, due on January 11.
Weights of three exams: ??, ??, ?? (to be decided in the end of
(Sample exam questions: 1,
- Midterm 1: Oct 19 (week 6)
- Midterm 2: Dec 7 (week 13)
- Final: Final: Jan 11 (week 18) Discussion: Jan 18, 12pm, room 104
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.