
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: Thursday, 10:2013:00
 There will be around 15 minute break in the middle of each lesson
 Room: CSIE 102
Administration
 Please check this website regularly.
 All the course notes and homework will be posted here.
 All the announcements will also be posted here, as well as in the bulletin of this course in CEIBA.
 If you want to send me email, please use: tonytan@csie.ntu.edu.tw
Teaching assistants
 Li Yu Sheng (b03902086@ntu.edu.tw), office hour: Monday, 1:102:10, red sofa in basement.
 Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Thursday, 1:303:00, red sofa in basement.
 If needed, you may try to arrange another time slot with the TA directly.
Schedule (tentative)
Part 
Week 
Dates 
Lesson 
Remark 
A 
I 
14 Sep. 
Lesson 1. Preliminaries 
 
B 
II 
21 Sep. 
Lesson 2. Deterministic finite state automata 
 
III 
28 Sep. 
Lesson 3. Nondeterministic finite state automata 
HW 1 out. 
IV 
5 Oct. 
Lesson 4. Regular expressions 
 
C 
V 
12 Oct. 
Lesson 5. Contextfree languages 
 
VI 
19 Oct. 
Lesson 6. Pumping lemma and pushdown automata 
HW 1 due. HW 2 out. 
VII 
26 Oct. 
Lesson 7. CFG = PDA 
 

VIII 
2 Nov. 
Reading week 
 
IX 
9 Nov. 
Midterm exam 
HW 2 due. 
D 
X 
16 Nov. 
Lesson 8. Turing machines and decidable languages 
 
XI 
23 Nov. 
Lesson 9. Variants of Turing machines 
 
XII 
30 Nov. 
Lesson 10. Universal Turing machines and Halting problem 
HW 3 out. 
XIII 
7 Dec. 
Lesson 11. Reducibility 
 
E 
XIV 
14 Dec. 
Lesson 12. Time and space complexity 
 
XV 
21 Dec. 
Lesson 13. NPcomplete problems 
 
XVI 
28 Dec. 
Lesson 14. NLog and PSPACEcomplete problems 
HW 3 due. HW 4 out. 

XVII 
4 Jan. 
Reading week 
 
XVIII 
11 Jan. 
Final exam 
HW 4 due. 
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 Thurdays in the indicated week.
 Their due dates are also always on Thursdays at the end of the class in the indicated week.
 You can submit your homework earlier than usualthe 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.
