
Instructor
 Name: Tony Tan
 Room: CSIE 516
 Office hour: By appointment via email
 Email: tonytan@csie.ntu.edu.tw
 Personal website
Venue and time
 Class 02: Tuesday, 09:1012:00
 Class 01: Thursday, 09:1012: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.
 This document (2016aautadmin.pdf)
contains more information about the course.
 If you want to send me email, please use: tonytan@csie.ntu.edu.tw
 Notes and homework can be found in the latest website:
https://www.csie.ntu.edu.tw/~tonytan/teaching/2017aaut/2017aaut.html
Schedule (tentative)
Part 
Week 
Dates 
Lesson 
Remark 
A 
I 
13 and 15 Sep. 
Lesson 1. Preliminaries 
HW 1 out. 
B 
II 
22 Sep. 
Lesson 2. Deterministic finite state automata 
HW 1 due. 
III 
27 and 29 Sep. 
Lesson 3.
Nondeterministic finite state automata 
HW 2 out. 
IV 
4 and 6 Oct. 
Lesson 4. Regular expressions

 
C 
V 
11 and 13 Oct. 
Lesson 5. Contextfree languages

 
VI 
18 and 20 Oct. 
Lesson 6. Pumping lemma and pushdown automata

HW 2 due. HW 3 out. 
VII 
25 and 27 Oct. 
Lesson 7. CFG = PDA

 

VIII 
1 and 3 Nov. 
Reading week 
HW 3 due. 
IX 
8 Nov. 
Midterm exam 
 
D 
X 
15 and 17 Nov. 
Lesson 8. Turing machines and decidable languages 
 
XI 
22 and 24 Nov. 
Lesson 9. Variants of Turing machines 
HW 4 out. 
XII 
29 Nov. and 1 Dec. 
Note: There is no lecture this week due to
an overseas assignment from the EECS College. 
 
XIII 
6 and 8 Dec. 
Lesson 10. Universal Turing machines and Halting problem 
 
XIV 
13 and 15 Dec. 
Lesson 11. Reducibility 
 
E 
XV 
20 and 22 Dec. 
Lesson 12. Time and space complexity 
HW 4 due. HW 5 out. 
XVI 
27 and 29 Dec. 
Lesson 13. NPcomplete problems 
 

XVII 
3 and 5 Jan. 
Reading week 
HW 5 due. 
XVIII 
10 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 at 17:00 in the indicated week.
 Their due dates are also always on Mondays at 17:00 in the indicated week,
except Homeworks 3 and 5 which are due on Friday, 17:00, respectively.
 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.
