CS/ECE 374: Lecture and Lab Schedule

Zoom link : Recording of live lectures: Mediaspace, Classtranscribe : Prerec lectures

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.

Week	Tuesday Lecture	Wednesday Lab	Thursday Lecture	Friday Lab
1 Aug 24-28	Adminis+ trivia and course goals Introduction and history; strings L1: [slides1, slides2] Scribbles	String induction [induction notes, more] [solutions] [pre-recording]	Languages and regular expressions L2: [slides] Scribbles	Regular expressions [solutions]
2 Aug 31-Sep 4	DFAs, product construction [Automata Tutor] DFA Proofs L3: [slides] Scribbles	DFA construction [solutions] [prerecorded]	Non-determinism, NFAs Jeff's NFA notes L4: [slides] Scribbles	DFA product construction [solutions] [yt : ms : ct]
3 Sep 7-11	NFAs continued, equivalence with DFAs and regular expressions Jeff's NFA notes Converting NFA to regex L5: [slides] Scribbles	DFA/NFA transformation [solutions]	Proving non-regularity via fooling sets [DFA Proofs] [Fooling sets guide] L6: [slides] Scribbles	Proving non-regularity [solutions]
4 Sep 14-18	Context-free languages and grammars L7: [slides] Scribbles	Context-free grammars [solutions]	Turing machines: history, formal definitions, examples, variations L8: [slides] Scribbles	Regular or not? [solutions]
5 Sep 21-25	Halting and undecidability L9: [slides] Scribbles	Undecidability [solutions]	Optional review for Midterm 1 Scribbles	Optional review for Midterm 1
Midterm 1: Sunday/Monday, September 27/28 (details): solution.
6 Sep 28-Oct 2	Recursion: Hanoi, mergesort [slides][solving recurrences] Scribbles	Hint: Binary search [solutions]	Divide and conquer: linear-time selection, Karatsuba multiplication [recurrence notes] [slides] Scribbles	Divide and conquer [solutions]
7 Oct 5-9	Backtracking: independent set, longest increasing subsequence [slides] Scribbles n queens demo(ipynb)(html)	Backtracking [solutions]	Dynamic programming: splitting strings, longest increasing subsequence [slides] Scribbles python memoize demo(ipynb) (html)	Dynamic programming [solutions]
8 Oct 12-16	More DP: Edit Distance, MIS in trees memoization and edit distance [slides] Scribbles	More dynamic programming [solutions]	CYK Algorithm, Graphs, basic search [CYK, Graph search slides] Scribbles optimal bst (ipynb) (html)	Yet even still more dynamic programming Drop deadline [solutions]
9 Oct 19-23	Directed graphs, depth-first search Scribbles	Graph modeling [solutions]	DFS/Strong connected components [slides] [Graph notes] Scribble[1, 2]	Graph modeling [solutions]
10 Oct 26-30	BFS and Shortest Paths [slides] Scribbles	Shortest paths [solutions]	Shortest Paths with Negative Lengths via DP [slides] Scribble[1, 2] - Animation	More shortest paths [solutions]
11 Nov 2-6	ELECTION DAY Vote early and vote often	Greedy [solutions]	Greedy algorithms [slides] Scribbles	Fodder: Optional review for Midterm 2
Midterm 2: Sunday/Monday, November 8/9 (details): solution.
12 Nov 9-13	No lecture in lieu of midterm	No discussion in lieu of midterm	MST Algorithms [slides] Scribbles	MST [solutions]
13 Nov 16-20	Polynomial time Reductions [slides] Scribbles	Self Reductions [solutions]	NP, NP-Completeness, 3SAT to Independent Set [slides] Scribbles [helpful video on P vs NP]	NP-hardness proofs [solutions]
Nov 21-29	Definitely give thanks, go on vacation.
14 Nov 30-Dec 4	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]
15 Dec 7-9	Wrap-up and preliminary review for the final exam Scribbles	Review for final
Dec 10	Reading day (Thursday)
Final exam time window: Dec 17, 12:01am - Dec 18, 11:59pm (CST).
OLD Skill set for final Study material for the final

Some additional notes:

Some of the lectures in handout format are here.

holidays : academic calendar.

Last modified: Fri 2020-09-18 02:49:34 UTC 2020 by Sariel Har-Peled