CS320: Algorithms - Theory and Practice - McConnell
| Week | Dates | Topics | Material | Due |
|---|---|---|---|---|
| 1 | 1/22-1/25 | Overview, Proof by contradiction and reduction of one problem to another: Stable Marriage Problem | Chapter 1, Section 1.1 | |
| 2 | 1/28-2/1 | More proofs by contradiction. Reductions of other problems to Stable Marriage. Game theory. Classes of problems; five representative problems from Ch. 1. Significance of asymptotic bounds. | Chapter 1, 2.1, 2.2 Study guide for quiz on 1/31; Quiz 1/31 solutions | Quiz on 1/31 |
| 3 | 2/4-2/8 | Classes of problems. The class NP. Undecidable problems (halting problem). Big-O analysis. | Chapters 1 and 2 Homework 1 due Tuesday 2/5, CallMatching.java, Matching.class, Homwork 1 solutions | Registration closes on evening of 2/6 -- Last day to drop and get your tuition back |
| 4 | 2/11-2/15 | Big-O analysis. | Chapter 2 | |
| 5 | 2/18-2/22 | More on big-O, Chapter 2 | Homework 2 solutions. | |
| 6 | 2/25-3/1 | Graph theory and graph algorithms | Chapter 3 | Homework 3 due 3/7 |
The midterm will be on 3/28, in-class.