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
[scribbles, video]
More language transformations
[solutions]
Optional review for Midterm 1
[practice midterm, Dakshita's solutions, Jeff's solutions, video]
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
[scribbles, video]
Hint: Binary search
[solutions]
Divide and conquer: Karatsuba multiplication, linear-time selection [scribbles, video] Fun with Karatsuba
[solutions]
Oct 4–8 Backtracking: n queens, game trees, text segmentation [scribbles, video] Backtracking
[solutions]
Dynamic programming: Fibonacci, text segmentation again [scribbles, video] Dynamic programming
[solutions]
Oct 11–15 Sequence dynamic programming: Edit distance [scribbles, video] More dynamic programming
[solutions]
Tree-shaped dynamic programming: Optimal binary search trees [scribbles, video] Yet even still more dynamic programming
[solutions]
Drop deadline
Oct 18–22 Graphs: definitions, representations, data structures, traversal [scribbles, video] Graph modeling
[solutions]
Depth-first search, topological sort [scribbles, video] Topological sort
[solutions]
Oct 25–29 Dynamic programming in DAGs, strongly connected components
Generic shortest paths [scribbles, video]
Shortest paths
[solutions]
Shortest paths: BFS, DFS, Disjktra, Bellman-Ford, and (briefly) Floyd-Warshall [scribbles, video] All-pairs shortest paths
[solutions]
Nov 1–5 All-pairs shortest paths in detail [scribbles, video] Solve it both ways
[solutions]
Optional review for Midterm 2
[
practice midterm, Jeff's solutions, video]
Optional review for Midterm 2
Midterm 2 — Monday, November 8, 7:00–9:30pm
Conflict exam: Tuesday, November 9
Nov 8–12 Reductions, hardness [scribbles, video] Reductions
[solutions]
P vs NP, NP-hardness, NP-hardness reductions: 3SAT, Clique [scribbles, video] NP-hardness proofs
[solutions]
Nov 15–19 More NP-hardness: 3 Coloring, Hamiltonian cycle [scribbles, video] More NP-hardness proofs
[solutions]
Hamiltonian Cycle wrap-up, Hamiltonian path, other NP hard problems, NP-hardness review [scribbles, video] Even more NP-hardness proofs
[solutions]
Nov 22–26 Thanksgiving break
Nov 29–Dec 3 NP Hardness examples, Undecidability: code is data, the halting problem
[scribbles, video]
ICES forms available
Yet even still more NP-hardness examples
[solutions]
Undecidability: reductions and Rice's theorem
[scribbles, video, skipped lab on undecidability reductions, skipped lab solutions
Using Rice's Theorem
[solutions]
Dec 6–10 Wrap-up and final exam review [scribbles, video] Review for final exam
ICES deadline
Final exam — Wednesday, December 15, 8am—11am
Conflict exam: TBA