
General Information

Lecturer: WingKai Hon 韓永楷


wkhon @ cs.nthu.edu.tw


資電館 540 / 資電館 741


Tue 1500—1600, Fri 1420—1520


Tutor: YuHan 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 NPcomplete)

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

Contextfree Grammar

Pushdown Automata

3

Turing Machines


4

Computability

Halting Problem, Reduction Technique

5

Time Complexity

Class P, NP, NPComplete

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
