|
|
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
- There will be around 15 minute break in the middle of each lesson
- Room: 104
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.
- 林廷衛 (Lin Tingwei), r08922089@csie.ntu.edu.tw, TA hour: Tuesday, 16:00-17:00, room 401.
- 呂佳軒 (Lu Chia-Hsuan), r09922064@ntu.edu.tw, r09922064@csie.ntu.edu.tw, TA hour: Tuesday, 11:00-12:00, room 401.
- 潘廣霖 (Pan Kuang-Lin), r08922087@csie.ntu.edu.tw, TA hour: Wednesday, 14:00-15:00, room 401.
- 陳法熏 (Chen Fahsun), b06902062@ntu.edu.tw, TA hour: Tuesday, 13:00-14:00, room 401.
- 周寬 (Chou Kuan), b06902085@ntu.edu.tw, TA hour: Friday, 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.
- Introduction to Automata Theory, Languages, and Computation by J. Hopcroft and J. Ullman, 1st edition.
- Chapter 1 in The Design and Analysis of Computer Algorithms by A. Aho, J. Hopcroft and J. Ullman.
Administrations
- All notes and homeworks (in both pdf and tex files) will be posted here.
- To compile the tex file, you will need this file: mysty.sty
- 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.
Schedule (tentative)
| Week |
Dates |
Lesson |
Remark |
|
| Part 0: Preliminaries
|
| I |
14 Sep. |
Lesson 0. Preliminaries |
-- |
|
| Part 1: Regular languages and context-free languages |
| II |
21 Sep. |
Lesson 1. Finite state automata |
-- |
| III |
28 Sep. |
Lesson 2. Pumping lemma and regular expressions |
-- |
| IV |
5 Oct. |
Lesson 3. Context-free grammars |
HW 1 |
| V |
12 Oct. |
Lesson 4. Push-down automata |
-- |
| VI |
19 Oct. |
Lesson 5. Equivalence between CFL and PDA |
-- |
| VII |
26 Oct. |
Review week with exercises |
HW 1 due. |
|
| Midterm exam |
| VIII |
2 Nov. |
Midterm exam: Monday, 19:00--21:00, room: 103 and 104. |
-- |
|
| Part 2: Turing machines and some basic complexity classes |
| IX |
9 Nov. |
Lesson 6. Turing machines and decidable languages |
-- |
| X |
16 Nov. |
Lesson 7. Turing machines and the notion of algorithm |
-- |
| XI |
23 Nov. |
Lesson 8. Universal Turing machines and halting problem |
-- |
| XII |
30 Nov. |
Lesson 9. Reducibility |
HW 2 |
| XIII |
7 Dec. |
Lesson 10. Non-deterministic Turing machines |
-- |
| XIV |
14 Dec. |
Lesson 11. Basic complexity classes |
-- |
| XV |
21 Dec. |
Lesson 12. NP-complete languages |
-- |
| XVI |
28 Dec. |
Review week |
HW 2 due. |
|
| Reading week and final exam |
| XVII |
4 Jan. |
Reading week |
-- |
| XVIII |
11 Jan. |
Final exam: Monday, 10:30--12:30, room: 103 and 104. |
-- |
|