Introduction to the Theory of Computation
 Instructor:
ChihJen Lin, Room 413, CSIE building.
 TAs:
 TA email: ?? AT ntu DOT edu DOT tw, ?? AT ntu DOT edu DOT tw
 TA hour : ??
Your HW and exam scores, with solutions to exams
 Time: Monday 10:20am to 1pm.
We will do two 10minute breaks at around 11:10am and 12:10pm. The class
ends at 1pm.
 Place:

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 14 and 7.

FAQ of this course is here

We have prerecorded 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

Chapter 0 (
part 1:
slides
video
)

Chapter 1

Chapter 2

Chapter 3

Chapter 4

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.
Exams
Weights of three exams will be decided at the end of
the semester.
 Midterm 1: October 3 (week 5)
 Midterm 2: November 14 (week 11)
 Final: Final: December 19 (week 16) Discussion: ??, room ??
(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: