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): solution. 
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
n queens demo(ipynb)(html) 
Backtracking
[solutions] 
Dynamic programming: splitting strings, longest increasing subsequence
[slides]
Scribbles
python memoize demo(ipynb) (html) 
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
optimal bst (ipynb) (html) 
Yet even still more dynamic programming
Drop deadline
[solutions] 
9
Oct 1923 
Directed graphs, depthfirst search
Scribbles 
Graph modeling
[solutions] 
DFS/Strong connected components
[slides]
[Graph notes]
Scribble[1, 2] 
Graph modeling
[solutions] 
10
Oct 2630 
BFS and Shortest Paths
[slides]
Scribbles 
Shortest paths
[solutions] 
Shortest Paths with Negative Lengths via DP
[slides]
Scribble[1, 2]  Animation 
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 
Midterm 2: Sunday/Monday, November 8/9 (details): solution. 
12
Nov 913 
No lecture in lieu of midterm 
No discussion in lieu of midterm 
MST Algorithms [slides]
Scribbles 
MST
[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 
Self redutions and NPC
[solutions] 
15
Dec 79 
Wrapup and preliminary review for the final exam
Scribbles 
Review for final 


Dec 10 
Reading day (Thursday) 
Final exam time window: Dec 17, 12:01am  Dec 18, 11:59pm (CST). 
OLD Skill set for final
Study material for the final 