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