Jan 1720 
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 2427 
DFAs, product construction
[Automata Tutor] [slides] DFA Proofs 
DFA construction
[solutions] 
Nondeterminism, NFAs
Jeff's NFA notes
[slides] 
DFA product construction
[solutions] 
Jan 31Feb 3 
NFAs continued, equivalence with DFAs and regular expressions
Jeff's NFA notes
[slides] 
NFAs
[solutions] 
Proving nonregularity via fooling sets
[slides][Fooling sets notes][Fooling sets guide] 
Language transformations
[solutions] 
Feb 710 
Contextfree languages and grammars
[slides] 
Proving nonregularity
[solutions] 
Turing machines: history, formal definitions, examples, variations
[slides] 
Context free languages
[solutions] 
Feb 1417 
Universal Turing Machine, RAM simulation, P
[UTM slides][complexity slides] 
Turing machine design
[solutions] 
Optional review for Midterm 1
Fodder for exam preparation 
Regular or not and Fodder
[solutions] 
Midterm 1: Monday, Feb 20, 79:30pm (Syllabus/Skillset)

Feb 2124 
Recursion: Hanoi, mergesort
[slides][solving recurrences] 
Hint: Binary search
[solutions] 
Divide and conquer: lineartime selection, Karatsuba multiplication
[recurrence notes] [slides] 
Divide and conquer
[solutions] 
Feb 28Mar 3 
Backtracking: independent set, longest increasing subsequence
[slides ] 
Backtracking
[solutions] 
Dynamic programming: splitting strings, longest increasing subsequence
[slides] 
Dynamic programming
[solutions] 
Mar 710 
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] 
Mar 1417 
Spring break 
Mar 2124 
Directed graphs, depthfirst search
[slides] 
Graph modeling
[solutions] 
Graphs continued
[Graph notes] 
Graph modeling
[solutions] 
Mar 2831 
BFS and Shortest Paths
[slides] 
Shortest paths
[solutions] 
Shortest Paths with Negative Lengths via DP, All Pairs
[slides] 
More shortest paths
[solutions] 
April 47 
MST Algorithms
[slides] 
MST
[solutions] 
Optional review for Midterm 2, Fodder 
Optional review for Midterm 2 
Midterm 2: Monday, April 10, 79:30pm (Syllabus/Skillset)

April 1114 
Greedy algorithms
[slides] 
Greedy
[solutions] 
Undecidability: halting problem, diagonalization, reductions
[slides] 
Undecidability via reductions
[solutions] 
April 1821 
Reductions
[slides] 
Self Reductions
[solutions] 
NP, NPCompleteness, 3SAT to Independent Set
[slides][helpful video on P vs NP] 
NPhardness proofs
[solutions] 
April 2528 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides] 
NPHardness, the final chapter
[solutions] 
More on SAT, Wrap up
[slides]

Reductions 
May 25 
No lecture, optional review session 
Optional review for final, Fodder

Reading Day 

Final Exam: Friday, May 5, 811am (Syllabus/Skillset) 