Introduction to the Theory of Computation
 Instructor:
ChihJen Lin, Room 413, CSIE building.
 TA (official ones): ChuanYao Su (r05922081 at ntu.edu.tw), HungYi Chou (s1243221 at gmail.com). TA hour:
Monday 14:0016:00 and Thursday 14:0016:00 in room 528
TA (undergraduate helper): HsinYuan Huang (momohuang at gmail.com), TA hour Wed. 10:0012:00 in B1 of CSIE or by email appointments
https://www.csie.ntu.edu.tw/~r05922081/comptheory2017/
 Time: Thursday 10:20am to 1pm.
We have a 20minute 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 20minute 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 14 and 7.

FAQ of this course is here
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?
Why you are forced to study this theoretical and maybe
boring topic?
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
Homework
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
homework.
 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.
Exams
Weights of three exams: ??, ??, ?? (to be decided in the end of
the semester).
 Midterm 1: Oct 19 (week 6)
 Midterm 2: Dec 7 (week 13)
 Final: Final: Jan 11 (week 18) Discussion: Jan 18, 12pm, room 104
(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.