|
|
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: Thursday, 10:20-13: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.
- If you want to send me email, please use: tonytan@csie.ntu.edu.tw
Teaching assistants
- Li Yu Sheng (b03902086@ntu.edu.tw), office hour: Monday, 1:10--2:10, red sofa in basement.
- Liu Han Sheng (b04902012@ntu.edu.tw), office hour: Thursday, 1:30--3:00, red sofa in basement.
- If needed, you may try to arrange another time slot with the TA directly.
Schedule (tentative)
| Part |
Week |
Dates |
Lesson |
Remark |
|
| A |
I |
14 Sep. |
Lesson 1. Preliminaries |
-- |
|
| B |
II |
21 Sep. |
Lesson 2. Deterministic finite state automata |
-- |
| III |
28 Sep. |
Lesson 3. Nondeterministic finite state automata |
HW 1 out. |
| IV |
5 Oct. |
Lesson 4. Regular expressions |
-- |
|
| C |
V |
12 Oct. |
Lesson 5. Context-free languages |
-- |
| VI |
19 Oct. |
Lesson 6. Pumping lemma and push-down automata |
HW 1 due. HW 2 out. |
| VII |
26 Oct. |
Lesson 7. CFG = PDA |
-- |
|
|
VIII |
2 Nov. |
Reading week |
-- |
| IX |
9 Nov. |
Midterm exam |
HW 2 due. |
|
| D |
X |
16 Nov. |
Lesson 8. Turing machines and decidable languages |
-- |
| XI |
23 Nov. |
Lesson 9. Variants of Turing machines |
-- |
| XII |
30 Nov. |
Lesson 10. Universal Turing machines and Halting problem |
HW 3 out. |
| XIII |
7 Dec. |
Lesson 11. Reducibility |
-- |
|
| E |
XIV |
14 Dec. |
Lesson 12. Time and space complexity |
-- |
| XV |
21 Dec. |
Lesson 13. NP-complete problems |
-- |
| XVI |
28 Dec. |
Lesson 14. NLog- and PSPACE-complete problems |
HW 3 due. HW 4 out. |
|
|
XVII |
4 Jan. |
Reading week |
-- |
| XVIII |
11 Jan. |
Final exam |
HW 4 due. |
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 Thurdays in the indicated week.
- Their due dates are also always on Thursdays at the end of the class in the indicated week.
- You can submit your homework earlier than usualthe 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.
|