|
|
|
Date
|
Lecture Topic
|
Homework / Group Work
|
Reading
|
Jan
20
|
Introduction;
DFAs (pdf, ppt, bw)
|
Homework
1 (solution)
|
0,
1.1
|
Jan
21
|
Recitation
|
Group Work 1
(solution)
|
|
Jan
22
|
Regular
operations and NFAs (pdf, ppt, bw)
|
|
1.1,
1.2
|
Jan
27
|
Equivalence
of DFAs and NFAs (pdf, ppt, bw)
|
Homework
2 (solution)
|
1.2
|
Jan
28
|
Quiz 1
|
Group
Work 2 (solution)
|
|
Jan
29
|
Regular
Expressions (pdf, ppt,
bw)
|
|
1.3
|
Feb
3
|
The
pumping lemma: nonregular
languages (pdf, ppt,
bw)
|
Homework
3 (solution)
|
1.4
|
Feb
4
|
Recitation
|
Group
Work 3 (solution)
|
|
Feb
5
|
Context-Free
Languages (pdf, ppt,
bw)
|
|
2.1,2.2
|
Feb
10
|
PDA/CFG
Equivalence (pdf, ppt,
bw)
|
Homework
4 (solution)
|
2.2
|
Feb
11
|
Quiz 2
|
Group
Work 4 (solution)
|
|
Feb
12
|
Parsing,
Patching and Pumping (pdf, ppt, bw)
|
|
2.1,2.3
|
Feb
17
|
Review
(pdf, ppt, bw)
|
none
|
|
Feb
18
|
Recitation
|
Group
Work 5 (solution)
|
|
Feb 19
|
Midterm
I (practice
midterm, solutions)
|
|
|
Feb
24
|
Turing
Machines (pdf, ppt,
bw)
|
Homework
5 (solution)
|
3.1,
3.2
|
Feb
25
|
Recitation
|
Group
Work 6 (solution)
|
|
Feb
26
|
The
Church-Turing Thesis (pdf, ppt, bw) |
|
3.2,
3.3 |
Mar
3
|
Problems
about Programs; To Infinity... and Beyond! (pdf,
ppt, bw)
|
Homework
6 (solution)
|
4.1,
4.2
|
Mar
4
|
Quiz 3
|
Group
Work 7 (solution)
|
|
Mar
5
|
Undecidability
I: The Halting
problem (pdf, ppt,
bw) |
|
4.2
|
Mar
10
|
Undecidability
II: Reductions (pdf, ppt, bw) |
Homework
7 (solution)
|
5.3,
5.2 |
Mar
11
|
Recitation
|
Group
Work 8 (solution)
|
|
Mar
12
|
Undecidability
III: More Reductions (pdf, ppt, bw) |
|
5.1 |
Mar
17
|
SPRING BREAK
|
Mar
18
|
Mar
19
|
Mar
24
|
Undecidability
IV: Rice's
Theorem (pdf, ppt,
bw)
|
Homework
8 (solution)
|
5.1,
p. 215 |
Mar
25
|
Quiz 4
|
Group
Work 9 (solution)
|
|
Mar
26
|
The
Recursion Theorem and Incompleteness (pdf, ppt, bw)
|
|
6.1,
6.2
|
Mar
31
|
Review
(pdf, ppt, bw)
|
|
|
Apr
1
|
Recitation
|
Group
Work 10 (April Fool's)
|
|
Apr 2
|
Midterm
II (practice
midterm, solutions)
|
|
|
Apr
7
|
Intro
Complexity Theory (pdf, ppt, bw)
|
Homework 9 (solution)
|
7.1
|
Apr
8
|
Recitation
|
Group
Work 11 (solution)
|
|
Apr
9
|
Polynomial
Time and NP (pdf, ppt,
bw)
|
|
7.2,
7.3
|
Apr
14
|
The
P vs NP problem (pdf, ppt, bw)
|
Homework
10 (solution)
|
7.3,
7.4
|
Apr
15
|
Quiz 5
|
Group
Work 12 (solution)
|
|
Apr
16
|
NP-Completeness
I: Trivial NP-Complete languages and Circuit Satsifiability (pdf, ppt, bw)
|
|
7.4
|
Apr
21
|
NP-Completeness
II: More Satisfiability variants (pdf, ppt, bw)
|
Homework
11 (solution)
|
7.4
|
Apr
22
|
Recitation
|
Group
Work 13 (solution)
|
|
Apr
23
|
NP-Completeness
III: Restriction and Local Replacement
(pdf, ppt, bw)
|
|
7.5
|
Apr
28
|
NP-Completeness
IV: Component Design Reductions
(pdf, ppt, bw)
|
Homework
12 (solution)
|
7.5
|
Apr
29
|
Quiz 6
|
Group
Work 14 (solution)
|
|
Apr
30
|
Space
complexity and Savitch's Theorem (pdf, ppt, bw)
|
|
8.1
|
May
5
|
PSPACE
completeness (pdf, ppt,
bw)
|
|
8.2,
8.3
|
May
6
|
Recitation
|
Group
Work 15 (no solution)
|
|
May
7
|
Review
(pdf, ppt, bw)
|
|
|
THURSDAY,
May 14,
8:00am-10:00am
|
FINAL
EXAM 8:00am - 10:00am, PHYS 170 (Lecture Hall)
(practice
final, solutions)
|
The lecture slides for this course are partially based on materials
developed by Luis von Ahn, for CS 453 at Carnegie Mellon University.
|
|
