1
Jan 1721

Administrivia
Introduction and history;
strings
[scribbles]

String induction
[more]
[solutions]

Languages and regular
expressions
[scribbles]

Regular expressions
[solutions]

2
Jan 2428 
DFAs
[scribbles]

DFA construction
[solutions]

DFA product construction
[scribbles]

DFA product construction
[solutions]

3
Jan 31Feb 4 
Nondeterminism, NFAs
(revised version)
[scribbles]

NFAs
[solutions]

NFAs continued, equivalence with DFAs and regular
expressions (revised version)
Converting NFA to regex (Sariel's notes)
[scribbles]

Regular language transformation
[solutions]

4
Feb 711 
Proving nonregularity via fooling sets
[scribbles]

Proving nonregularity
[solutions]

Contextfree languages and grammars
[scribbles]

Contextfree grammars
[solutions]

5
Feb 1418 
Turing machines: history, formal definitions,
examples, variations
[scribbles] [slides]

Turing machine design
[solutions]

Optional review for Midterm 1
[scribbles]

Optional review for Midterm 1

Midterm 1: Feb 21 Monday 7:00pm9:30pm
Conflict: Feb 22 Tuesday 7:00pm9:30pm

6
Feb 2125 
Recursion: Hanoi, mergesort
[scribbles]
[solving recurrences] [BigO Notation]

Hint: Binary search
[solutions]

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

Divide and conquer
[solutions]

7
Feb 28Mar 4 
Backtracking: independent set, longest
increasing subsequence
[scribbles]

Backtracking
[solutions]

Dynamic programming: splitting strings,
longest common subsequence
[scribbles]

Dynamic programming
[solutions]

8
Mar 711 
More DP: Edit distance, Subset Sum
[scribbles]

More dynamic programming
[solutions]

More DP: MIS in trees
memoization and edit distance
[scribbles]

Yet even still more dynamic programming
[solutions]
Drop deadline

Mar 1418 
Spring break 
9
Mar 2125 
Graphs, basic search
[scribbles]

Graph modeling
[solutions]

DFS, topological sort, and strong connected compoments
[scribbles]

Graph modeling
[solutions]

10
Mar 28Apr 1 
BFS and shortest paths
[scribbles]

Shortest paths
[solutions]

Shortest paths with negative lengths via DP Allpairs shortest paths via DP
[scribbles]

More shortest paths
[solutions]

11
Apr 48 
Greedy algorithms
[scribbles]

Greedy
[solutions]

Optional review for Midterm 2
[scribbles]

Optional review for Midterm 2

Midterm 2: Apr 11 Monday 7:00pm9:30pm
Conflict: Apr 12 Tuesday 7:00pm9:30pm

12 Apr 1115 
MST algorithms
[scribbles]

MST
[solutions]

Polynomialtime reductions
[scribbles]

Reductions
[solutions]

13
Apr 1822 
NP, NPcompleteness,
3SAT to independent set
[scribbles]

NPhardness proofs
[solutions]

More NPhardness reductions: 3coloring, Hamiltonian cycle
[scribbles]

More NPhardness
[solutions]

14
Apr 2529 
More more NPcompleteness
[scribbles]
[slides (3coloring, Hamiltonian cycle, etc.)]

NPhardness: The final chapter
[solutions]

Undecidability: halting problem, diagonalization, reductions
[scribbles]

Undecidability via reductions
[solutions]

15
May 26 
Wrapup and preliminary review for the final exam
[scribbles]

Review for final

Reading day 

Final exam: May 12 Thursday 8:00am11:00am
