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. (Lab solutions are posted after each lab ends; future solutions links are placeholders.) Future topics and lab handouts 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 23–27 Administrivia and course goals
Introduction; strings and induction
[scribbles, video]
String induction
[induction notes] [solutions]
Languages and regular expressions;
[scribbles, video]
Regular expressions
[solutions]
Aug 30—Sep 3 DFAs: intuition, definitions, examples
[scribbles, video]
DFAs
[Automata Tutor, JFLAP, solutions]
DFAs: product construction, closure properties, automatic=regular
[scribbles, video]
DFA product construction
[solutions]
Sep 6–10 Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, video]
[additional fooling set notes by Eric Huber]
Proving nonregularity
[solutions]
NFAs: ε-transitions, equivalence with DFAs
[scribbles, video]
Regex to NFA to DFA (to regex)
[solutions]
Sep 13–17 Converting regular expressions to NFAs, language transformations
[scribbles, video],
[language transformations walkthrough video pdf or notability]
Language transformations
[solutions]
Context-free languages and grammars
[
scribbles, video]
Context-free grammars
[solutions]
Sep 20–24 Turing machines TBA
[solutions]
Optional review for Midterm 1 Optional review for Midterm 1
Midterm 1 — Monday, September 27, 7:00–9:30pm
Conflict exam: Tuesday, September 28
Sep 27–Oct 1 Recursion: Hanoi, mergesort, quicksort Hint: Binary search
[solutions]
Divide and conquer: Karatsuba multiplication, linear-time selection Fun with Karatsuba
[solutions]
Oct 4–8 Backtracking: n queens, game trees, text segmentation Backtracking
[solutions]
Dynamic programming: Fibonacci, text segmentation again Dynamic programming
[solutions]
Oct 11–15 Sequence dynamic programming: Edit distance More dynamic programming
[solutions]
Tree-shaped dynamic programming: Optimal binary search trees Yet even still more dynamic programming
[solutions]
Drop deadline
Oct 18–22 Graphs: definitions, representations, data structures, traversal Graph modeling
[solutions]
Depth-first search, topological sort Topological sort
[solutions]
Oct 25–29 Dynamic programming in DAGs, strongly connected components
Generic shortest paths
Shortest paths
[solutions]
Shortest paths: BFS, DFS, Disjktra, Bellman-Ford, and (briefly) Floyd-Warshall All-pairs shortest paths
[solutions]
Nov 1–5 All-pairs shortest paths in detail More graph modeling
[solutions]
Optional review for Midterm 2 Optional review for Midterm 2
Midterm 2 — Monday, November 8, 7:00–9:30pm
Conflict exam: Tuesday, November 9
Nov 8–12 P vs NP, NP-hardness, Cook-Levin Theorem, Circuit SAT, 3SAT
( Removing nondeterminism via dovetailing, proof of Cook-Levin)
Self-reductions
[solutions]
NP-hardness reductions: Independent Set, Clique, Vertex Cover, 3-coloring NP-hardness proofs
[solutions]
Nov 15–19 More NP-hardness reductions: Hamiltonian cycle, choosing which problem to reduce from, international draughts More NP-hardness proofs
[solutions]
NP-hardness review Return of the Son of Revenge of the Planet of the NP-hardness Proofs, the Final Chapter, Part 4½: Zatoichi versus Godzilla
[solutions]
Nov 22–26 Thanksgiving break
Nov 29—Dec 3 Undecidability: code is data, the non-president's club, self-haters gonna self-hate, halting problem Undecidability via reductions
[solutions]
Undecidability: reductions and Rice's theorem Using Rice's Theorem
[solutions]
Dec 6–10 Wrap-up and final exam review Review for final exam
Final exam — Wednesday, December 15, 8am—11am
Conflict exam: TBA