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-17 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)] (Solutions)	Required Reading: Chapter 7 [Comprehension Quiz 7] Undecidability	Required Reading: Chapter 8 Optional Reading: CLRS Ch4, Erickson Ch1 [Comprehension Quiz 8] Decidability and Undecidability (practice) (Solutions)
5	9/21	Divide and Conquer Part 1 [Mastery Quiz 3 (Ch6-7)] (Solutions)	Required Reading: Chapter 9 [Comprehension Quiz 9] Divide and Conquer Part 2	Required Reading: Chapter 10 Optional Reading: CLRS Ch14, Erickson Ch2 [Comprehension Quiz 10] Divide and Conquer (practice) (Solutions)
6	9/28	Recursive Backtracking [Mastery Quiz 4 (Ch8-9)](Solutions)	Dynamic Programming Part 1	Exam Review Exam Topics Sample Exam Solutions
7	10/5	MIDTERM EXAM (Solutions)	Required Reading: Chapter 11 Optional Reading: Erickson Ch3 [Comprehension Quiz 11] Dynamic Programming Part 2	Required Reading: Chapter 12 Optional Reading: CLRS Ch15, Erickson Ch4 [Comprehension Quiz 12] Dynamic Programming (practice)(Solutions)
8	10/12	Greedy Algorithms [Mastery Quiz 5 (Ch10-11)](Solutions)	Required Reading: Chapter 13 Optional Reading: CLRS Apdx B.4, Ch20.1, Erickson Ch5.1-5.4 [Comprehension Quiz 13] Graph Basics	Required Reading: Chapter 14 Optional Reading: CLRS Ch20.2-20.5, Erickson Ch5.5-6.6 [Comprehension Quiz 14] Greedy Algorithms and Graphs (practice)(Solutions)
9	10/19	Connected Components and Topological Sort [Mastery Quiz 6 (Ch12-13)]	Required Reading: Chapter 15 Optional Reading: CLRS Ch22, Erickson Ch8.1-8.6 [Comprehension Quiz 15] Shortest Paths Part 1	Required Reading: Chapter 16 Optional Reading: CLRS Ch23, Erickson Ch8.7-9.8 [Comprehension Quiz 16] Graph Algorithms (practice) (Solutions)
10	10/26	Shortest Paths Part 2 [Mastery Quiz 7 (Ch14-15)]	Required Reading: Chapter 17 Optional Reading: CLRS Ch21, Erickson Ch7 [Comprehension Quiz 17] Minimum Spanning Trees	[Comprehension Quiz 18] Shortest Paths and MSTs (practice)
11	11/2	Flows [Mastery Quiz 8 (Ch16-17)]	[Comprehension Quiz 19] Matchings	[Comprehension Quiz 20] Flows and Matchings (practice)
12	11/9	Linear Programming Part 1 [Mastery Quiz 9 (Ch18-19)]	[Comprehension Quiz 21] Linear Programming Part 2	[Comprehension Quiz 22] Linear Programming (practice)
13	11/16	NP Verifiers [Mastery Quiz 10 (Ch20-21)]	NP Verifiers (practice)	[Comprehension Quiz 23] NP-Hardness Part 1
14	11/23	NP-Hardness Part 2	Thanksgiving - No Class	Thanksgiving - No Class
15	11/30	[Comprehension Quiz 24] NP-Hardness (practice)	12/1 [Tuesday redefined as Friday] Approximation Algorithms [Mastery Quiz 11 (Ch22-23)]	12/2 [Wednesday] Final Exam Review
16	12/7	Wed Dec. 9 at 10:30 AM FINAL EXAM