| Aug 28-31 |
Administrivia and course goals
Notes on strings
[sect A: slides1, slides2] [sect B: slides1, slides2] |
String induction
[Jeff's induction notes, Chandra's additional notes] [solutions] |
Languages and regular expressions
[sec A slides, sect B slides] |
Regular expressions
[solutions] |
| Sep 4-7 |
DFAs, product construction
[Automata Tutor] [sec A slides] [sec B slides] DFA Proofs |
DFA construction
[solutions] |
Non-determinism, NFAs
Jeff's NFA notes
[sec A slides] [sec B slides] |
DFA product construction
[solutions] |
| Sep 11-14 |
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
[sec A slides sec B slides] |
DFA/NFA transformation
[solutions] |
Proving non-regularity via fooling sets
[slides]
[DFA Proofs][Fooling sets guide] |
Proving nonregularity
[solutions] |
| Sep 18-21 |
Context-free languages and grammars
[slides: secA, secB]
|
Context-free grammars
[solutions] |
Turing machines: history, formal definitions, examples, variations
[slides]
|
Regular or not?
[solutions] |
| Sep 25-28 |
Universal Turing Machine, RAM simulation, P
[UTM slides][complexity slides]
|
Turing machine design
[solutions] |
SecA Optional review for Midterm 1
Sec B Recursion: Hanoi, mergesort (see Oct 2 links)
sec B slides
| Optional review for Midterm 1 |
Midterm 1: Monday, October 1, 7-9:30pm
|
| Oct 2-5 |
Sec A: Recursion: Hanoi, mergesort
Sec B: no lecture
[slides][solving recurrences]
|
Hint: Binary search
[solutions] |
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides]
|
Divide and conquer
[solutions] |
| Oct 9-12 |
Backtracking: independent set, longest increasing subsequence
[sec A slides sec B notebook] |
Backtracking
[solutions] |
Dynamic programming: splitting strings, longest increasing subsequence
[slides sec B notebook] |
Dynamic programming
[solutions] |
| Oct 16-19 |
More DP: Edit Distance, MIS in trees
[slides]
|
More dynamic programming
[solutions] |
CYK Algorithm, Graphs, basic search
[CYK slides, Graph search slides] |
Yet even still more dynamic programming
Drop deadline
[solutions] |
| Oct 23-26 |
Directed graphs, depth-first search
[slides]
|
Graph modeling
[solutions] |
Catch up lecture
[Graph notes]
|
Graph modeling
[solutions] |
| Oct 30 - Nov 2 |
BFS and Shortest Paths
[slides]
|
Shortest paths
[solutions] |
Shortest Paths with Negative Lengths via DP
[slides]
|
More shortest paths
[solutions] |
| Nov 6-9 |
MST Algorithms
[Kent's slides], [slides]
|
MST
[solutions] |
Optional review for midterm 2
[sec B sketches] |
Optional review for Midterm 2 |
Midterm 2: Monday, November 12, 7-9:30pm
Conflict exam: Tuesday, Nove 13 |
| Nov 13-16 |
Greedy algorithms
[slides]
| Greedy
[solutions] |
Undecidability: halting problem, diagonalization, reductions
[slides]
|
Undecidability via reductions
[solutions] |
| Nov 20-23 |
Fall break |
| Nov 27-30 |
Polynomial time Reductions
[slides]
|
Self Reductions
[solutions] |
NP, NP-Completeness,
3SAT to Independent Set
[slides][helpful video on P vs NP] |
NP-hardness proofs
[solutions] |
| Dec 4-7 |
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides]
|
NP-Hardness, the final chapter
[solutions] |
Undecidability: more reductions, Rice's theorem
[slides]
ICES Forms |
Using Rice's Theorem
ICES Forms
[solutions] |
| Dec 11-14 |
No lecture, review session Thursday |
Review for final |
Review session: 7pm, ECEB 1002 |
|
Final exam: Saturday, Dec 15, 1:30-4:30 p.m.
|