1
Aug 2428 
Adminis+ trivia and course goals
Introduction and history; strings
L1: [slides1, slides2]
Scribbles 
String induction
[induction notes, more] [solutions]
[prerecording] 
Languages and regular expressions
L2: [slides]
Scribbles 
Regular expressions
[solutions] 
2
Aug 31Sep 4 
DFAs, product construction
[Automata Tutor] DFA Proofs
L3: [slides]
Scribbles 
DFA construction
[solutions]
[prerecorded] 
Nondeterminism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles 
DFA product construction
[solutions]
[yt : ms : ct] 
3
Sep 711 
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
Scribbles 
DFA/NFA transformation
[solutions] 
Proving nonregularity via fooling sets
[DFA Proofs] [Fooling sets guide]
L6: [slides]
Scribbles 
Proving nonregularity
[solutions] 
4
Sep 1418 
Contextfree languages and grammars
L7: [slides]
Scribbles 
Contextfree grammars
[solutions] 
Turing machines: history, formal definitions, examples, variations
L8: [slides]
Scribbles 
Regular or not?
[solutions] 
5
Sep 2125 
Halting and undecidability
L9: [slides]
Scribbles 
Undecidability
[solutions] 
Optional review for Midterm 1
Scribbles 
Optional review for Midterm 1 
Midterm 1: Sunday/Monday, September 27/28 (details (TBD)) 
6
Sep 28Oct 2 
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Scribbles 
Hint: Binary search
[solutions] 
Divide and conquer: lineartime selection, Karatsuba multiplication
[recurrence notes] [slides]
Scribbles 
Divide and conquer
[solutions] 
7
Oct 59 
Backtracking: independent set, longest increasing subsequence
[slides]
Scribbles 
Backtracking
[solutions] 
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Scribbles 
Dynamic programming
[solutions] 
8
Oct 1216 
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
Scribbles 
More dynamic programming
[solutions] 
CYK Algorithm, Graphs, basic search
[CYK, Graph search slides]
Scribbles 
Yet even still more dynamic programming
Drop deadline
[solutions] 
9
Oct 1923 
Directed graphs, depthfirst search
Scribbles 
Graph modeling
[solutions] 
DFS/Strong connected compoments
[slides]
[Graph notes]
Scribbles 
Graph modeling
[solutions] 
10
Oct 2630 
BFS and Shortest Paths
[slides]
Scribbles 
Shortest paths
[solutions] 
Shortest Paths with Negative Lengths via DP
[slides]
Scribbles 
More shortest paths
[solutions] 
11
Nov 26 
ELECTION DAY
Vote early and vote often 
Greedy
[solutions] 
Greedy algorithms
[slides]
Scribbles 
Fodder: Optional review for Midterm 2 
OLD Skillset for midterm 2 
Midterm 2: Sunday/Monday, November 8/9
(details TBD : OLD cover page : dead link) 
12
Nov 913 
MST Algorithms
[slides]
Scribbles 
MST
[solutions] 
No lecture in lieu of midterm 
Turing Machines?
[solutions] 
13
Nov 1620 
Polynomial time Reductions
[slides]
Scribbles 
Self Reductions
[solutions] 
NP, NPCompleteness, 3SAT to Independent Set
[slides]
Scribbles
[helpful video on P vs NP] 
NPhardness proofs
[solutions] 
Nov 2129 
Definitely give thanks, go on vacation. 
14
Nov 30Dec 4 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]
Scribbles 
NPHardness, the final chapter
[solutions] 
More more more NP Completeness.
[slides]
Scribbles 
Using Rice's Theorem
ICES Forms
[solutions] 
15
Dec 79 
Wrapup and preliminary review for the final exam
Scribbles 
Review for final 


Dec 10 
Reading day (Thursday) 
OLD Skill set for final
Study material for the final 
Final exam: TBD 