|
Lecture
|
Topics
|
Files
|
|
0
|
Overview
|
[pdf]
|
|
1
|
Mathematics Review I (Basic Terminology)
|
[pdf]
|
|
2
|
Mathematics Review II (Common Proof
Techniques)
|
[pdf]
|
|
3
|
Automata Theory I (DFA and NFA)
|
[pdf]
|
|
4
|
Automata Theory II (DFA = NFA, Regular
Language)
|
[pdf]
|
|
5
|
Automata Theory III (Non-regular
Language, Pumping Lemma)
|
[pdf]
|
|
6
|
Automata Theory IV (Reg Expression =
NFA = DFA)
|
[pdf]
|
|
7
|
Automata Theory V (CFG, CFL, CNF)
|
[pdf]
|
|
8
|
Automata Theory VI (PDA, CFG = PDA)
|
[pdf]
|
|
9
|
Automata Theory VII (Pumping Lemma,
Non-CFL)
|
[pdf]
|
|
10
|
Computability Theory I (Turing Machine)
|
[pdf]
|
|
11
|
Computability Theory II (TM Variants,
Church-Turing Thesis)
|
[pdf]
|
|
12
|
Computability Theory III (Decidable
Languages)
|
[pdf]
|
|
13
|
Computability Theory IV (Undecidable
Languages)
|
[pdf]
|
|
14
|
Computability Theory V (Prove by Reduction)
|
[pdf]
|
|
15
|
Computability Theory VI (Post’s
Correspondence, Reducibility)
|
[pdf]
|
|
16
|
Complexity Theory I (Time Complexity)
|
[pdf]
|
|
17
|
Complexity Theory II (Relationship
Among Models)
|
[pdf]
|
|
18
|
Complexity Theory III (P and NP)
|
[pdf]
|
|
19
|
Complexity Theory IV (More on NP,
NP-Complete)
|
[pdf]
|
|
20
|
Complexity Theory V (Polynomial-Time
Reducibility)
|
[pdf]
|
|
21
|
Complexity Theory VI (More NP-Complete
Problems)
|
[pdf]
|
|
22
|
Complexity Theory VII (More NP-Complete
Problems)
|
[pdf]
|
|
23
|
Complexity Theory VIII (Space
Complexity)
|
[pdf]
|
|
24
|
Complexity Theory IX (PSPACE, L, NL)
|
[pdf]
|
|
***
|
The Revision
|
[pdf]
|
