|
|
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:20-13:00
- Room: Online (see the announcement on 25 Sept. in NTU COOL for the details)
Teaching assistants
- TA mailing list: automata@csie.ntu.edu.tw.
- If there is an issue that does not need a specific TA to settle, please write to TA mailing list above.
- 呂佳軒 (Lu Chia-Hsuan), r09922064@ntu.edu.tw, r09922064@csie.ntu.edu.tw, TA hour: Friday, 16:00-17:00, room: 401.
- 呂侑承 (Lu Yu-Cheng), r10922030@ntu.edu.tw, r10922030@csie.ntu.edu.tw, TA hour: Friday, 13:20--14:10, room: 401.
- 陳翰霆 (Chen Han-Ting), r10922073@ntu.edu.tw, r10922073@csie.ntu.edu.tw, TA hour: Wednesday, 14:00-15:00, room: 401.
- 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.
Administrations
- All notes and homeworks (in both pdf and tex files) will be posted here.
- There will be two homeworks, each weighs 20%.
- Midterm and final exams weigh 30% each.
- The instructions on homework submissions will be provided in each homework.
- The pre-recorded lectures will posted in NTU COOL.
Schedule (tentative)
| Week |
Dates |
Lesson |
Remark |
|
| Part 0: Preliminaries
|
| I |
27 Sep. |
Lesson 0. Preliminaries (slide-00.pdf) |
-- |
|
| Part 1: Regular languages and context-free languages |
| II |
4 Oct. |
Lesson 1. Finite state automata (slide-01.pdf) |
-- |
| III |
11 Oct. |
Holiday (National day) |
-- |
| IV |
18 Oct. |
Lesson 2. Regular expressions (slide-02.pdf) |
--
|
| V |
25 Oct. |
Lesson 3. Context-free languages (slide-03.pdf) |
-- |
| VI |
1 Nov. |
Lesson 4. Push-down automata (slide-04.pdf) |
-- |
|
| Reading week and midterm exam |
| VII |
8 Nov. |
Reading week |
-- |
| VIII |
15 Nov. |
Midterm exam: Monday, 10:30-13:00, online. It will be posted in NTU COOL. |
HW 1 due on 14 Nov. |
|
| Part 2: Turing machines and some basic complexity classes |
| IX |
22 Nov. |
Lesson 5. Turing machines and decidable languages (slide-05.pdf) |
-- |
| X |
29 Nov. |
Lesson 6. Turing machines and the notion of algorithm (slide-06.pdf) |
-- |
| XI |
6 Dec. |
Lesson 7. Universal Turing machines and the halting problem (slide-07.pdf) |
-- |
| XII |
13 Dec. |
Lesson 8. Reducibility (slide-08.pdf) |
-- |
| XIII |
20 Dec. |
Lesson 9. Non-deterministic Turing machines (slide-09.pdf) |
-- |
| XIV |
27 Dec. |
Lesson 10. Basic complexity classes (slide-10.pdf) |
-- |
|
| Reading week and final exam |
| XV |
3 Jan. |
Reading week |
-- |
| XVI |
10 Jan. |
Final exam: Monday, 10:30--12:30, room: 103 and 104. |
-- |
|