|
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: CSIE 104
Teaching assistants
- Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Friday, 13:00--14:00.
- Ma Yanger (b04902032@ntu.edu.tw), office hour: Wednesday, 13:00--14:00.
- 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.
Schedule (tentative)
Part |
Week |
Dates |
Lesson |
Remark |
A |
I |
10 Sep. |
Lesson 1. Preliminaries |
-- |
B |
II |
17 Sep. |
Lesson 2. Deterministic finite state automata |
-- |
III |
24 Sep. |
Lesson 3. Nondeterministic finite state automata |
-- |
IV |
1 Oct. |
Lesson 4. Regular expressions |
-- |
C |
V |
8 Oct. |
Lesson 5. Context-free languages |
-- |
VI |
15 Oct. |
Lesson 6. Push-down automata |
HW 1 due. HW 2 out. |
VII |
22 Oct. |
Lesson 7. CFG = PDA |
-- |
|
VIII |
29 Oct. |
Reading week |
-- |
IX |
5 Nov. |
Midterm exam. |
HW 2 due. |
D |
X |
12 Nov. |
Lesson 8. Turing machines and decidable languages |
-- |
XI |
19 Nov. |
Lesson 9. Variants of Turing machines |
-- |
XII |
26 Nov. |
Lesson 10. Universal Turing machines and Halting problem |
-- |
XIII |
3 Dec. |
Lesson 11. Reducibility, part I |
HW 3 out. |
XIV |
10 Dec. |
Lesson 12. Reducibility, part II |
-- |
E |
XV |
17 Dec. |
Lesson 13. Time and space complexity |
-- |
XVI |
24 Dec. |
Lesson 14. NP-complete and PSPACE-complete languages |
-- |
|
XVII |
31 Dec. |
Reading week |
HW 3 due. |
XVIII |
7 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 in the indicated week.
- Their due dates are also always on Mondays at the end of the class in the indicated week.
- 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.
|