The calendar below lists the topics of each lecture and lab section for the semester, with links to relevant lecture notes, lecture videos, and lab handouts.
Topics for future lectures and labs are subject to change; exam dates are not.
| Week | Tuesday Lecture | Wednesday Lab | Thursday Lecture | Friday Lab |
|---|---|---|---|---|
| Aug 24-28 |
Administrivia, course goals, introduction
[slides-part1] [slides-part2] |
Induction
[Induction notes] [lab work] More on induction |
Strings, languages, and regular expressions
[string notes], [languages & regular expressions notes] [slideshow | pdf ] |
String induction & regular expressions [lab work] |
| Aug 31–Sept 4 |
DFAs: definitions, examples, design, product construction
& closure properties
[notes] [slideshow | pdf ] |
DFA constructions [lab work] | Nondeterminism: intuition, examples, NFA definitions, equivalence with DFAs, ε-transitions [notes] [slideshow | pdf ] |
NFA constructions
[lab work] |
| Sept 7–11 | Equivalence among NFAs, DFAs & Regular Expressions, closure properties of regular languages [notes] [slideshow | pdf ] |
NFAs to DFAs
[lab work] |
Non-regularity [notes (sec. 3.8)] [slideshow | pdf ] |
Regular or not?
[lab work] |
| Sept 14-18 |
Context-free grammars
[notes] [slideshow | pdf ] |
Context-free grammars constructions
[lab work] (End of Midterm 1 material) |
Reductions, Recursion, Divide and Conquer, Sorting
[notes] [slides] Jeff's [notes] on recurrences Chapter 5 of KT book, Chapter 2 of DPV book |
Binary Search
[lab work] |
| Sept 21-25 |
Divide and Conquer: Linear-time selection, Karatsuba's Alg.
[notes] [slides] Jeff's [notes] on recurrences Chapter 5 of KT book, Chapter 2 of DPV book |
Divide and conquer
[lab work] |
Optional review for Midterm 1 (No lecture) | Optional review for Midterm 1 (No lab) |
| Sept 28 | Midterm 1, 7–9pm, Monday Sept 28 | |||
| Sept 28-Oct 2 |
Backtracking, Intro to Dynamic Programming: Fibonacci
[notes] [slides] |
Backtracking
[lab work] |
Dynamic Programming: Longest Increasing Subsequence, String splitting
[notes] [slides] Chapter 6 of KT book, Chapter 6 of DPV book |
Dynamic Programming
[lab work] |
| Oct 5-9 |
Dynamic Programming: Edit Distance, Max Independent Set in Trees
[notes] [slides] Chapter 6 of KT book, Chapter 6 of DPV book |
Dynamic Programming
[lab work] |
Greedy Algorithms: techniques, examples
[notes] [slides] Chapter 4 of KT book, Chapter 5 of DPV book |
Greedy Algorithms
[lab work] |
| Oct 12-16 |
Graph search
[notes] [slides] Chapter 3 of KT book, Chapter 3 of DPV book |
Graph modeling
[lab work] |
Directed graphs, Strong components, DAGs, Topological sort
[Notes] [slides] Chapter 3 of KT book, Chapter 3 of DPV book |
Directed graphs
[lab work] Drop deadline |
| Oct 19–23 |
BFS, Single-source shortest paths, Dijkstra
[notes] [slides] Chapter 4 of DPV book, Chapter 4 of KT book |
Shortest Paths
[lab work] |
Shortest Paths with negative lengths, DFA to Regexp
[notes] [slides] Chapter 4 of DPV book, Chapter 6 of KT book |
Shortest paths with negative lengths
[lab work] |
| Oct 26–30 |
Minimum spanning tree algorithms
[notes] [slides] Chapter 5 of DPV book, Chapter 4 of KT book |
Minimum spanning trees
[lab work] (End of Midterm 2 material) |
Turing machines: history, definitions, examples, variations and extensions
[notes] [slideshow | pdf ] |
Turing machine design
[lab work] |
| Nov 2-6 |
Multi-tape TM, Universal TM, RAM computer, Church-Turing thesis.
[notes] [slideshow | pdf ] |
More TM design
[lab work] |
Optional review for Midterm 2 (No lecture) | Optional review for Midterm 2 (No lab) |
| Nov 9 | Midterm 2, 7–9pm, Monday Nov 9 | |||
| Nov 9-13 |
Undecidability, reductions
[notes] [slideshow | pdf ] |
Undecidability, reductions
[lab work] |
P, NP
[notes] [slideshow | pdf ] |
NP, NP-completeness, coNP
[lab work] |
| Nov 16-20 |
Polynomial-time Reductions [notes] | [slides] Chapter 8 of Kleinberg-Tardos |
Reductions
[lab work] |
NP-Completeness via Reductions
[notes] | [slides] Chapter 8 of Kleinberg-Tardos Video on P vs NP |
NP-hardness proofs
[lab work] |
| Nov 23–27 | Thanksgiving Break | |||
| Nov 30 - Dec 4 |
More hard problems, Cook-Levin theorem
[notes] [slides] Chapter 8 of Kleinberg-Tardos, Chapter 7 of Sipser |
NP-Completeness proofs
[lab work] |
Undecidability: reductions again, Rice's theorem
[notes] [slides] ICES Forms |
Rice's Theorem, r.e. and non-r.e. languages
[lab work] ICES Forms |
| Dec 8-10 | Review for final | Review for final | Reading Day | |
| Dec 11-18 | Final Exam: 8-11am on Friday, Dec 11 | |||