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 18-22 |
Administrivia, strings, and languages
[slides], [string notes], [languages notes (sec. 2.1 & 2.2)] |
Preliminaries, strings, and induction
[lab work] [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 [lab work], [automatatutor] |
| Jan 25-29 |
DFAs: correctness proofs, lower bounds
[notes (sec. 3.3, 3.8)], [DFA proof notes] |
DFA proofs [lab work] | Nondeterminism: intuition, examples, NFA definitions, equivalence with DFAs [notes] |
NFA constructions
[lab work] |
| Feb 1-5 | Equivalence among NFAs, DFAs & Regular Expressions [notes (sec. 4.6, 4.8)] |
Regular expressions, DFAs, and NFAs
[lab work] |
Non-regularity [notes (sec. 3.8)], [Infinite Fooling Sets Guide] |
Regular or not?
[lab work] |
| Feb 8-12 |
Context-free grammars
[notes] |
Context-free grammars constructions
[lab work] |
Turing machines: history, definitions, examples, variations and extensions
[notes] |
Turing machine design
[lab work] (End of Midterm 1 material) |
| Feb 15-19 |
Turing machine variants and Church-Turing thesis
[notes], [CT notes] |
Church-Turing thesis
[lab work] |
Optional review for Midterm 1 (No lecture) | Optional review for Midterm 1 (No lab) |
| Feb 22 | Midterm 1, 7-8:30pm, Monday Feb 22 | |||
| Feb 22-26 |
Measuring Time, Invariance thesis, Divide and conquer: MergeSort
[notes] [slides] Jeff's [notes] on recurrences Chapter 2 of DPV book |
Merge Sort and Recurrences
[lab work] |
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
[lab work] |
| Feb 29-Mar 4 |
Backtracking, Intro to Dynamic Programming: Fibonacci
[notes] |
Backtracking
[lab work] |
Dynamic Programming: Longest Increasing Subsequence, String Splitting
[notes] Chapter 6 of DPV book |
Dynamic Programming
[lab work] |
| Mar 7-11 |
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]Drop deadline |
| Mar 14-18 |
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] (End of Midterm 2 material) |
| Mar 21-25 | Spring Break | |||
| Mar 29-Apr 1 |
BFS, Single-source shortest paths, Dijkstra
[notes] [slides] Chapter 4 of DPV book, Chapter 4 of KT book |
Shortest Paths
[lab work] |
Optional review for Midterm 2 (No lecture) | Optional review for Midterm 2 (No lab) |
| Apr 4 | Midterm 2, 7-8:30pm, Monday Apr 4 | |||
| Apr 4-8 |
Priority Queues, Bellman-Ford and Shortest Paths with negative lengths
[notes] [slides] Chapter 4 of DPV book, Chapter 6 of KT book |
Shortest paths with negative lengths
[lab work] |
All-pairs shortest paths, DFA to regular expressions, Minimum spanning tree algorithms
[notes] [slides] Chapter 5 of DPV book, Chapter 4 of KT book |
Minimum spanning trees
[lab work] |
| Apr 11-15 |
MST correctness, Decidability and recursive enumerability
[notes] [slideshow | pdf ] |
Closure properties
[lab work] |
Reductions, undecidability, and non r.e.-ness
[notes], [reduction notes] [slideshow | pdf ] |
Reductions, and undecidability
[lab work] |
| Apr 18-22 |
Polynomial-time Reductions [notes] | [slides] Chapter 8 of Kleinberg-Tardos |
P and NP
[lab work] |
NP-Completeness via Reductions
[notes] | [slides] Chapter 8 of Kleinberg-Tardos Video on P vs NP |
Reductions and NP-completeness
[lab work] |
| Apr 25-29 |
More hard problems, Cook-Levin theorem
[notes] [slides] Chapter 8 of Kleinberg-Tardos, Chapter 7 of Sipser |
NP-Completeness proofs
[lab work] |
NP-Completeness
[notes] [slides] |
More NP-Completeness
[lab work] ICES Forms |
| May 2-6 |
Wrapup: Tying up loose ends, and course overview
ICES Forms |
Review for final |
Reading Day
Office Hours (Mahesh) 11am to 12:15pm in 3405 Siebel |
Office Hours (Mahesh) 11:30am to 1pm in 4403 Siebel |
| May 9 | Final Exam: 8-11am on Monday, May 9 | |||