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 |
---|---|---|---|---|
Jan 19-23 |
Administrivia, course goals, introduction
[notes] [slides-part1] [slides-part2] |
Induction
[Induction notes] [lab work] |
Strings, languages, and regular expressions
[string notes], [languages & regular expressions notes] [slides] |
String induction & regular expressions [lab work] |
Jan 26–30 |
DFAs: definitions, examples, design, product construction
& closure properties
[notes] [slides] |
DFA constructions [lab work] |
Nondeterminism: intuition, examples, NFA definitions, ε-transitions,
equivalence with DFAs
[notes] [slides] |
NFA constructions
[lab work] |
Feb 2–6 |
Regular expressions equivalence with NFAs, DFAs, closure properties of
regular languages
[notes] [NFA slides] [regular expressions and automata] [clsoure properties] |
NFAs to DFAs
[lab work] |
Non-regularity
[notes (sec. 3.8)] [slides] |
Regular or not?
[lab work] |
Feb 9-13 |
Context-free grammars
[notes] [slides] |
Context-free grammars constructions
[lab work] (End of Midterm 1 material) |
Graphs: representation, search, DFS
[notes] [slides] |
Graph modeling
[lab work] |
Feb 16-20 | Optional review for Midterm 1 (No lecture) | Midterm 1, 7–9pm (No lab) |
Directed graphs, Strong components, DAGs, Topological sort
[notes] [slides] |
Directed graphs
[lab work] |
Feb 23-27 |
BFS, Single-source shortest paths, Dijkstra
[notes] [slides] |
Shortest Paths
[lab work] |
Reductions, Recursion, Divide and Conquer, Sorting
[notes] [slides] |
Binary Search
[lab work] |
Mar 2–6 |
Divide and Conquer contd: Linear-time selection, Binary Search
[notes] [slides] Jeff's notes on recurrences |
Divide and conquer
[lab work] |
Backtracking, Intro to Dynamic Programming: Fibonacci
[notes] [slides] |
Backtracking
[lab work] |
Mar 9–13 |
Dynamic Programming: Longest Increasing Subsequence, Interval Scheduling
[notes] [slides] |
Dynamic Programming
[lab work] |
Dynamic Programming: Max Independent Set in Trees, Edit Distance
[notes] [slides] |
Dynamic Programming
[lab work] Drop deadline |
Mar 16–20 |
More Dynamic Programming: Shortest Paths, DFA to Regexp
[notes] [slides] |
Dynamic Programming
[lab work] |
Greedy Algorithms: techniques, examples
[notes] [slides] |
Greedy Algorithms
[lab work] |
Mar 23–27 | Spring Break | |||
Mar 30–Apr 3 |
Minimum spanning tree algorithms
[notes] [slides] |
Minimum spanning trees
[lab work] (End of Midterm 2 material) |
Turing machines: history, definitions, examples, variations and extensions
[notes] [slides] |
Turing machine design
[lab work] |
Apr 6–10 | Optional review for Midterm 2 (No lecture) | Midterm 2, 7–9pm (No lab) |
Universal Turing machine, RAM computer, Church-Turing thesis.
Intro Decidability.
[notes] [slides:Universal TM] [slides:Intro Decidability] |
More TM design
[lab work] |
Apr 13–17 |
Time-bounded TMs, complexity classes, Nondeterminism, P and NP
[notes] [slides: Complexity] [slides: Nondeterminism] |
Closure properties
[lab work] |
NP, Polynomial-time reductions
[notes] [slides] |
Reductions
[lab work] |
Apr 20–24 |
NP-Completeness, 3SAT to Independent Set, Hamiltonian Cycle [notes] [slides] Video on P vs NP |
NP-hardness proofs
[lab work] |
3SAT to 3-Color, Proof of Cook-Levin Theorem
[notes] [slides] |
More NP-hardness proofs
[lab work] |
Apr 27 - May 1 |
Undecidability: reductions again, Rice's theorem
[notes] [slides] |
Undecidability via reductions
[lab work] |
Recursive enumerability and beyond
[notes] [slides] ICES Forms |
Rice's Theorem, r.e. and non-r.e. languages
[lab work] ICES Forms |
May 4-8 | Wrap-up — Any questions? | Review for final | Reading Day | Final exam: 7pm - 10pm |
May 11-15 | Party Time! |