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 typeset notes, scribbles, and video for each lecture, as well as problem handouts and solutions for each lab. Future lecture topics are subject to change. Exam dates are not.

Textbook chapters or lecture notes are available for each lecture, and problem handouts are available for each lab. (Solution links for future labs are just placeholders.) Stars ★ indicate materials that have been updated or revised this semester. Hearts ♥ indicate more advanced material (not covered in class and not appearing in any homework or exam).

If you find any of the bugs we've cleverly hidden in the lecture materials, please open a new issue on bug-tracking site for Jeff's textbook and post a description of the error to Piazza; I will give extra credit to the first person to find each bug and describe how to fix it.

Week	Tuesday Lecture	Wednesday Lab	Thursday Lecture	Friday Lab
Aug 26–30	Adminis trivia and course goals Introduction and history; strings [scribbles, my video]	String induction [induction notes] [solutions]	String induction, Languages and regular expressions [scribbles, my video]	Regular expressions [solutions]
Sep 2–6	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 [solutions]
Sep 9–13	Proving nonregularity via fooling sets NFAs: intuition and examples [scribbles, Echo360 video]	Proving nonregularity [solutions]	NFAs: ε-transitions, (most of) equivalence with DFAs and regular expressions [scribbles, my video]	Regex to NFA to DFA (to regex) [solutions]
Sep 16–20	Converting NFAs to regular expressions, language transformations [Chandra's slides]	Language transformations [solutions]	Context-free languages and grammars [Ian's slides]	Context-free grammars [solutions]
Sep 23–27	Turing machines [scribbles, my video]	Language transformation formalism [solutions]	Optional review for Midterm 1 [fake midterm, scribbles, my video]	Optional review for Midterm 1
Midterm 1 — Monday, September 30, 7–9pm Conflict exam: Tuesday, October 1
Sep 30–Oct 4	Recursion: Hanoi, mergesort, quicksort [scribbles, my video]	Hint: Binary search [solutions]	Divide and conquer: Karatsuba multiplication, linear-time selection [scribbles, my video]	Fun with Karatsuba [solutions]
Oct 7–11	Backtracking: n queens, game trees, text segmentation [scribbles, my video]	Backtracking [solutions]	Dynamic programming: Fibonacci, text segmentation again [scribbles, my video]	Dynamic programming [solutions]
Oct 14–18	Sequence dynamic programming: Edit distance [scribbles, my video]	More dynamic programming [solutions]	Tree-shaped dynamic programming: Optimal binary search trees [scribbles, my video]	Yet even still more dynamic programming [solutions] Drop deadline
Oct 21–25	Graphs: definitions, representations, data structures, traversal [scribbles, my video]	Graph modeling [solutions]	Depth-first search, topological sort [scribbles, my video]	Topological sort [solutions]
Oct 28–Nov 1	Dynamic programming in DAGs, strongly connected components Generic shortest paths [scribbles, my video]	Shortest paths [solutions]	Shortest paths: BFS, DFS, Disjktra, Bellman-Ford, and (briefly) Floyd-Warshall [scribbles, my video]	All-pairs shortest paths [solutions]
Nov 4–8	All-pairs shortest paths in detail [scribbles, my video]	More graph modeling [solutions]	Optional review for Midterm 2 [fake midterm, scribbles, my video, extra video for problem 4]	Optional review for Midterm 2
Midterm 2 — Monday, November 11, 7–9pm Conflict exam: Tuesday, November 12
Nov 11–15	P vs NP, NP-hardness, Cook-Levin Theorem, Circuit SAT, 3SAT (♥ Removing nondeterminism via dovetailing, proof of Cook-Levin) [blackboard, Echo360 video]	Self-reductions [solutions]	NP-hardness reductions: Independent Set, Clique, Vertex Cover, 3-coloring [scribbles, my video]	NP-hardness proofs [solutions]
Nov 18–22	More NP-hardness reductions: Hamiltonian cycle, choosing which problem to reduce from, international draughts [scribbles, my video]	More NP-hardness proofs [solutions]	NP-hardness review [scribbles, my video]	Return of the Son of Revenge of the Planet of the NP-hardness Proofs, the Final Chapter, Part 4½: Zatoichi versus Godzilla [solutions]
Nov 25–29	Thanksgiving break
Dec 2–6	Undecidability: code is data, the non-president's club, self-haters gonna self-hate, halting problem [scribbles, my video] <	Undecidability via reductions [solutions]	Undecidability: reductions and Rice's theorem ICES Forms [scribbles, my video]	Using Rice's Theorem [solutions] TA ICES Forms
Dec 9–13	Wrap-up and final exam review [scribbles, my video]	Review for final exam		Final Exam
Final exam — Friday, December 13, 8am–11am Conflict exam: TBA