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.

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
[solutions]
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
[solutions]
Jan 29–Feb 2 Proving nonregularity via fooling sets
NFAs: intuition and examples
[scribbles, my 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]
Feb 5–9 Converting NFAs to regular expressions, language transformations
[scribbles, my video]
Language transformations
[solutions]
Context-free languages and grammars
[
scribbles, my video]
Context-free grammars
[solutions]
Feb 12–16 Turing machines
[scribbles, my video]
Language transformation formalism
[solutions]
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
[scribbles, my video]
Hint: Binary search
[solutions]
Divide and conquer: Karatsuba multiplication, linear-time selection [scribbles, Echo video] Fun with Karatsuba
[solutions]
Feb 26–Mar 2 Backtracking: n queens, game trees, text segmentation
[scribbles, my video]
Backtracking
[solutions, scribbles, video: intro, #1, #1 again, #2, #3]
Dynamic programming: Fibonacci, text segmentation again
[scribbles, my video]
Dynamic programming
[solutions, scribbles, video: #1, #1 again, #2, #3, #5]
Mar 5–9 Sequence dynamic programming: Edit distance
[scribbles, my video]
More dynamic programming
[solutions, scribbles, video: #1, #2, #3]
Tree-shaped dynamic programming: Optimal binary search trees
[scribbles, my video]
Yet even still more dynamic programming
[solutions, scribbles, video: #1, #2a, #2b]
Mar 12–16 Graphs: definitions, representations, data structures, traversal
[scribbles, my video]
Graph modeling
[solutions]
Depth-first search, topological sort
[scribbles, my video]
Topological sort
[solutions]
Drop deadline
Mar 19–23 Spring break
Mar 26–30 Strongly connected components
Greedy shortest paths: Dijkstra
[scribbles, my video]
Shortest paths
[solutions]
Shortest paths via dynamic programming: Shimbel-Moore-Bellman-Ford and Roy-Kleene-Floyd-Warshall
[scribbles, my video]
All-pairs shortest paths
[solutions]
Apr 2–6 Minimum spanning trees
[scribbles, my video]
More graph modeling
[solutions]
Optional review for Midterm 2
[
scribbles, my video]
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, Circuit SAT, 3SAT, Independent Set
( Removing nondeterminism via dovetailing, proof of Cook-Levin)
[scribbles, my video]
Self-reductions
[solutions]
NP-hardness reductions: Clique, Vertex Cover, 3-coloring, Hamiltonian cycle
[scribbles, my video]
NP-hardness proofs
[solutions]
Apr 16–20 More NP-hardness reductions: Hamiltonian cycle again, Super Mario Bros, international draughts
[scribbles, my video]
More NP-hardness proofs
[solutions]
Undecidability: code is data, the non-president's club, diagonalization, self-haters gonna self-hate, halting problem
[scribbles, my video: #1 #2]
Undecidability via reductions
[solutions]
Apr 23–27 Undecidability: reductions, Rice's theorem
[scribbles, my video]
Using Rice's Theorem
[solutions]
Undecidability: Proof of Rice's theorem
Universal models of computation
[scribbles, my video]
ICES Forms
More undecidability
[solutions]
TA ICES Forms
Apr 30–May 4 Wrap-up and Q&A Review for final
Final exam — Tuesday, May 8, 8–11am
Conflict exam: TBA