1
Jan 14 18

Adminis+trivia
and course goals
Introduction and history;
strings
L1: [slides1,
slides2]
Scribbles:
A,
B.

String induction
[induction notes,
more]
[solutions]

Languages and regular
expressions
L2: [slides]
Scribbles:
A,
B.

Regular expressions
[solutions]

2
Jan 2125 
DFAs, product construction
[Automata Tutor]
DFA Proofs
L3: [slides]
Scribbles:
A,
B.

DFA construction
[solutions]

Nondeterminism, NFAs
Jeff's NFA notes
L4: [slides]
Scribbles:
A,
B.

DFA product construction
[solutions]

3
Jan 28
Feb 1 
NFAs continued, equivalence with DFAs and regular
expressions
Jeff's NFA notes
Converting NFA to regex
L5: [slides]
Scribbles:
A,
B.

DFA/NFA transformation
[solutions]

Proving nonregularity via fooling sets
[DFA Proofs]
[Fooling sets guide]
L6: [slides]
Scribbles:
A,
B.

Proving nonregularity
[solutions]

4
Feb 48 
Contextfree languages and grammars
L7: [slides]
Scribbles:
A,
B.

Contextfree grammars
[solutions]

Turing machines: history, formal definitions,
examples, variations
L8: [slides]
Scribbles:
A,
B.

Regular or not?
[solutions]

5
Feb 1115 
Halting and undecidability
L9: [slides]
Scribbles:
A,
B.

Turing machine design
[solutions]

Optional review for Midterm 1
Scribbles:
A,
B.

Optional review for Midterm 1

Skillset for midterm
1

Midterm 1: Monday, February 18, 79pm
(rooms)
Conflict: Gregory Hall,
213: Wednesday, February 20, 79pm.
Cover page

6
Feb 1822 
Recursion: Hanoi, mergesort
[slides][solving recurrences]
Scribbles:
A,
B.

Hint: Binary search
[solutions]

Divide and conquer: lineartime selection,
Karatsuba multiplication
[recurrence notes]
[slides]
Scribbles:
A,
B.

Divide and conquer
[solutions]

7
Feb 25
Mar 1 
Backtracking: independent set, longest
increasing subsequence
[slides]
Scribbles:
A,
B.

Backtracking
[solutions]

Dynamic programming: splitting strings,
longest increasing subsequence
[slides]
Scribbles:
A,
B.

Dynamic programming
[solutions]

8
Mar 48 
More DP: Edit Distance, MIS in trees
memoization and edit distance
[slides]
Scribbles:
A,
B.

More dynamic programming
[solutions]

CYK Algorithm,
Graphs, basic search
[CYK, Graph search slides]
Scribbles:
A,
B.

Yet even still more dynamic programming
Drop deadline
[solutions]

9
Mar 1115 
Directed graphs, depthfirst search
Scribbles:
A,
B.

Graph modeling
[solutions]

DFS/Strong connected compoments
[slides]
[Graph notes]
Scribbles:
A,
B.

Graph modeling
[solutions]

Mar 1624 
Don't give thanks, go on vacation anyway. 
10
Mar 25 29 
BFS and Shortest Paths
[slides]
Scribbles:
A,
B.

Shortest paths
[solutions]

Shortest Paths with Negative Lengths via DP
[slides]
Scribbles:
A,
B.

More shortest paths
[solutions]

11
Apr 15 
Greedy algorithms
[slides]
Scribbles:
A,
B.

Greedy
[solutions]

MST Algorithms
[slides]
Scribbles:
A,
B.

Fodder: Optional review for Midterm 2

Skillset for midterm
2

Midterm 2: Monday, April 8, 79pm
(rooms :
cover page :
solution)
Conflict exam: Wednesday, April 10, 79pm, Siebel 1404

12 Apr 812 
No lecture in lieu of midterm 
MST
[solutions]

Undecidability: halting problem, diagonalization, reductions
[slides]
Scribbles:
A,
B.

Undecidability via reductions
[solutions]

13
Apr 1519 
Polynomial time Reductions
[slides]
Scribbles:
A,
B.

Self Reductions
[solutions]

NP, NPCompleteness,
3SAT to Independent Set
[slides]
Scribbles:
A,
B.
[helpful video on P vs NP]

NPhardness proofs
[solutions] 
14
Apr 2226 
More NPhardness reductions: 3coloring, Hamiltonian cycle
[slides]

NPHardness, the final chapter
[solutions]

More more more NP Completeness.
[slides]
ICES Forms

Using Rice's Theorem
ICES Forms
[solutions]

15
Apr 29 May 3 
Wrapup and preliminary review for the final exam 
Review for final

Reading Day 

Skill
set for final

Final exam:
Monday May 6th, 1:30pm to 4:30pm (proof)
Conflict final: May 7th, 10am1pm, Siebel 1404.
