CS/ECE 374A fa24: Lecture and Lab Schedule

Recording of live lectures: Mediaspace : Classtranscribe
Old prerecorded lectures: here.

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.

Tuesday Lecture	Wednesday Lab	Thursday Lecture	Friday Lab
Week 1: Aug 26-30
L1:Adminis+ trivia and course goals Introduction and history; strings [slides1, slides2 : scribbles]	String induction [induction notes, more] [solutions]	L2: Languages and regular expressions [slides : scribbles]	Regular expressions [solutions]
Week 2: Sep 2-6
L3: DFAs, product construction [Automata Tutor] DFA Proofs L3: [slides : scribbles]	DFA construction [solutions]	L4: Non-determinism, NFAs Jeff's NFA notes L4: [slides]	DFA product construction [solutions] [ms : ct]
Week 3: Sep 9-13
L5: NFAs continued, equivalence with DFAs and regular expressions Jeff's NFA notes Converting NFA to regex L5: [slides : scribbles]	DFA/NFA transformation [solutions]	L6: Proving non-regularity via fooling sets [DFA Proofs] [Fooling sets guide] L6: [slides : scribbles : h]	Proving non-regularity [solutions]
Week 4: Sep 16-20
L7: Context-free languages and grammars [slides : scribbles]	Context-free grammars [h] [solutions]	L8: More on Context-free languages and grammars, Turing machines L7: [slides, slides : scribbles]	Regular or not? [h] [solutions]
Week 5: Sep 23-27
L9: Halting and undecidability L9: [slides]	Algorithms for langs [solutions]	Optional review for Midterm 1	Optional review for Midterm 1
Week 6: Sep 30-Oct 4
Midterm 1: Monday, 7pm-9:30pm (details): solution.
L10: Recursion: Hanoi, mergesort [slides : scribbles] [solving recurrences] closest_pair.jl	Hint: Binary search [solutions]	L11: Divide and conquer: linear-time selection, Karatsuba multiplication [recurrence notes] [slides : scribbles]	Divide and conquer [solutions]
Week 7: Oct 7-Oct 11
L12: Backtracking: independent set, longest increasing subsequence [slides : scribbles]	Backtracking [solutions]	L13: Dynamic programming: splitting strings, longest increasing subsequence [slides : scribbles]	Dynamic programming [solutions]
Week 8: Oct 14-18
L14: More DP: Edit Distance, MIS in trees memoization and edit distance [slides : scribbles]	More dynamic programming [solutions]	L15: More dynamic programming, CYK Algorithm, DP via DAGs, DAGs, extraction order, and longest path in linear time [CYK : scribbles],	Yet even still more dynamic programming Drop deadline [solutions]
Week 9: Oct 21-Oct 25
L16: Graphs, basic search, Directed graphs, depth-first search [slides : scribbles]	Graph modeling [solutions]	L17: DFS/Strong connected components [slides : scribbles] [Graph notes]	Graph modeling [solutions]
Week 10: Oct 28-Nov 1
L18: BFS, Shortest Paths, Dijkstra [slides : scribbles]	Shortest paths [solutions]	L19: Shortest Paths: Negative Lengths via DP : All Pairs Shortest Path [slides : scribbles]	More shortest paths [solutions]
Week 11: Nov 4-Nov 8
ELECTIONS DAY Vote early and vote often L20: Greedy algorithms [slides]	Greedy [solutions]	Review sessions for midterm [scribbles]	Fodder: Optional review for Midterm 2
Week 12: Nov 11-Nov 19
Midterm 2: 11/11/2024, Monday, 7pm-9:30pm (details): solution.
L21: MST Algorithms [slides : scribbles]	MST [solutions]	L22: Unweighted Bipartite Matchings [slides	Matchings [solutions]
Week 13: Nov 18-Nov 23
L23: Polynomial time Reductions [slides : scribbles]	Self Reductions [solutions]	L24: NP, NP-Completeness, 3SAT to Independent Set [slides : scribbles] [helpful video on P vs NP]	NP-hardness proofs [solutions]
Nov 23-Dec 1	Absolutely give thanks, go on vacation.
Week 14: Dec 2-Dec 6
More NP-hardness reductions: 3-coloring, Hamiltonian cycle [slides : scribbles]	NP-Hardness, the final chapter [solutions]	More more more NP Completeness. [slides : scribbles]	Self redutions and NPC [solutions]
Week 14: Dec 9-Dec 13
Wrap-up and preliminary review for the final exam	Review for final	WRITING DAY
Final exam

Some additional notes:

Some of the lectures in handout format are here.

holidays : academic calendar.

Last modified: Fri 2024-11-29 17:09:15 UTC 2024 by Sariel Har-Peled