
Instructor
 Name: Tony Tan
 Room: CSIE 516
 Office hour: By appointment via email
 Email: tonytan@csie.ntu.edu.tw
 Personal website
Venue and time
 Time: Monday, 10:2013:00
 There will be around 15 minute break in the middle of each lesson
 Room: CSIE 104
Teaching assistants
 Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Friday, 13:0014:00.
 Ma Yanger (b04902032@ntu.edu.tw), office hour: Wednesday, 13:0014:00.
 If needed, you may try to arrange another time slot with the TA directly.
Recommended textbooks
 Introduction to the Theory of Computation by M. Sipser.
 Introduction to Automata Theory, Languages, and Computation by J. Hopcroft and J. Ullman, 1st edition.
Schedule (tentative)
Part 
Week 
Dates 
Lesson 
Remark 
A 
I 
10 Sep. 
Lesson 1. Preliminaries 
 
B 
II 
17 Sep. 
Lesson 2. Deterministic finite state automata 
 
III 
24 Sep. 
Lesson 3. Nondeterministic finite state automata 
 
IV 
1 Oct. 
Lesson 4. Regular expressions 
 
C 
V 
8 Oct. 
Lesson 5. Contextfree languages 
 
VI 
15 Oct. 
Lesson 6. Pushdown automata 
HW 1 due. HW 2 out. 
VII 
22 Oct. 
Lesson 7. CFG = PDA 
 

VIII 
29 Oct. 
Reading week 
 
IX 
5 Nov. 
Midterm exam. 
HW 2 due. 
D 
X 
12 Nov. 
Lesson 8. Turing machines and decidable languages 
 
XI 
19 Nov. 
Lesson 9. Variants of Turing machines 
 
XII 
26 Nov. 
Lesson 10. Universal Turing machines and Halting problem 
 
XIII 
3 Dec. 
Lesson 11. Reducibility, part I 
HW 3 out. 
XIV 
10 Dec. 
Lesson 12. Reducibility, part II 
 
E 
XV 
17 Dec. 
Lesson 13. Time and space complexity 
 
XVI 
24 Dec. 
Lesson 14. NPcomplete and PSPACEcomplete languages 
 

XVII 
31 Dec. 
Reading week 
HW 3 due. 
XVIII 
7 Jan. 
Final exam. 
 
Notes on homeworks
 You should write down your class number, your student number and your name in your homework solution.
 Homeworks will be posted here on Mondays in the indicated week.
 Their due dates are also always on Mondays at the end of the class in the indicated week.
 You can submit your homework earlier than the due date by slipping it under the door of my office.
 Homework can be handwritten or typewritten. If it is handwritten, the writing must be legible.
 The tidiness of your homework contributes to your grade.
 Discussions/collaborations are allowed, but make sure that you acknowledge that you do your homeworks in collaboration and
that you understand and write down your own solutions.
 Points will be deducted if you don't understand your own solutions.
