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