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 typeset notes, scribbles, and video for each lecture, as well as problem handouts and solutions for each lab. Future lecture topics are subject to change. Exam dates are not.

Textbook chapters, as well as possibly lecture notes and videos from previous semesters, are available for each lecture, and problem handouts are available for each lab. (Solution links for future labs are just placeholders.)

If you find any of the bugs we've cleverly hidden in the materials, please open a new issue on bug-tracking site for Jeff's textbook or post a description of the error to Piazza (as appropriate).

✍ denotes notes/chapters revised for this semester.

Week	Tuesday Lecture	Tues/Wed Lab	Thursday Lecture	Thurs/Fri Lab
Jan 25–29	Adminis trivia and course goals Introduction and history; strings [Sariel's Videos, Lec 1] [A: video, scribbles] [B: video, slides]	String induction [Jeff's induction notes, Chandra's induction notes] [solutions]	Languages and regular expressions [Sariel's Videos, Lec 2] [A: video, scribbles] [B: video, slides, scribble]	Regular expressions [solutions]
Feb 1–5	DFAs: intuition, definitions, closure properties [Automata Tutor, JFLAP, Mahesh's DFA notes, Sariel's Videos, Lec 3] [A: video, scribbles][B: video, slides, scribble]	DFA construction [solutions]	Non-Determinism, NFAs ✍ [Sariel's Videos, Lec 4] [A: video, scribbles][B: video, slides, scribble]	DFA product construction [solutions]
Feb 8–12	Equivalence of DFAs, NFAs, and regular expressions [Sariel's Videos, Lec 5] [A: video, scribbles][B: video, slides, scribble]	Regex to NFA to DFA (to Regex) [solutions]	Closure Properties: Language Transformations [Patrick's Cycle(L) notes] [A: video, scribbles][B: video, slides, scribble]	Language Transformations [solutions]
Feb 15–19	Fooling Sets and Proving Non-Regularity [Mahesh's DFA notes, Fall 2015 TAs' Fooling Sets Notes, Sariel's Videos, Lec 6] [A: video, scribbles][B: video, slides, scribble]	NO INSTRUCTION (Campus-wide break)	Beyond Regularity: CFGs, PDAs, Turing Machines [Sariel's Videos, Lec 7/8] [A: video, scribbles][B: video, slides, scribble]	Proving Non-Regularity [solutions]
Feb 22–26	Universal Turing machines [Sariel's Videos, Lec 8] [A: video, scribbles][B: video, slides, scribble]	Turing Machines [solutions]	Optional review for Midterm 1 [A: video, scribbles][B: video, slides, scribble]	Optional review for Midterm 1
Midterm 1 – Monday, March 1 18:30–21:30 [Skill set] Conflict exam: Tuesday, March 2 07:30–10:30
Mar 1– 5	Reductions & Recursion [Sariel's Videos, Lec 10, Notes on Solving Recurrences] [A: video, scribbles][B: video, slides, scribbles]	Hint: Binary search [solutions]	Divide and conquer: Selection, Karatsuba [Sariel's Videos, Lec 11] [A: video, scribbles][B: video,slides, scribbles]	Divide and Conquer [solutions]
Mar 8–12	Backtracking [Sariel's Videos, Lec 12] [A: video, scribbles][B: video, slides, scribbles]	Backtracking [solutions]	Dynamic programming [Sariel's Videos, Lec 13] [A: video, scribbles][B: video, slides, scribbles]	Dynamic programming [solutions]
Mar 15–19	More Dynamic programming [Sariel's Videos, Lec 14] [A: video, scribbles] [B: video, slides, scribbles]	More Dynamic programming [solutions]	Even More DP, Graphs, Basic Search [Chandra's Graph notes, Sariel's Videos, Lec 15] [A: video, slides][B: video, slides, scribbles]	Even more DP [solutions] Drop deadline
Mar 22–26	Directed Graphs, DFS, DAGs and Topological Sort [Chandra's Graph notes, Sariel's Videos, Lec 16] [A: video, slides, scribbles] [B: video, slides, scribbles]	NO INSTRUCTION (Campus-wide break)	More Directed Graphs: DFS again, SCCs [A: video, slides, scribbles] [B: video, slides, scribbles]	Graph Modeling [solutions]
Mar 29–Apr 2	Shortest Paths: BFS and Dijkstra [Chandra's Graph notes, Sariel's Videos, Lec 17] [A: video, slides, scribbles][B: video, slides, scribbles]	More Graph Modeling [solutions]	Shortest paths: Bellman-Ford, Dynamic Programming on DAGs [Chandra's Graph notes, Sariel's Videos, Lec 18] [A: video, slides, scribbles] [B: video, slides, scribbles]	Shortest Paths [solutions]
Apr 5–9	Catch up lecture [A: video, scribbles] [B: video, slides, scribbles]	More Shortest Paths [solutions]	Optional review for Midterm 2 [A: video][B: video, slides, scribble]	Optional review for Midterm 2
Midterm 2 – Monday, April 12 18:30–21:30 [Skill set] Conflict exam: Monday, April 12 07:30–10:30 and 20:30–23:30
Apr 12–16	NO INSTRUCTION (Campus-wide break)	NO INSTRUCTION (Campus-wide break on Tues)	Reductions [Sariel's Videos, Lec 21] [A: video, slides] [B: video, slides, scribbles]	Reductions [solutions]
Apr 19–23	Undecidability [Sariel's Videos, Lec 9] [A: video, slides] [B: video, slides, scribbles]	Undecidability reductions [solutions]	SAT, NP and NP-Hardness [Sariel's Videos, Lec 22-24] [A: video, slides] [B: video, slides, scribbles]	NP-hardness reductions [solutions] ICES Forms Released
Apr 26-30	More NP-Hardness [Sariel's Videos, Lec 23-24] [A: video, slides] [B: video, slides, scribbles]	More NP-Hardness [solutions]	Catch up lecture [A: video, slides] [B: video, slides, scribbles]	No Lab
May 3-7	Wrap-up, closing remarks Optional review for Final Exam [A: video, slides] [B: video, slides, scribbles]	Optional Review for final exam Drop Deadline	Reading Day ICES Forms Due
Final Exam – Monday, May 10 08:00–11:00 [Skill set] Conflict exam: Monday, May 10 19:00–22:00