"CS 374": Lecture and Lab Schedule

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.

Lecture notes are tagged as follows:

Please let me know if you find any of the bugs I've cleverly hidden in the notes, especially the new () notes. Most of these bugs are just typos, but undoubtedly a few are actually quite serious. I will give extra credit to the first person to find each bug and describes how to fix it on the course's Piazza site.

videos for all lectures are automatically posted to a separate web page at most an hour after each lecture; it may take me a day or two to (manually) add links to the schedule below. Notes and videos from Jeff's Fall 2012 CS 473 lectures are also available. Lecture videos can be accessed directly from any on-campus computer; unfortunately, off-campus access requires an active UIUC NetID and password (after the first two weeks).

Topics for future lectures and labs are subject to change; exam dates are not.

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
Aug 25–29 Administrivia and course goals
Introduction and history [video]
Induction boilerplate ( induction notes) Strings, string functions, and languages [video] String induction
Sep 1–5 Regular expressions and context-free grammars [video] Regular expressions DFAs: definitions, examples, intuition [video] Context-free grammars
Sep 8–12 DFAs: design techniques, product construction, closure properties of regular languages [video] DFA construction Proving nonregularity via fooling sets
Nondeterminism: intuition, examples, NFA definitions [video]
Proving nonregularity
Sep 15–19 NFAs: ε-transitions, generalizations, equivalence with DFAs and regular expressions [video] Regular or not?
(End of Midterm 1 material)
Recursion: Hanoi, mergesort [video] Hint: binary search
Sep 22–26 Recursion: linear-time selection, Karatsuba multiplication [video]
( notes on recurrences)
Optional review for Midterm 1 Midterm 1, 7–9pm (No lecture)
[video of review session]
More recursion
Sep 29–Oct 3 Backtracking: n queens, subset sum, NFA acceptance, longest increasing subsequence [video] Backtracking Dynamic programming: Fibonacci, longest increasing subsequence [video] Dynamic programming
Oct 6–10 Dynamic programming: subset sum, NFA acceptance, edit distance [video] More dynamic programming Tree-like dynamic programming: Parsing context-free languages [video] Return of the son of revenge of dynamic programming, the final chapter, part III: Zatoichi versus Godzilla
Oct 13–17 Greedy algorithms: tape sorting, scheduling, exchange arguments [video] Which greedy algorithm? Graphs: definitions, representations, data structures, whatever-first search [video]/td> Graph modeling
Drop deadline
Oct 20–24 Depth-first search, topological sort [video] Graph modeling Minimum spanning trees: Borůvka and, if you absolutely insist, two others [video] Minimum spanning trees
Oct 27–31 Single-source shortest paths: Dijkstra, Bellman-Ford [video]
( All-pairs shortest paths: Floyd-Kleene-Warshall)
Shortest paths
(End of Midterm 2 material)
Turing machines: history, formal definitions, examples [video]
(See also Lenny's slides from last semester)
Turing machine design, costumes, candy
Nov 3–7 Turing machine variations: multiple tracks, heads, and tapes; doubly-infinite tape; subroutines; random-access memory [video]
(See also Lenny's slides from last semester)
Optional review for Midterm 2 Midterm 2, 7–9pm (No lecture)
[video of review session]
Wacky machine design
Nov 10–14 Nondeterminism, dovetailing [video]
(See also Lenny's slides from last semester)
deciding TM behavior P vs NP, NP-hardness, Cook-Levin Theorem, circuit and formula satisfiability [video]
( Proof of the Cook-Levin theorem)
Nov 17–21 NP-hardness reductions: 3SAT, Independent Set, Clique, Vertex Cover [video] NP-hardness proofs More NP-hardness reductions: 3-coloring, Hamiltonian cycle, international draughts [video] More NP-hardness proofs
Nov 24–28 Thanksgiving break
Dec 1–5 Undecidability: diagonalization, reductions, halting problem [video] Undecidability via reductions Undecidability: reductions again, Rice's theorem [video]
ICES Forms
Using Rice's Theorem
ICES Forms
Dec 8–12 Wrap-up — Any questions? [video] Review for final
Dec 15–19 Final exam: 7–10pm