1
Jan 1519

Administrivia
Introduction and history;
strings
[scribbles]

String induction
[more]
[solutions]

Languages and regular
expressions
[scribbles]

Regular expressions
[solutions]

2
Jan 2226 
DFAs
[scribbles]

DFA construction
[solutions]

DFA product construction
[scribbles]

DFA product construction
[solutions]

3
Jan 29Feb 2 
Nondeterminism, NFAs
[scribbles]

NFAs
[solutions]

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

Regular language transformation
[solutions]

4
Feb 59 
Proving nonregularity via fooling sets
[scribbles]

Proving nonregularity
[solutions]

Contextfree languages and grammars
[scribbles]

Contextfree grammars
[solutions]

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

Turing machine design
[solutions]

Optional review for Midterm 1
[scribbles]

Optional review for Midterm 1

Midterm 1: Feb 19 Monday 7:00pm9:00pm
(cover page ,
skillset)
Conflict: Feb 20 Tuesday 7:00pm9:00pm

6
Feb 1923 
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 26Mar 1 
Backtracking: independent set, longest
increasing subsequence
[scribbles]

Backtracking
[solutions]

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

Dynamic programming
[solutions]

8
Mar 48 
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 1115 
Spring break 
9
Mar 1822 
Graphs, basic search
[scribbles]

Graph modeling
[solutions]

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

Graph modeling
[solutions]

10
Mar 25Mar 29 
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 15 
Greedy algorithms
[scribbles]

Greedy
[solutions]

Optional review for Midterm 2
[scribbles]

Optional review for Midterm 2

Midterm 2: Apr 9 Tuesday 7:00pm9:00pm
(skillset)
Conflict: Apr 8 Monday 7:00pm9:00pm

12 Apr 812 
MST algorithms
[scribbles]

MST
[solutions]

Polynomialtime reductions
[scribbles]

Reductions
[solutions]

13
Apr 1519 
NP, NPcompleteness
[scribbles]

NPhardness proofs
[solutions]

More NPhardness reductions:
3SAT to independent set
[scribbles]

More NPhardness
[solutions]

14
Apr 2226 
More more NPcompleteness
[scribbles]

NPhardness: The final chapter
[solutions]

Undecidability: halting problem, diagonalization, reductions
[scribbles]

Undecidability via reductions
[solutions]

15
Apr 29May 3 
Wrapup and preliminary review for the final exam
[scribbles]

Review for final

Reading day 

Final Exam: May 9 Thursday 7:00pm10:00pm (skillset)
Conflict: TBA
