The Semester Project
Lecture W5M2: What It Is, How It Is Graded, and How to Start
September 21, 2026
What the project is
What it is
In teams of three, pick a substantial algorithmic problem, implement one or more solutions, measure them against your own theoretical analysis, and report what you found in writing and in a conference-style talk.
- It is worth 20% of the course grade, plus 10% for the final presentation.
- It exists because Learning Outcome 9 says apply algorithms to real problems, and because the gap between “\(O(n \log n)\) on paper” and “fast on my laptop” is where most of the interesting engineering lives.
Timeline and deliverables
The timeline
The four deliverables
| Deliverable | Due | Share of project grade |
|---|---|---|
| Proposal (2 pages) | Mon 10/5 | 15% |
| Checkpoint (working code, first measurements) | Wed 11/4 | 25% |
| Final report (8 to 12 pages, LaTeX) and code | Mon 11/30 | 60% |
| Presentation (12 minutes plus questions) | Mon 11/30 or Wed 12/2 | separate 10% of course grade |
Milestones lose 10% per day late, up to 5 days. Presentation slots are fixed; only documented emergencies move them.
Doing it well
What a good project has
- A real question. Not “implement Dijkstra” but “which shortest-path approach should a transit app use on Salem’s network, and why?”
- Two things to compare. Two algorithms, or one algorithm and a baseline, or one algorithm under two data structures.
- Analysis first. Bounds you derive before you measure, so the measurements can agree or disagree with something.
- Honest measurement. Inputs that grow, repeated runs, and a plot where the \(x\)-axis is \(n\).
- A conclusion you did not know in September.
Topic menu
- Network optimization: routing on real road or transit data; MST for network design; comparing Dijkstra with a heap versus without.
- Scheduling: interval scheduling and its weighted cousin; greedy heuristics against an exact dynamic program; course or exam timetabling.
- Resource allocation: knapsack variants; assignment problems via bipartite matching; load balancing.
- Text and search: autocomplete with tries versus hashing; approximate string matching; plagiarism detection with fingerprints.
- Your own. Pitch it in the proposal. Topics from later in the course (DP, flows) are welcome; you will learn them a few weeks ahead of the class, with help.
Getting started
This week’s job
- Form a team of three by Friday, September 25.
- Read the Project Overview page; it links the proposal spec and rubric.
- Pick two candidate topics and come talk them through before you write the proposal.
Where to find everything
- Project Overview page: requirements, the five parts every project needs, topic menu, teamwork and AI policy.
- Linked from it: the Proposal, Checkpoint, Final Report, and Presentation pages, each with its rubric.
Next up: binary trees (deck W5M3). HW3, which goes out today, is the project loop run once on your own; more on it at the end of the lecture.
References
Sources
- CS 351 Syllabus and Project Overview: Canvas.
