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