| Jan 21-24 |
Administrivia, course goals, Strings and Languages
Notes on strings
[slides1, slides2]
|
String induction
[Jeff's induction notes, Chandra's additional notes] [solutions] |
Languages and regular expressions
[slides] |
Regular expressions
[solutions] |
| Jan 28-31 |
DFAs, product construction
[Automata Tutor] [slides] DFA Proofs |
DFA construction
[solutions] |
Non-determinism, NFAs
Jeff's NFA notes
[slides] [scribbles] |
DFA product construction
[solutions] |
| Feb 4-7 |
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
[slides] [scribbles] |
NFAs
[solutions] |
Proving non-regularity via fooling sets
[slides][Fooling sets notes][Fooling sets guide] |
Language transformations
[solutions] |
| Feb 11-14 |
Context-free languages and grammars
[slides] |
Proving non-regularity
[solutions] |
Turing machines: history, formal definitions, examples, variations
[slides] |
Context free languages
[solutions] |
| Feb 18-21 |
Universal Turing Machine, RAM simulation, P
[slides] |
Turing machine design
[solutions] |
Optional review for Midterm 1
Fodder for exam preparation |
Regular or not and Fodder
[solutions] |
Midterm 1: Monday, Feb 24, 7-9:30pm (Syllabus/Skillset)
|
| Feb 25-28 |
Recursion: Hanoi, mergesort
[slides][solving recurrences] |
Hint: Binary search
[solutions] |
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides] |
Divide and conquer
[solutions] |
| Mar 4-7 |
Backtracking: independent set, longest increasing subsequence
[slides ] |
Backtracking
[solutions] |
Dynamic programming: splitting strings, longest increasing subsequence
[slides] |
Dynamic programming
[solutions] |
| Mar 11-14 |
More DP: Edit Distance, MIS in trees
[slides] [CYK slides] [CYK Algorithm] |
More dynamic programming
[solutions] |
Graphs, basic search
[slides] [handout] [scribbles] |
Yet even still more dynamic programming
Drop deadline
[solutions] |
| Mar 18-21 |
Spring break |
| Mar 25-29 |
Directed graphs, depth-first search
[slides] [handout] [scribbles] |
Graph modeling
[solutions] |
DP in DAGs, strongly connected components
[Graph notes] [slides] [handout] [scribbles] |
Graph modeling
[solutions] |
| April 1-4 |
Single-Source Shortest Paths
[slides] [handout] [scribbles] |
Shortest paths
[solutions] |
Shortest Paths with Negative Lengths via DP, All Pairs
[slides] [handout] [scribbles] |
More shortest paths
[solutions] |
| April 8-11 |
MST Algorithms
[slides] [handout] [scribbles] |
MST
[solutions] |
Optional review for Midterm 2, Fodder
[scribbles] |
Optional review for Midterm 2 |
Midterm 2: Monday, April 14, 7-9:30pm (Syllabus/Skillset)
|
| April 15-18 |
Greedy algorithms
[slides] [handout] [scribbles] |
Greedy
[solutions] |
Reductions
[slides] [handout] [scribbles] |
Self Reductions
[solutions] |
| April 22-25 |
Undecidability: halting problem, diagonalization, reductions
[slides] [handout] [scribbles] |
Undecidability via reductions
[solutions] |
NP, NP-Completeness, 3SAT to Independent Set
[slides] [handout] [scribbles][helpful video on P vs NP] |
NP-hardness proofs
[solutions] |
| April 29-May 2 |
More NP-hardness reductions: Independent Set, 3-Coloring
[slides] [handout] [scribbles] |
NP-Hardness, the final chapter
[solutions] |
Even more NP-hardness reductions: Hamiltonian Cycle, Subset Sum
[slides] [handout] [scribbles] |
Reductions |
| May 6-9 |
No lecture, optional review session |
Optional review for final, Fodder
|
Reading Day |
|
| Final Exam: Thursday, May 15, 7-10pm (Syllabus/Skillset) |