Homework assignments are to be submitted via Moodle before class on the day on which they are listed. Projects are due by 11 PM via Moodle on the day on which they are listed. Note that all page numbers and problems listed are specific to the hardcopy version of the book with the ISBN number as listed in the syllabus.
| Date | Class Period & Lecture Topic | Reading | Assignment |
|---|---|---|---|
| Jan 9 | Syllabus, policies, business, goals, intro | Join course Discord server | |
| Jan 11 | Big-O and basic arithmetic | Chs. 0-1.1 (pp. 1-15) | Install Python and PyQt5 and start playing around |
| Jan 16 | Modular arithmetic and Primality | 1.2-1.3 (pp. 16-30) | HW1 |
| Jan 18 | Cryptography and Euclid | 1.4-1.5 (pp. 30-38) Cracking RSA (optional) |
HW2 P1 Design Experience (due 1/19) |
| Jan 23 | DIVIDE AND CONQUER: Multiplication, Recurrence Relations, Merge Sort |
2-2.2 (pp. 45-50) | HW3 P1: Primality Tester |
| Jan 25 | Medians, Matrix Multiplication, Convex Hull | 2.3-2.5 (pp. 50-57) | HW4 |
| Jan 30 | GRAPHS: Depth-first Search |
3-3.2 (pp. 80-87) | HW5 P2 Design Experience |
| Feb 1 | Directed Graphs and Strong Connectedness | 3.3-3.4 (pp. 87-95) | HW6 |
| Feb 6 | Shortest Paths | 4-4.4 (pp. 104-113) | HW7 |
| Feb 8 | Priority Queues and Variations on Shortest Path | 4.5-4.7 (pp. 113-120) | HW8 P2: Convex Hull |
| Feb 13 | GREEDY: Minimum Spanning Trees |
5-5.1 (pp. 127-138) | HW9 Examity Practice Quiz |
| Feb 15 | Huffman Encoding | 5.2 (pp. 138-143) | HW10 P3 Design Experience |
| Feb 20 | Horn Formulas and Set Cover | 5.3-5.4 (pp. 144-147) | HW11 |
| Feb 22 | Midterm (on Moodle, no class) | Study Guide | |
| Feb 27 | DYNAMIC PROGRAMMING: Longest Increasing Subsequence and Edit Distance |
6-6.3 (pp. 156-164) | HW12 P3: Network Routing |
| Feb 29 | Knapsack | 6.4-6.5 (pp. 164-171) | HW13 |
| Mar 5 | Chain Matrix Multiplication | 6.4-6.5 (pp. 164-171) | |
| Mar 7 | Shortest Paths and Independent Sets | 6.6-6.7 (pp. 171-177) | P4 Design Experience |
| Mar 12 | Traveling Salesperson | HW14 | |
| Mar 14 | LINEAR PROGRAMMING: Introduction to Linear Programming |
7-7.1 (pp. 188-198) | HW15 |
| Mar 19 | Spring Break | ||
| Mar 21 | Spring Break | ||
| Mar 26 | Duality and Zero-sum Games | 7.4-7.5 (pp. 206-213) | HW16 P4: Gene Sequencing |
| Mar 28 | INTELLIGENT SEARCH: Backtracking and Branch & Bound |
9-9.1 (pp. 271-276) + extra B&B TSP material |
HW17 |
| Apr 2 | More Branch & Bound | 9-9.1 (pp. 271-276) + extra B&B TSP material |
P5 Design Experience |
| Apr 4 | NP-completeness | 8-8.2 (pp. 232-247) + "Unsolvable Problems" (p. 263) |
HW19 |
| Apr 9 | Approximation and Local Search | 9.2-9.3 (pp. 276-293) | HW20 |
| Apr 11 | ADVANCED ALGORITHMS: Randomized Algorithms & Grad School |
Section 2.4; Boxes on pp. 29, 56, 140 |
HW21 |
| Apr 16 | Quantum Computation | 10-10.2 (pp. 297-302) | P5: TSP with Branch and Bound |
| Apr 18 | Evolutionary Computation | ||
| Apr 23 | Final Exam Review | Study Guide | |
| Apr 25 | Group Project Presentations | P6: Group TSP | |
| May 3 | Final (on Moodle, closes midnight) | Study Guide |
The schedule is subject to change.
