COMP221 - Algorithm Design & Analysis (Spring 2025)
Welcome to the COMP221 (Algorithm Design & Analysis) Course Page. For course policies, please check the syllabus.
Resources
Office Hours
Me and the preceptors will hold OH from the 2nd week of the semester onward. Times can be found in this google calendar. If posted times don’t work for you, please email me and we can schedule a separate meeting!
Schedule
The schedule below will be updated to keep track of all released course materials. Keep in mind that I may shift planned topics to adjust pace as necessary.
| Week | Date | Topic | Reading | Materials |
|---|---|---|---|---|
| 0 | FRI 1/24 | Course Overview | NA | Beginning-of-Semester Survey |
| 1 | MON 1/27 | Mathematical Foundations | Skiena 2.1, 2.6–2.8, Proof-Writing Guide | Activity 1 |
| - | WED 1/29 | Big-O(h) Analysis | Skiena 2.2–2.4 | |
| - | FRI 1/31 | Big-O(h) Analysis | - | Activity: Sorting, Time Complexity Notes |
| 2 | MON 2/03 | Proofs of Correctness (Loop Invariants) | Skiena 1.3–1.4, 1.6. Skim 2.5 | Tao on rigor |
| - | WED 2/05 | Proofs of Correctness (Loop Invariants 2) | ||
| - | FRI 2/07 | Proofs of Correctness (Recursion) | Skiena 3.1–3.2 | Optional Activity: BubbleSort, Correctness Notes |
| 3 | MON 2/10 | Brute Force Algorithms & DS Review | Skiena 3.3–3.7, 7.1–7.2 | Activity: DS Review |
| - | WED 2/12 | Sorting: Tree/HeapSort | Skiena 4.1–4.3 | Activity: Heaps & TreeSort |
| - | FRI 2/14 | Sorting: MergeSort | *Skiena 4.5 | Activity: Sorting as Pre-Processing, MergeSort Notes |
| 4 | MON 2/17 | Sorting: QuickSort | Skiena 4.6 | Optional Activity: Partition and Quicksort |
| - | WED 2/19 | Exam Review | ||
| - | FRI 2/21 | Exam 1 | ||
| 5 | MON 2/24 | Recursion & Binary Search Variants | *Skiena 5.1–5.3 | Activity: Binary Search Variants |
| - | WED 2/26 | The Master Theorem | Skiena 5.4 | Activity: Master Theorem |
| - | FRI 2/28 | NO CLASS: CAPSTONES | ||
| 6 | MON 3/03 | Divide and Conquer Algorithms | *5.5–5.6 | |
| - | WED 3/05 | Graphs: BFS (& DFS Variants) | *7.5–7.10 | BFS Notes |
| - | FRI 3/07 | Greedy Algorithms: Prim’s and MSTs | *8.1 | |
| 7 | MON 3/10 | Kruskal’s & Union-Find | MST Notes | |
| - | WED 3/12 | Djikstra’s and the Shortest Path Problem | 8.3.1 | Dijkstra Notes |
| - | FRI 3/14 | Floyd-Warshall & APSP | *8.3.2 | |
| 8 | - | SPRING BREAK | ||
| 9 | MON 3/24 | The Max-Flow Problem & Bipartite Matching | 8.5 | |
| - | WED 3/26 | Max-Flow = Min-Cut and Ford-Fulkerson | *8.5.2 | Ford-Fulkerson Notes |
| - | FRI 3/28 | Graph Modeling as a Design Principle | 8.7 | Graph Application Activity |
| 10 | MON 3/31 | Exam Review | ||
| - | WED 4/02 | Exam 2 | ||
| - | FRI 4/04 | Dynamic Programming | 10.1 | Dynamic Programming Activity 1 |
| 11 | MON 4/07 | Approximate String Match | *10.2 | Dynamic Programming Activity 2 |
| - | WED 4/09 | Subset Sum | *10.5 | |
| - | FRI 4/11 | CKY Parsing | *10.8 | |
| 12 | MON 4/14 | Combinatorial Methods 1 | 9.1–9.3, 9.6–9.7 | |
| - | WED 4/16 | Combinatorial Methods 2 | ||
| - | FRI 4/18 | Intro to Complexity Theory | 11.1 | |
| 13 | MON 4/21 | Reduction as a Proof Technique | 11.2–11.3 | |
| - | WED 4/23 | Reductions and SAT | *11.4–11.6 | |
| - | FRI 4/25 | P vs. NP | 11.9 | |
| 14 | MON 4/28 | Approximate Methods for Hard Problems | 12.1–12.3, 12.5 | |
| - | WED 4/30 | Complexity Review | ||
| - | FRI 5/02 | Report Peer Review | ||
| 15 | MON 5/05 | Exam 3 | ||
| FINALS | FRI 5/09 1:30–3:30pm |
Section 01 Final | ||
| FINALS | SAT 5/10 1:30–3:30pm |
Section 02 Final |
*s indicate the presence of an assigned reading problem. Enrolled students should see the Moodle to complete the problem before classtime.
Homeworks
Solutions for written assignments should be submitted through Moodle. Solutions for programming assignments should be submitted through the Github Classroom, which can be joined through Moodle.
Homework 0
OUT: 1/24 DUE: 2/3 9pm.
| instructions | TeX |
Homework 1
Out: 2/4 Due: 2/10 9pm.
| instructions | TeX |
Notes: A prior version of the assignment had problem 3 state that $c$ should be summed up to $i=n$. It has been corrected to $i=k$.
Homework 2
Out:: 2/11 Due:: 2/17 9pm.
| instructions | TeX |
Programming Assignment 1 - Sorting
Out: 2/25 Due: 3/4 11:59pm
Enrolled Students should accept the Github Classroom Link Posted on Moodle and work in that repository
Starter Code + Instructions (for reference)
Homework 3
Out:: 3/11 Due:: 3/25 9pm
Notes: The instructions for these two problems are quite long, but critical. Please read them carefully and ensure you understand what’s going on before starting work on the problems themselves. Many subparts are straightforward when understood but daunting when approached with a partial effort.
| instructions | TeX |
Programming Assignment 2 - MSTs and Union-Find
Out: 4/5 Due: 4/14 11:59pm
Enrolled Students should accept the Github Classroom Link Posted on Moodle and work in that repository
Starter Code + Instructions (for reference)
Homework 4
Out:: 4/21 Due:: 4/30 9pm
Notes: A prior version of this assignment was vague about the greedy strategy for Prob. 1. It has been updated to reflect that I don’t mean this to be unncessarily vague — the greedy strategy simply repeatedly adds the largest valued coin that does not overshoot $k$ to our multiset!
| instructions | TeX |
Final Report and Presentation
Instructions Out: 4/7
Topic Proposal: 4/14
In-class Peer-Review:: 5/02
Final Report Due: 11:59PM before Final Exam Slot
Final Presentation: Final Exam Slot
| Instructions | Sample Report | Sample Report TeX |
Note: In the interest of giving you (and me, in the sample report!) a bit more space, the page requirement now allows for 5-page submissions.