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.

Videos for all lectures are automatically posted to a separate web page shortly after lecture. They will not be added to the schedule page below.

Week	Tuesday Lecture	Wednesday Lab	Thursday Lecture	Friday Lab
Jan 21-24	Adminis trivia, course goals, Strings and Languages Notes on strings [slides1, slides2]	String induction [Jeff's induction notes, Chandra's additional notes] [solutions]	Languages and regular expressions [slides]	Regular expressions [solutions]
Jan 28-31	DFAs, product construction [Automata Tutor] [slides] DFA Proofs	DFA construction [solutions]	Non-determinism, NFAs Jeff's NFA notes [slides] [scribbles]	DFA product construction [solutions]
Feb 4-7	NFAs continued, equivalence with DFAs and regular expressions Jeff's NFA notes [slides] [scribbles]	NFAs [solutions]	Proving non-regularity via fooling sets [slides][Fooling sets notes][Fooling sets guide]	Language transformations [solutions]
Feb 11-14	Context-free languages and grammars [slides]	Proving non-regularity [solutions]	Turing machines: history, formal definitions, examples, variations [slides]	Context free languages [solutions]
Feb 18-21	Universal Turing Machine, RAM simulation, P [UTM slides][complexity slides]	Turing machine design [solutions]	Optional review for Midterm 1 Fodder for exam preparation	Regular or not and Fodder [solutions]
Midterm 1: Monday, Feb 24, 7-9:30pm (Syllabus/Skillset)
Feb 25-28	Recursion: Hanoi, mergesort [slides][solving recurrences]	Hint: Binary search [solutions]	Divide and conquer: linear-time selection, Karatsuba multiplication [recurrence notes] [slides]	Divide and conquer [solutions]
Mar 4-7	Backtracking: independent set, longest increasing subsequence [slides ]	Backtracking [solutions]	Dynamic programming: splitting strings, longest increasing subsequence [slides]	Dynamic programming [solutions]
Mar 11-14	More DP: Edit Distance, MIS in trees [slides] [CYK slides] [CYK Algorithm]	More dynamic programming [solutions]	Graphs, basic search [slides] [handout] [scribbles]	Yet even still more dynamic programming Drop deadline [solutions]
Mar 18-21	Spring break
Mar 25-29	Directed graphs, depth-first search [slides] [handout] [scribbles]	Graph modeling [solutions]	Graphs continued [Graph notes]	Graph modeling [solutions]
April 1-4	BFS and Shortest Paths [slides]	Shortest paths [solutions]	Shortest Paths with Negative Lengths via DP, All Pairs [slides]	More shortest paths [solutions]
April 8-11	MST Algorithms [slides]	MST [solutions]	Optional review for Midterm 2, Fodder	Optional review for Midterm 2
Midterm 2: Monday, April 14, 7-9:30pm (Syllabus/Skillset)
April 15-18	Greedy algorithms [slides]	Greedy [solutions]	Undecidability: halting problem, diagonalization, reductions [slides]	Undecidability via reductions [solutions]
April 22-25	Reductions [slides]	Self Reductions [solutions]	NP, NP-Completeness, 3SAT to Independent Set [slides][helpful video on P vs NP]	NP-hardness proofs [solutions]
April 29-May 2	More NP-hardness reductions: 3-coloring, Hamiltonian cycle [slides]	NP-Hardness, the final chapter [solutions]	More on SAT, Wrap up [slides]	Reductions
May 6-9	No lecture, optional review session	Optional review for final, Fodder	Reading Day
Final Exam: Thursday, May 15, 7-10pm (Syllabus/Skillset)