CS 5371 Theory of Computation (Fall 2006)

 

 

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]

 

Assignment

Topics

Related Files

1

Regular Languages

[pdf] [doc] [solution]

2

Context Free Grammar

[pdf] [doc] [solution] [figure]

3

Turing Machines, Decidability

[pdf] [doc] [solution]

4

Reducibility

[pdf] [doc] [solution]

5

P, NP, and NP-complete

[pdf] [doc] [solution]

 


 

 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