1
Jan 17-21
|
Administrivia
Introduction and history;
strings
[scribbles]
|
String induction
[more]
[solutions]
|
Languages and regular
expressions
[scribbles]
|
Regular expressions
[solutions]
|
2
Jan 24-28 |
DFAs
[scribbles]
|
DFA construction
[solutions]
|
DFA product construction
[scribbles]
|
DFA product construction
[solutions]
|
3
Jan 31-Feb 4 |
Non-determinism, 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 7-11 |
Proving non-regularity via fooling sets
[scribbles]
|
Proving non-regularity
[solutions]
|
Context-free languages and grammars
[scribbles]
|
Context-free grammars
[solutions]
|
5
Feb 14-18 |
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:00pm-9:30pm
Conflict: Feb 22 Tuesday 7:00pm-9:30pm
|
6
Feb 21-25 |
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 28-Mar 4 |
Backtracking: independent set, longest
increasing subsequence
[scribbles]
|
Backtracking
[solutions]
|
Dynamic programming: splitting strings,
longest common subsequence
[scribbles]
|
Dynamic programming
[solutions]
|
8
Mar 7-11 |
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 14-18 |
Spring break |
9
Mar 21-25 |
Graphs, basic search
[scribbles]
|
Graph modeling
[solutions]
|
DFS, topological sort, and strong connected compoments
[scribbles]
|
Graph modeling
[solutions]
|
10
Mar 28-Apr 1 |
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 4-8 |
Greedy algorithms
[scribbles]
|
Greedy
[solutions]
|
Optional review for Midterm 2
[scribbles]
|
Optional review for Midterm 2
|
Midterm 2: Apr 11 Monday 7:00pm-9:30pm
Conflict: Apr 12 Tuesday 7:00pm-9:30pm
|
|---|
12
Apr 11-15 |
MST algorithms
[scribbles]
|
MST
[solutions]
|
Polynomial-time reductions
[scribbles]
|
Reductions
[solutions]
|
13
Apr 18-22 |
NP, NP-completeness,
3SAT to independent set
[scribbles]
|
NP-hardness proofs
[solutions]
|
More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[scribbles]
|
More NP-hardness
[solutions]
|
14
Apr 25-29 |
More more NP-completeness
[scribbles]
[slides (3-coloring, Hamiltonian cycle, etc.)]
|
NP-hardness: The final chapter
[solutions]
|
Undecidability: halting problem, diagonalization, reductions
[scribbles]
|
Undecidability via reductions
[solutions]
|
15
May 2-6 |
Wrap-up and preliminary review for the final exam
[scribbles]
|
Review for final
|
Reading day |
|
| Final exam: May 12 Thursday 8:00am-11:00am
|