|
|
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: Tuesday and Friday, 10:20-13:00
- There will be around 15 minute break in the middle of each lesson
- Room: CSIE 104 (class 2) and CSIE 102 (class 1)
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.
- 鄭士驤 (Cheng Shih Hsiang), r08922047@ntu.edu.tw, r08922047@csie.ntu.edu.tw, TA hour: Wednesday, 13:00-14:00, room 217.
- 林廷衛 (Lin Tingwei), r08922089@ntu.edu.tw, r08922089@csie.ntu.edu.tw, TA hour: Monday, 16:00-17:00, room 401.
- 黃世瑋 (Huang Shiwei), r07944035@ntu.edu.tw, r07944035@csie.ntu.edu.tw, TA hour: Wednesday, 16:00-17: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.
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 four homeworks, each weighs 10%.
- 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 |
10 and 13 Sep. |
Lesson 0. Preliminaries |
-- |
|
| Part 1: Regular languages |
| II |
17 and 20 Sep. |
Lesson 1.a. Finite state automata |
-- |
| III |
24 and 27 Sep. |
Lesson 1.b. Pumping lemma and regular expressions |
-- |
| IV |
1 and 4 Oct. |
Lesson 1.c. Review |
-- |
|
| Part 2: Context-free languages |
| V |
8 and 11 Oct. |
Lesson 2.a. Context-free grammars and pumping lemma |
-- |
| VI |
15 and 18 Oct. |
Lesson 2.b. Push-down automata |
-- |
| VII |
22 and 25 Oct. |
Lesson 2.b. Push-down automata |
-- |
| VIII |
29 Oct. and 1 Nov. |
Lesson 2.c. Review |
-- |
|
| Reading week and midterm exam |
| IX |
5 and 8 Nov. |
Reading week |
-- |
| X |
12 Nov. |
Midterm exam: Tuesday, 12 November, 18:30--20:30, room: 101, 102, 103, 104. |
-- |
|
| Part 3: Decidable and undecidable languages |
| XI |
19 and 22 Nov. |
Lesson 3.a. Turing machines and decidable languages |
-- |
| XII |
26 and 29 Nov. |
Lesson 3.b. Variants of Turing machines |
-- |
| XIII |
3 and 6 Dec. |
Lesson 3.c. Universal Turing machines and halting problems |
-- |
| XIV |
10 and 13 Dec. |
Lesson 3.d. Reducibility |
-- |
|
| Part 4: Basic complexity theory |
| XV |
17 and 20 Dec. |
Lesson 4.a. Basic complexity classes |
-- |
| XVI |
24 and 27 Dec. |
Lesson 4.b. NP-complete languages |
-- |
|
| Reading week and final exam |
| XVII |
31 Dec. and 3 Jan. |
Reading week |
-- |
| XVIII |
7 Jan. |
Final exam: Tuesday, 7 January, 19:00--21:00, room: 101, 102, 103, 104. |
-- |
|