|
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:10-12:00
- Class 01: Thursday, 09:10-12: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 (2016a-aut-admin.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/2017a-aut/2017a-aut.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. Context-free languages
|
-- |
VI |
18 and 20 Oct. |
Lesson 6. Pumping lemma and push-down 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. NP-complete 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.
|