CS/ECE 374 A: 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.

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 any 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
Jan 15–19 Administrivia and course goals
Introduction and history; strings
[scribbles, my video]
String induction
[induction notes] [solutions]
Languages and regular expressions
[scribbles, my video]
Regular expressions
Jan 22–26 DFAs: intuition, definitions, examples
[Automata Tutor, JFLAP, scribbles, my video]
DFA construction
[Automata Tutor, JFLAP, solutions]
DFAs: product construction, closure properties, automatic=regular, fooling sets
[scribbles, my video]
DFA product construction
Jan 29–Feb 2 Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, my video]
Proving nonregularity
NFAs: ε-transitions, (most of) equivalence with DFAs and regular expressions
[scribbles, my video]
Regex to NFA to DFA (to regex)
Feb 5–9 Converting NFAs to regular expressions, language transformations
[scribbles, my video]
Language transformations
Context-free languages and grammars
scribbles, my video]
Context-free grammars
Feb 12–16 Turing machines
[scribbles, my video]
Language transformation formalism
Optional review for Midterm 1 [scribbles, my video] Optional review for Midterm 1
Midterm 1 — Monday, February 19, 7–9pm
Conflict exam: Tuesday, February 20
Feb 19–23 Recursion: Hanoi, mergesort Hint: Binary search Divide and conquer: Karatsuba multiplication, linear-time selection Fun with Karatsuba
Feb 26–Mar 2 Backtracking: n queens, subset sum, longest increasing subsequence Backtracking Dynamic programming: Fibonacci, longest increasing subsequence Dynamic programming
Mar 5–9 Sequence dynamic programming More dynamic programming Tree-shaped dynamic programming Yet even still more dynamic programming
Drop deadline
Mar 12–16 Greedy algorithms: tape sorting, scheduling, exchange arguments Which greedy algorithm? Graphs: definitions, representations, data structures, traversal Graph modeling
Mar 19–23 Spring break
Mar 26–30 Depth-first search, topological sort Topological sort Strongly connected components
Greedy shortest paths: Dijkstra
Shortest paths
Apr 2–6 Shortest paths via dynamic programming: Shimbel-Moore-Bellman-Ford and Floyd-Roy-Kleene-Warshall All-pairs shortest paths Optional review for Midterm 2 Optional review for Midterm 2
Midterm 2 — Monday, April 9, 7–9pm
Conflict exam: Tuesday, April 10
Apr 9–13 P vs NP, NP-hardness, Cook-Levin Theorem
( Removing nondeterminism via dovetailing, proof of Cook-Levin)
Self-reductions NP-hardness reductions: 3SAT, Independent Set, Clique, Vertex Cover NP-hardness proofs
Apr 16–20 More NP-hardness reductions: 3-coloring, Hamiltonian cycle More NP-hardness proofs [Slack] Return of the Son of Beneath the Planet of the NP-Hardness Proofs, the Final Chapter, Part II, Section 27B/6
Apr 23–27 Undecidability: halting problem, diagonalization, reductions Undecidability via reductions Undecidability: more reductions, Rice's theorem
ICES Forms
Using Rice's Theorem
Apr 30–May 4 Wrap-up and preliminary review for the final exam Review for final
Final exam — Tuesday, May 8, 8–11am
Conflict exam: TBA