1
Jan 15-19
|
Administrivia
Introduction and history;
strings
[scribbles]
|
String induction
[more]
[solutions]
|
Languages and regular
expressions
[scribbles]
|
Regular expressions
[solutions]
|
2
Jan 22-26 |
DFAs
[scribbles]
|
DFA construction
[solutions]
|
DFA product construction
[scribbles]
|
DFA product construction
[solutions]
|
3
Jan 29-Feb 2 |
Non-determinism, 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 5-9 |
Proving non-regularity via fooling sets
[scribbles]
|
Proving non-regularity
[solutions]
|
Context-free languages and grammars
[scribbles]
|
Context-free grammars
[solutions]
|
5
Feb 12-16 |
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:00pm-9:00pm
(cover page ,
skillset)
Conflict: Feb 20 Tuesday 7:00pm-9:00pm
|
6
Feb 19-23 |
Recursion: Hanoi, mergesort
[scribbles]
[solving recurrences] [Big-O Notation]
|
Hint: Binary search
[solutions]
|
Divide and conquer: linear-time selection,
Karatsuba multiplication
[scribbles]
[recurrence notes]
|
Divide and conquer
[solutions]
|
7
Feb 26-Mar 1 |
Backtracking: independent set, longest
increasing subsequence
[scribbles]
|
Backtracking
[solutions]
|
Dynamic programming: splitting strings,
longest common subsequence
[scribbles]
|
Dynamic programming
[solutions]
|
8
Mar 4-8 |
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 11-15 |
Spring break |
9
Mar 18-22 |
Graphs, basic search
[scribbles]
|
Graph modeling
[solutions]
|
DFS, topological sort, and strong connected compoments
[scribbles]
|
Graph modeling
[solutions]
|
10
Mar 25-Mar 29 |
BFS and shortest paths
[scribbles]
|
Shortest paths
[solutions]
|
Shortest paths with negative lengths via DP
All-pairs shortest paths via DP
[scribbles]
|
More shortest paths
[solutions]
|
11
Apr 1-5 |
Greedy algorithms
[scribbles]
|
Greedy
[solutions]
|
Optional review for Midterm 2
[scribbles]
|
Optional review for Midterm 2
|
Midterm 2: Apr 9 Tuesday 7:00pm-9:00pm
(skillset)
Conflict: Apr 8 Monday 7:00pm-9:00pm
|
|---|
12
Apr 8-12 |
MST algorithms
[scribbles]
|
MST
[solutions]
|
Polynomial-time reductions
[scribbles]
|
Reductions
[solutions]
|
13
Apr 15-19 |
NP, NP-completeness
[scribbles]
|
NP-hardness proofs
[solutions]
|
More NP-hardness reductions:
3SAT to independent set
[scribbles]
|
More NP-hardness
[solutions]
|
14
Apr 22-26 |
More more NP-completeness
[scribbles]
|
NP-hardness: The final chapter
[solutions]
|
Undecidability: halting problem, diagonalization, reductions
[scribbles]
|
Undecidability via reductions
[solutions]
|
15
Apr 29-May 3 |
Wrap-up and preliminary review for the final exam
[scribbles]
|
Review for final
|
Reading day |
|
Final Exam: May 9 Thursday 7:00pm-10:00pm (skillset)
Conflict: TBA
|