CS/ECE 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, slides, lecture videos, and lab handouts. Topics for future lectures and labs are subject to change; exam dates are not.

Videos for all lectures are automatically posted to a separate web page at most an hour after each lecture; it may take us a day or two to (manually) add links to the schedule below.

Lecture notes are tagged as follows:

Please let Jeff know if you find any of the bugs we'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.

Week Tuesday Lecture Wednesday Lab Thursday Lecture Friday Lab
Aug 22–26 Administrivia and course goals
Introduction and history; strings
[slides] [sorry, no video]
String induction
[induction notes] [solutions]
Languages and regular expressions
[slides] [video]
Regular expressions
[solutions]
Aug 29–Sep 2 DFAs: intuition, definitions, examples
[Automata Tutor] [slides] [audio]
DFA construction
[solutions]
DFAs: design techniques, product construction, operations on regular languages
[slides] [video]
DFA product construction
[solutions]
Sep 5–9 Proving nonregularity via fooling sets
Nondeterminism: intuition, examples, NFA definitions
[slides] [video]
Proving nonregularity
[solutions]
NFAs: ε-transitions, equivalence with DFAs and regular expressions
[slides] [video]
DFA/NFA transformation
[solutions]
Sep 12–16 Context-free languages and grammars
[slides] [video]
Context-free grammars
[solutions]
Turing machines: history, formal definitions, examples
[slides] [video]
Regular or not?
[solutions]
Sep 19–23 Turing machine variations: multiple tracks, heads, and tapes; doubly-infinite tape; subroutines; random-access memory
[slides] [video]
Turing machine design
[solutions]
Optional review for Midterm 1 Optional review for Midterm 1
Midterm 1 — Monday, September 26, 7–9pm
Conflict exam: Tuesday, September 27
Sep 26–30 Recursion: Hanoi, mergesort
[slides] [video]
Hint: Binary search
[solutions]
Divide and conquer: linear-time selection, Karatsuba multiplication
[recurrence notes] [slides] [video]
Divide and conquer
[solutions]
Oct 3–7 Backtracking: n queens, subset sum, longest increasing subsequence
[slides] [borked video]
Backtracking
[solutions]
Dynamic programming: Fibonacci, longest increasing subsequence
[slides] [video]
Dynamic programming
[solutions]
Oct 10–14 Sequence dynamic programming
[slides: pdf, note] [video]
More dynamic programming
[solutions]
Tree-shaped dynamic programming
[slides: pdf, note] [video]
Yet even still more dynamic programming
Drop deadline
[solutions]
Oct 13–21 Greedy algorithms: tape sorting, scheduling, exchange arguments
[slides] [video]
Which greedy algorithm?
[solutions]
Graphs: definitions, representations, data structures, traversal
[slides] [video]
Graph modeling
[solutions]
Oct 24–28 Depth-first search, topological sort
[slides] [video]
Topological sort
[solutions]
Strongly connected components
Greedy shortest paths: Dijkstra
[slides] [video]
Shortest paths
[solutions]
Oct 31–Nov 4 Shortest paths via dynamic programming: Shimbel-Moore-Bellman-Ford and Floyd-Roy-Kleene-Warshall
[slides] [video]
All-pairs shortest paths
[solutions]
Optional review for Midterm 2 Optional review for Midterm 2
Midterm 2 — Monday, November 7, 7–9pm
Conflict exam: Tuesday, November 8
Nov 7–11 P vs NP, NP-hardness, Cook-Levin Theorem
( Removing nondeterminism via dovetailing, proof of Cook-Levin)
[slides] [video]
Self-reductions
[solutions]
NP-hardness reductions: 3SAT, Independent Set, Clique, Vertex Cover
[slides] [video]
NP-hardness proofs
[solutions]
Nov 14–18 More NP-hardness reductions: 3-coloring, Hamiltonian cycle
[slides] [video]
More NP-hardness proofs
[solutions]
Approximation algorithms, hardness of approximation, unique games
[video]
Return of the Son of Beneath the Planet of the NP-Hardness Proofs, the Final Chapter, Part II, Section 27B/6
[solutions]
Nov 21–25 Thanksgiving break
Nov 29–Dec 2 Undecidability: halting problem, diagonalization, reductions
[slides] [video]
Undecidability via reductions
[solutions]
Undecidability: more reductions, Rice's theorem
ICES Forms
[slides] [video]
Using Rice's Theorem
ICES Forms
[solutions]
Dec 5–9 Wrap-up and preliminary review for the final exam Review for final
Final exam — Thursday, December 15, 7–10pm
Conflict exam: TBA