CSCE 411: Algorithm Design and Analysis

Please note, the assigned readings for each lecture should be completed BEFORE class (the comprehsnion quiz will check your understanding of the readings)

Course Notes Ch1-7 as a single document.

Week	Date	Day 1 (Monday)	Day 2 (Wednesday)	Day 3 (Friday)
1	8/24	Course Overview	Required Reading: Chapter 1 Optional Reading: CLRS Apdx A, B [Comprehension Quiz 1] Mathematical Foundations	Required Reading: Chapter 2 [Comprehension Quiz 2] Proof Basics
2	8/31	Required Reading: Chapter 3 [Comprehension Quiz 3] Induction and Loop Invariants	Required Reading: Chapter 4 Optional Reading: CLRS Ch3 [Comprehension Quiz 4] Proofs (practice) [Solutions]	Asymptotic Analysis [Mastery Quiz 1 (Ch1-3)] (Solutions)
3	9/7	Labor Day - No Class	Required Reading: Chapter 5 Optional Reading: CLRS Ch2, Erickson Ch0 [Comprehension Quiz 5] The RAM model	Required Reading: Chapter 6 [Comprehension Quiz 6] Runtime Analysis (practice) (Solutions)
4	9/14	Decidability [Mastery Quiz 2 (Ch4-5)]	Required Reading: Chapter 7 [Comprehension Quiz 7] Undecidability	[Comprehension Quiz 8] Decidability and Undecidability (practice)
5	9/21	Divide and Conquer Part 1 [Mastery Quiz 3 (Ch6-7)]	[Comprehension Quiz 9] Divide and Conquer Part 2	[Comprehension Quiz 10] Divide and Conquer (practice)
6	9/28	Recursive Backtracking [Mastery Quiz 4 (Ch8-9)]	[Comprehension Quiz 11] Dynamic Programming Part 1	Exam Review
7	10/5	MIDTERM EXAM	[Comprehension Quiz 12] Dynamic Programming Part 2	[Comprehension Quiz 13] Dynamic Programming (practice)
8	10/12	Greedy Algorithms [Mastery Quiz 5]	[Comprehension Quiz 14] Graph Basics	[Comprehension Quiz 15] Greedy Algorithms and Graphs (practice)
9	10/19	Connected Components and Topological Sort [Mastery Quiz 6]	[Comprehension Quiz 16] Shortest Paths Part 1	[Comprehension Quiz 17] Graph Algorithms (practice)
10	10/26	Shortest Paths Part 2 [Mastery Quiz 7]	[Comprehension Quiz 18] Minimum Spanning Trees	[Comprehension Quiz 19] Shortest Paths and MSTs (practice)
11	11/2	Flows [Mastery Quiz 8]	[Comprehension Quiz 20] Matchings	[Comprehension Quiz 21] Flows and Matchings (practice)
12	11/9	Linear Programming Part 1 [Mastery Quiz 9]	[Comprehension Quiz 22] Linear Programming Part 2	[Comprehension Quiz 23] Linear Programming (practice)
13	11/16	NP Verifiers [Mastery Quiz 10]	NP Verifiers (practice)	[Comprehension Quiz 24] NP-Hardness Part 1
14	11/23	NP-Hardness Part 2	Thanksgiving - No Class	Thanksgiving - No Class
15	11/30	[Comprehension Quiz 25] NP-Hardness (practice)	12/1 [Tuesday redefined as Friday] Approximation Algorithms [Mastery Quiz 11]	12/2 [Wednesday] Final Exam Review
16	12/7	Wed Dec. 9 at 10:30 AM FINAL EXAM