Aug 23–27 
Administrivia and course goals
Introduction;
strings and induction
[scribbles,
video]

String induction
[induction notes]
[solutions]

Languages and regular expressions;
[scribbles,
video]

Regular expressions
[solutions]

Aug 30–Sep 3 
DFAs: intuition, definitions, examples
[scribbles,
video]

DFAs
[Automata Tutor,
JFLAP,
solutions]

DFAs: product construction, closure properties, automatic=regular
[scribbles,
video]

DFA product construction
[solutions]

Sep 6–10 
Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, video]
[additional fooling set notes by Eric Huber]

Proving nonregularity
[solutions]

NFAs: εtransitions, equivalence with DFAs
[scribbles, video]

Regex to NFA to DFA (to regex)
[solutions]

Sep 13–17 
Converting regular expressions to NFAs,
language transformations
[scribbles, video],
[language transformations walkthrough video pdf or notability]

Language transformations
[solutions]

Contextfree languages and grammars
[scribbles,
video]

Contextfree grammars
[solutions]

Sep 20–24 
Turing machines
[scribbles,
video]

More language transformations
[solutions]

Optional review for Midterm 1
[practice midterm,
Dakshita's solutions,
Jeff's solutions,
video]

Optional review for Midterm 1

Midterm 1 — Monday, September 27, 7:00–9:30pm
Conflict exam: Tuesday, September 28

Sep 27–Oct 1 
Recursion: Hanoi, mergesort, quicksort
[scribbles,
video]

Hint: Binary search
[solutions]

Divide and conquer: Karatsuba multiplication, lineartime selection
[scribbles,
video]

Fun with Karatsuba
[solutions]

Oct 4–8 
Backtracking: n queens, game trees, text segmentation
[scribbles,
video]

Backtracking
[solutions]

Dynamic programming: Fibonacci, text segmentation again
[scribbles,
video]

Dynamic programming
[solutions]

Oct 11–15 
Sequence dynamic programming: Edit distance
[scribbles,
video]

More dynamic programming
[solutions]

Treeshaped dynamic programming: Optimal binary search trees
[scribbles,
video]

Yet even still more dynamic programming
[solutions]
Drop deadline

Oct 18–22 
Graphs: definitions, representations, data structures, traversal
[scribbles,
video]

Graph modeling
[solutions]

Depthfirst search, topological sort
[scribbles,
video]

Topological sort
[solutions]

Oct 25–29 
Dynamic programming in DAGs, strongly connected components
Generic shortest paths
[scribbles,
video]

Shortest paths
[solutions]

Shortest paths:
BFS, DFS, Disjktra, BellmanFord, and (briefly)
FloydWarshall
[scribbles,
video]

Allpairs shortest paths
[solutions]

Nov 1–5 
Allpairs shortest paths in detail
[scribbles,
video]

Solve it both ways
[solutions]

Optional review for Midterm 2
[practice midterm,
Jeff's solutions,
video]

Optional review for Midterm 2

Midterm 2 — Monday, November 8, 7:00–9:30pm
Conflict exam: Tuesday, November 9

Nov 8–12 
Reductions, hardness
[scribbles,
video]

Reductions
[solutions]

P vs NP, NPhardness, NPhardness reductions: 3SAT, Clique
[scribbles,
video]

NPhardness proofs
[solutions]

Nov 15–19 
More NPhardness: 3 Coloring, Hamiltonian cycle
[scribbles,
video]

More NPhardness proofs
[solutions]

Hamiltonian Cycle wrapup, Hamiltonian path, other NP hard problems, NPhardness review
[scribbles,
video]

Even more NPhardness proofs
[solutions]

Nov 22–26 
Thanksgiving break 
Nov 29–Dec 3 
NP Hardness examples, Undecidability: code is data, the halting problem
[scribbles,
video]
ICES forms available

Yet even still more NPhardness examples
[solutions]

Undecidability: reductions and Rice's theorem
[scribbles,
video,
skipped lab on undecidability reductions,
skipped lab solutions

Using Rice's Theorem
[solutions]

Dec 6–10 
Wrapup and final exam review
[scribbles,
video]

Review for final exam
ICES deadline



Final exam — Wednesday, December 15, 8am—11am
Conflict exam: TBA
