Jan 25–29 
Administrivia and course goals
Introduction and history; strings
[Sariel's Videos, Lec 1]
[A: video, scribbles] [B: video, slides] 
String induction
[Jeff's induction notes, Chandra's induction notes] [solutions] 
Languages and regular expressions
[Sariel's Videos, Lec 2]
[A: video, scribbles] [B: video, slides, scribble] 
Regular expressions
[solutions] 
Feb 1–5 
DFAs: intuition, definitions, closure properties
[Automata Tutor, JFLAP, Mahesh's DFA notes, Sariel's Videos, Lec 3]
[A: video, scribbles][B: video, slides, scribble] 
DFA construction
[solutions] 
NonDeterminism, NFAs ✍
[Sariel's Videos, Lec 4]
[A: video, scribbles][B: video, slides, scribble] 
DFA product construction
[solutions] 
Feb 8–12 
Equivalence of DFAs, NFAs, and regular expressions
[Sariel's Videos, Lec 5]
[A: video, scribbles][B: video, slides, scribble] 
Regex to NFA to DFA (to Regex)
[solutions] 
Closure Properties: Language Transformations
[Patrick's Cycle(L) notes]
[A: video, scribbles][B: video, slides, scribble] 
Language Transformations
[solutions] 
Feb 15–19 
Fooling Sets and Proving NonRegularity
[Mahesh's DFA notes, Fall 2015 TAs' Fooling Sets Notes, Sariel's Videos, Lec 6]
[A: video, scribbles][B: video, slides, scribble] 
NO INSTRUCTION
(Campuswide break) 
Beyond Regularity: CFGs, PDAs, Turing Machines
[Sariel's Videos, Lec 7/8]
[A: video, scribbles][B: video, slides, scribble] 
Proving NonRegularity
[solutions] 
Feb 22–26 
Universal Turing machines
[Sariel's Videos, Lec 8]
[A: video, scribbles][B: video, slides, scribble] 
Turing Machines
[solutions] 
Optional review for Midterm 1
[A: video, scribbles][B: video, slides, scribble] 
Optional review for Midterm 1 
Midterm 1 – Monday, March 1 18:30–21:30 [Skill set]
Conflict exam: Tuesday, March 2 07:30–10:30 
Mar 1– 5 
Reductions & Recursion
[Sariel's Videos, Lec 10, Notes on Solving Recurrences]
[A: video, scribbles][B: video, slides, scribbles] 
Hint: Binary search
[solutions] 
Divide and conquer: Selection, Karatsuba
[Sariel's Videos, Lec 11]
[A: video, scribbles][B: video,slides, scribbles] 
Divide and Conquer
[solutions] 
Mar 8–12 
Backtracking
[Sariel's Videos, Lec 12]
[A: video, scribbles][B: video, slides, scribbles] 
Backtracking
[solutions] 
Dynamic programming
[Sariel's Videos, Lec 13]
[A: video, scribbles][B: video, slides, scribbles] 
Dynamic programming
[solutions] 
Mar 15–19 
More Dynamic programming
[Sariel's Videos, Lec 14]
[A: video, scribbles] [B: video, slides, scribbles] 
More Dynamic programming
[solutions] 
Even More DP, Graphs, Basic Search
[Chandra's Graph notes, Sariel's Videos, Lec 15]
[A: video, slides][B: video, slides, scribbles] 
Even more DP
[solutions]
Drop deadline 
Mar 22–26 
Directed Graphs, DFS, DAGs and Topological Sort
[Chandra's Graph notes, Sariel's Videos, Lec 16]
[A: video, slides, scribbles] [B: video, slides, scribbles] 
NO INSTRUCTION
(Campuswide break) 
More Directed Graphs: DFS again, SCCs
[A: video, slides, scribbles] [B: video, slides, scribbles] 
Graph Modeling
[solutions] 
Mar 29–Apr 2 
Shortest Paths: BFS and Dijkstra
[Chandra's Graph notes, Sariel's Videos, Lec 17]
[A: video, slides, scribbles][B: video, slides, scribbles]

More Graph Modeling
[solutions] 
Shortest paths: BellmanFord, Dynamic Programming on DAGs
[Chandra's Graph notes, Sariel's Videos, Lec 18]
[A: video, slides, scribbles] [B: video, slides, scribbles] 
Shortest Paths
[solutions] 
Apr 5–9 
Catch up lecture
[A: video, scribbles] [B: video, slides, scribbles]

More Shortest Paths
[solutions] 
Optional review for Midterm 2
[A: video][B: video, slides, scribble] 
Optional review for Midterm 2 
Midterm 2 – Monday, April 12 18:30–21:30 [Skill set]
Conflict exam: Monday, April 12 07:30–10:30 and 20:30–23:30 
Apr 12–16 
NO INSTRUCTION
(Campuswide break) 
NO INSTRUCTION
(Campuswide break on Tues) 
Reductions
[Sariel's Videos, Lec 21]
[A: video, slides] [B: video, slides, scribbles]

Reductions
[solutions] 
Apr 19–23 
Undecidability
[Sariel's Videos, Lec 9]
[A: video, slides] [B: video, slides, scribbles] 
Undecidability reductions
[solutions] 
SAT, NP and NPHardness
[Sariel's Videos, Lec 2224]
[A: video, slides] [B: video, slides, scribbles] 
NPhardness reductions
[solutions]
ICES Forms Released 
Apr 2630 
More NPHardness
[Sariel's Videos, Lec 2324]
[A: video, slides] [B: video, slides, scribbles] 
More NPHardness
[solutions] 
Catch up lecture
[A: video, slides] [B: video, slides, scribbles] 
No Lab 
May 37 
Wrapup, closing remarks
Optional review for Final Exam
[A: video, slides] [B: video, slides, scribbles] 
Optional Review for final exam
Drop Deadline 
Reading Day
ICES Forms Due 

Final Exam – Monday, May 10 08:00–11:00 [Skill set]
Conflict exam: Monday, May 10 19:00–22:00 