1
Aug 28  Sep 1 
Adminis+trivia
and course goals
Introduction and history;
strings
L1: [slides1,
slides2]

String induction
[induction notes,
more]
[solutions]

Languages and regular
expressions
L2: [slides]

Regular expressions
[solutions]

2
Sep 48 
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides]

DFA construction
[solutions]

Nondeterminism, NFAs
Jeff's NFA notes
L4: [slides]

DFA product construction
[solutions]

3
Sep 1115 
NFAs continued, equivalence with DFAs and regular
expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]

DFA/NFA transformation
[solutions]

Proving nonregularity via fooling sets
[DFA Proofs]
[Fooling sets guide]
L6: [slides]

Proving nonregularity
[solutions]

4
Sep 1822 
Contextfree languages and grammars
L7: [slides]

Contextfree grammars
[solutions]

Turing machines: history, formal definitions,
examples, variations
L8: [slides]

Regular or not?
[solutions]

5
Sep 2529 
Universal Turing Machine, RAM simulation, P
[UTM slides][complexity slides]

Turing machine design
[solutions]

Optional review for Midterm 1

Optional review for Midterm 1

Midterm 1: Monday, October 2, 79pm
Conflict exam: TBD TBD 
6
Oct 26 
Recursion: Hanoi, mergesort
[slides][solving recurrences]

Hint: Binary search
[solutions]

Divide and conquer: lineartime selection,
Karatsuba multiplication
[recurrence notes] [slides]

Divide and conquer
[solutions]

7
Oct 913 
Backtracking: independent set, longest
increasing subsequence
[slides]

Backtracking
[solutions]

Dynamic programming: splitting strings,
longest increasing subsequence
[slides]

Dynamic programming
[solutions]

8
Oct 1620 
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]

9
Oct 2327 
Directed graphs, depthfirst search
[slides]

Graph modeling
[solutions]

Catch up lecture
[Graph notes]

Graph modeling
[solutions]

10
Oct 30 Nov 3 
BFS and Shortest Paths
[slides]

Shortest paths
[solutions]

Shortest Paths with Negative Lengths via DP
[slides]

More shortest paths
[solutions]

11
Nov 610 
Greedy algorithms
[slides]

Greedy
[solutions]

MST Algorithms
[slides]

Optional review for Midterm 2

Midterm 2: Monday, November 13, 79pm
, Conflict exam: TBD TBD TBD 
12 Nov 1317 
No lecture in lieu of midterm 
MST
[solutions]

Undecidability: halting problem, diagonalization, reductions
[slides]

Undecidability via reductions
[solutions]

Nov 1826 
Give thanks, go on vacation. 
13
Nov 27  Dec 1 
Polynomial time Reductions
[slides]

Self Reductions
[solutions]

NP, NPCompleteness,
3SAT to Independent Set
[slides][helpful video on P vs NP]

NPhardness proofs
[solutions] 
14
Dec 48 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]

NPHardness, the final chapter
[solutions]

Undecidability: more reductions, Rice's theorem
[slides]
ICES Forms

Using Rice's Theorem
ICES Forms
[solutions]

15
Dec 1115 
Wrapup and preliminary review for the final exam 
Review for final

Reading Day 

Final exam:
Monday, December 18 8:0011:00 a.m.
Conflict exam: TBD, TBD 