|
|
|
General Information
|
|
Lecturer: Wing-Kai Hon 韓永楷
|
|
|
wkhon @ cs.nthu.edu.tw
|
|
|
資電館 540 / 資電館 741
|
|
|
Tue 1500—1600, Fri 1420—1520
|
|
|
|
Tutor: Yu-Han Lyu 呂昱翰
|
|
|
944352 @ oz.nthu.edu.tw
|
|
|
紅樓 315
|
|
|
Wed 1500—1700
|
|
|
|
Meeting Times:
|
|
|
Tue 1410—1500, Fri 1520—1710
|
|
|
|
|
Announcement
|
|
Jan 08: Homework 5 solution [pdf]
|
|
Jan 05: Proof of Savitch’s Theorem [pdf]
|
|
Jan 03: Assignment 4 Solution uploaded [pdf]
Tutorial 6 uploaded
[pdf]
Lecture Notes 24
uploaded [pdf]
|
|
Jan 01:
Lecture Notes 21 updated [pdf]
(Thanks to 謝明峰同學 for pointing out an error in the proof of 3SAT is NP-complete)
|
|
Useful Web Links
|
|
v
Automata Theory
by Ullman [link]
v
Complexity Theory
by Arora and Barak [link]
v
Computational
Complexity by Goldreich [link]
|
|
 Course Materials
|
Lecture
|
Topics
|
Related
Files
|
|
0
|
Overview
|
[pdf]
|
|
1
|
Mathematics Review I
|
[pdf]
|
|
2
|
Mathematics Review II
|
[pdf]
|
|
3
|
Automata I
|
[pdf]
|
|
4
|
Automata II
|
[pdf]
|
|
5
|
Automata III
|
[pdf]
|
|
6
|
Automata IV
|
[pdf]
|
|
7
|
Automata V
|
[pdf]
|
|
8
|
Automata VI
|
[pdf]
|
|
9
|
Automata VII
|
[pdf]
|
|
10
|
Computability I
|
[pdf]
|
|
11
|
Computability II
|
[pdf]
|
|
12
|
Computability III
|
[pdf]
|
|
13
|
Computability IV
|
[pdf]
|
|
14
|
Computability V
|
[pdf]
|
|
15
|
Computability VI
|
[pdf]
|
|
16
|
Complexity I
|
[pdf]
|
|
17
|
Complexity II
|
[pdf]
|
|
18
|
Complexity III
|
[pdf]
|
|
19
|
Complexity IV
|
[pdf]
|
|
20
|
Complexity V
|
[pdf]
|
|
21
|
Complexity VI
|
[pdf]
|
|
22
|
Complexity VII
|
[pdf]
|
|
23
|
Complexity VIII
|
[pdf]
|
|
|
à Proof of Savitch’s Theorem
|
[pdf]
|
|
24
|
Complexity IX
|
[pdf]
|
|
Tutorial
|
Topics
|
Related
Files
|
|
1
|
Closed operations, Homework Hints
|
[pdf]
|
|
2
|
CFG, Homework Solutions and Hints
|
[pdf]
|
|
3
|
CFG, Chomsky Hierarchy, Homework Solutions
|
[pdf]
|
|
---
|
Quiz and Solutions
|
[pdf]
|
|
4
|
Computational Complexity, Homework Hints
|
[pdf]
|
|
5
|
Oracle, Reducibility, HW Solutions & Hints
|
[pdf]
|
|
6
|
Recent Theory Research, HW Solns & Hints
|
[pdf]
|
 Teaching Plan
|
1
|
Regular Language
|
DFA, NFA, Regular Expression
|
|
2
|
Context-free Grammar
|
Pushdown Automata
|
|
3
|
Turing Machines
|
|
|
4
|
Computability
|
Halting Problem, Reduction Technique
|
|
5
|
Time Complexity
|
Class P, NP, NP-Complete
|
|
6
|
Space Complexity
|
Relationship between Time and Space
|
|
7
|
Intractability
|
Problems Requiring More Time or Space
|
|
8
|
Advanced Topics
|
Interactive Proof Systems, Cryptography, …
|
Last updated: 08 January 2007
|