1
Jan 14- 18
|
Adminis+trivia
and course goals
Introduction and history;
strings
L1: [slides1,
slides2]
Scribbles:
A,
B.
|
String induction
[induction notes,
more]
[solutions]
|
Languages and regular
expressions
L2: [slides]
Scribbles:
A,
B.
|
Regular expressions
[solutions]
|
2
Jan 21-25 |
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides]
Scribbles:
A,
B.
|
DFA construction
[solutions]
|
Non-determinism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles:
A,
B.
|
DFA product construction
[solutions]
|
3
Jan 28
-Feb 1 |
NFAs continued, equivalence with DFAs and regular
expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
Scribbles:
A,
B.
|
DFA/NFA transformation
[solutions]
|
Proving non-regularity via fooling sets
[DFA Proofs]
[Fooling sets guide]
L6: [slides]
Scribbles:
A,
B.
|
Proving nonregularity
[solutions]
|
4
Feb 4-8 |
Context-free languages and grammars
L7: [slides]
Scribbles:
A,
B.
|
Context-free grammars
[solutions]
|
Turing machines: history, formal definitions,
examples, variations
L8: [slides]
Scribbles:
A,
B.
|
Regular or not?
[solutions]
|
5
Feb 11-15 |
Halting and undecidability
L9: [slides]
Scribbles:
A,
B.
|
Turing machine design
[solutions]
|
Optional review for Midterm 1
Scribbles:
A,
B.
|
Optional review for Midterm 1
|
| Skillset for midterm
1
|
Midterm 1: Monday, February 18, 7-9pm
(rooms)
Conflict: Gregory Hall,
213: Wednesday, February 20, 7-9pm.
Cover page
|
6
Feb 18-22 |
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Scribbles:
A,
B.
|
Hint: Binary search
[solutions]
|
Divide and conquer: linear-time selection,
Karatsuba multiplication
[recurrence notes]
[slides]
Scribbles:
A,
B.
|
Divide and conquer
[solutions]
|
7
Feb 25
-Mar 1 |
Backtracking: independent set, longest
increasing subsequence
[slides]
Scribbles:
A,
B.
|
Backtracking
[solutions]
|
Dynamic programming: splitting strings,
longest increasing subsequence
[slides]
Scribbles:
A,
B.
|
Dynamic programming
[solutions]
|
8
Mar 4-8 |
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
Scribbles:
A,
B.
|
More dynamic programming
[solutions]
|
CYK Algorithm,
Graphs, basic search
[CYK, Graph search slides]
Scribbles:
A,
B.
|
Yet even still more dynamic programming
Drop deadline
[solutions]
|
9
Mar 11-15 |
Directed graphs, depth-first search
Scribbles:
A,
B.
|
Graph modeling
[solutions]
|
DFS/Strong connected compoments
[slides]
[Graph notes]
Scribbles:
A,
B.
|
Graph modeling
[solutions]
|
| Mar 16-24 |
Don't give thanks, go on vacation anyway. |
10
Mar 25- 29 |
BFS and Shortest Paths
[slides]
Scribbles:
A,
B.
|
Shortest paths
[solutions]
|
Shortest Paths with Negative Lengths via DP
[slides]
Scribbles:
A,
B.
|
More shortest paths
[solutions]
|
11
Apr 1-5 |
Greedy algorithms
[slides]
Scribbles:
A,
B.
|
Greedy
[solutions]
|
MST Algorithms
[slides]
Scribbles:
A,
B.
|
Fodder: Optional review for Midterm 2
|
| Skillset for midterm
2
|
Midterm 2: Monday, April 8, 7-9pm
(rooms :
cover page :
solution)
Conflict exam: Wednesday, April 10, 7-9pm, Siebel 1404
|
12
Apr 8-12 |
No lecture in lieu of midterm |
MST
[solutions]
|
Undecidability: halting problem, diagonalization, reductions
[slides]
Scribbles:
A,
B.
|
Undecidability via reductions
[solutions]
|
13
Apr 15-19 |
Polynomial time Reductions
[slides]
Scribbles:
A,
B.
|
Self Reductions
[solutions]
|
NP, NP-Completeness,
3SAT to Independent Set
[slides]
Scribbles:
A,
B.
[helpful video on P vs NP]
|
NP-hardness proofs
[solutions] |
14
Apr 22-26 |
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
Scribbles:
A,
B.
|
NP-Hardness, the final chapter
[solutions]
|
More more more NP Completeness.
[slides]
ICES Forms
Scribbles:
A,
B.
|
Using Rice's Theorem
ICES Forms
[solutions]
|
15
Apr 29
-May 3 |
Wrap-up and preliminary review for the final exam
Scribbles:
A,
B.
|
Review for final
|
Reading Day |
|
Skill
set for final
Study material for the final
|
Final exam:
Monday May 6th, 1:30pm to 4:30pm (proof)
Conflict final: May 7th, 10am-1pm, Siebel 1404.
|