CS/ECE 374 - Schedule, Notes, and Handouts

CS/ECE 374: 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 videos are available at Echo360 site and requires university credentials to login.

Week	Tuesday Lecture	Wednesday Lab	Thursday Lecture	Friday Lab
Aug 28-31	Adminis trivia and course goals Notes on strings [sect A: slides1, slides2] [sect B: slides1, slides2]	String induction [Jeff's induction notes, Chandra's additional notes] [solutions]	Languages and regular expressions [sec A slides, sect B slides]	Regular expressions [solutions]
Sep 4-7	DFAs, product construction [Automata Tutor] [sec A slides] [sec B slides] DFA Proofs	DFA construction [solutions]	Non-determinism, NFAs Jeff's NFA notes [sec A slides] [sec B slides]	DFA product construction [solutions]
Sep 11-14	NFAs continued, equivalence with DFAs and regular expressions Jeff's NFA notes [sec A slides sec B slides]	DFA/NFA transformation [solutions]	Proving non-regularity via fooling sets [slides] [DFA Proofs][Fooling sets guide]	Proving nonregularity [solutions]
Sep 18-21	Context-free languages and grammars [slides: secA, secB]	Context-free grammars [solutions]	Turing machines: history, formal definitions, examples, variations [slides]	Regular or not? [solutions]
Sep 25-28	Universal Turing Machine, RAM simulation, P [UTM slides][complexity slides]	Turing machine design [solutions]	SecA Optional review for Midterm 1 Sec B Recursion: Hanoi, mergesort (see Oct 2 links) sec B slides	Optional review for Midterm 1
Midterm 1: Monday, October 1, 7-9:30pm
Oct 2-5	Sec A: Recursion: Hanoi, mergesort Sec B: no lecture [slides][solving recurrences]	Hint: Binary search [solutions]	Divide and conquer: linear-time selection, Karatsuba multiplication [recurrence notes] [slides]	Divide and conquer [solutions]
Oct 9-12	Backtracking: independent set, longest increasing subsequence [sec A slides sec B notebook]	Backtracking [solutions]	Dynamic programming: splitting strings, longest increasing subsequence [slides sec B notebook]	Dynamic programming [solutions]
Oct 16-19	More DP: Edit Distance, MIS in trees [slides]	More dynamic programming [solutions]	CYK Algorithm, Graphs, basic search [CYK slides, Graph search slides]	Yet even still more dynamic programming Drop deadline [solutions]
Oct 23-26	Directed graphs, depth-first search [slides]	Graph modeling [solutions]	Catch up lecture [Graph notes]	Graph modeling [solutions]
Oct 30 - Nov 2	BFS and Shortest Paths [slides]	Shortest paths [solutions]	Shortest Paths with Negative Lengths via DP [slides]	More shortest paths [solutions]
Nov 6-9	MST Algorithms [Kent's slides], [slides]	MST [solutions]	Optional review for midterm 2 [sec B sketches]	Optional review for Midterm 2
Midterm 2: Monday, November 12, 7-9:30pm Conflict exam: Tuesday, Nove 13
Nov 13-16	Greedy algorithms [slides]	Greedy [solutions]	Undecidability: halting problem, diagonalization, reductions [slides]	Undecidability via reductions [solutions]
Nov 20-23	Fall break
Nov 27-30	Polynomial time Reductions [slides]	Self Reductions [solutions]	NP, NP-Completeness, 3SAT to Independent Set [slides][helpful video on P vs NP]	NP-hardness proofs [solutions]
Dec 4-7	More NP-hardness reductions: 3-coloring, Hamiltonian cycle [slides]	NP-Hardness, the final chapter [solutions]	Undecidability: more reductions, Rice's theorem [slides] ICES Forms	Using Rice's Theorem ICES Forms [solutions]
Dec 11-14	No lecture, review session Thursday	Review for final	Review session: 7pm, ECEB 1002
Final exam: Saturday, Dec 15, 1:30-4:30 p.m.