The calendar below lists the topics of each lecture and lab section for the semester, with links to relevant lecture notes, 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 |
|---|---|---|---|---|
| Jan 15-19 |
Administrivia, strings, and languages
[slides], [string notes], [languages notes (sec. 2.1 & 2.2)] |
Preliminaries, Strings, and Languages
[Induction notes] [More induction notes] |
Regular expressions and Introduction to DFAs
[regular expressions notes], [DFA notes (upto sec. 3.5.3)] |
Regular expressions and DFA design, [automatatutor] |
| Jan 22-26 |
DFAs: correctness proofs, lower bounds
[notes (sec. 3.3, 3.8)], [DFA proof notes] |
DFA proofs | Nondeterminism: intuition, examples, NFA definitions, equivalence with DFAs [notes] | NFA constructions |
| Jan 29-Feb 2 | Equivalence among NFAs, DFAs & Regular Expressions [notes (sec. 4.6, 4.8)] | Regular expressions, DFAs, and NFAs | Non-regularity [notes (sec. 3.8)], [Infinite Fooling Sets Guide] | Regular or not? |
| Feb 5-9 |
Context-free grammars
[notes] |
Context-free grammars constructions |
Turing machines: history, definitions, examples, variations and extensions
[notes] |
Turing machine design |
| Feb 12-16 |
Turing machine variants and Church-Turing thesis
[notes], [CT notes] |
Church-Turing thesis | Optional review for Midterm 1 (No lecture) | Optional review for Midterm 1 (No lab) |
| Midterm 1, Monday Feb 19, 7-9pm
Conflict Midterm: Tuesday Feb 20 |
||||
| Feb 19-23 |
Measuring Time, Invariance thesis, Divide and conquer: MergeSort
[notes] [slides] Jeff's [notes] on recurrences Chapter 2 of DPV book |
Merge Sort and Recurrences |
Divide and Conquer: Recurrences, Quick sort, Karatsuba's algorithm, Linear selection
[notes] [slides] Jeff's [notes] on recurrences Chapter 2 of DPV book |
Binary Search |
| Feb 26-Mar 2 |
Linear Selection and Backtracking
[notes] |
Backtracking |
Dynamic Programming: Longest Increasing Subsequence, String Splitting
[notes] Chapter 6 of DPV book |
Dynamic Programming |
| Mar 5-9 |
Dynamic Programming: Edit Distance, Max Independent Set in Trees
[notes] Chapter 6 of KT book, Chapter 6 of DPV book |
Dynamic Programming |
Greedy Algorithms: techniques, examples
[notes] Chapter 4 of KT book, Chapter 5 of DPV book |
Greedy Algorithms Drop deadline |
| Mar 12-16 |
Graph search
[notes] Chapter 3 of KT book, Chapter 3 of DPV book |
Graph modeling |
Directed graphs, Strong components, DAGs, Topological sort
[Notes] [slides] Chapter 3 of KT book, Chapter 3 of DPV book |
Directed graphs |
| Mar 19-23 | Spring Break | |||
| Mar 26-30 |
BFS, Single-source shortest paths, Dijkstra, Priority Queues
[notes] [slides] Chapter 4 of DPV book, Chapter 4 of KT book |
Shortest Paths |
Bellman-Ford and Shortest Paths with negative lengths, All pairs Shortest Paths
[notes] [slides] Chapter 4 of DPV book, Chapter 6 of KT book |
Shortest paths with negative lengths |
| Apr 2-6 |
DFA to regular expressions, Minimum spanning tree algorithms
[APSP notes] [MST notes] [slides] Chapter 5 of DPV book, Chapter 4 of KT book |
Minimum spanning trees | Optional review for Midterm 2 (No lecture) | Optional review for Midterm 2 (No lab) |
| Midterm 2 — Monday, April 9, 7–9pm
Conflict exam: Tuesday, April 10 |
||||
| Apr 9-13 |
Decidability, recursive enumerability, non-r.e.-ness, undecidability
[notes] [slideshow | pdf ] |
Closure properties |
Many-one Reductions
[reduction notes] [slideshow | pdf ] |
Reductions, and undecidability |
| Apr 16-20 |
P and NP [notes] | [slides] Chapter 8 of Kleinberg-Tardos |
P and NP |
Polynomial Time Reductions
[notes] | [slides] Chapter 8 of Kleinberg-Tardos Video on P vs NP |
Polynomial time Reductions |
| Apr 23-27 |
NP-completeness and Cook-Levin theorem
[notes] [slides] Chapter 8 of Kleinberg-Tardos, Chapter 7 of Sipser |
NP-Completeness proofs |
More NP-Completeness
[notes] [slides] |
More NP-Completeness
ICES Forms |
| Apr 30-May 4 |
Wrapup: Tying up loose ends, and course overview
ICES Forms |
Review for final | Reading Day | |
| Final exam — Tuesday, May 8, 8--11am
Conflict exam: Monday, May 7, 8--11am, in 3401 Siebel |
||||