Beyond Brute Force
Overview
Beyond Brute Force is an integrative algorithms project in which each team studies one NP-complete optimization problem from theory through implementation and experimentation.
Over three weeks, you will build a straightforward exact baseline, develop improved exact and heuristic approaches, and use experiments to understand where the different methods succeed or struggle.
A useful way to think about the project is:
Week 1: Understand your problem, build the exhaustive baseline, and plan what comes next.
Week 2: Make the algorithms substantially better.
Week 3: Find out how good the algorithms actually are.
Start Here
If your team has not yet received an assigned problem, begin with Getting Started.
After your project is assigned, proceed to Checkpoint 1: Foundation to create your team repository and begin the algorithmic work.
Project Roadmap
| Stage | Goal | Points |
|---|---|---|
| Getting Started / Project Selection | Form your team, review the problem definitions, and submit three ranked project preferences through Gradescope. | 5 |
| Checkpoint 1: Foundation | Create the shared repository, configure the assigned problem, build and validate the exhaustive baseline, and plan what follows. | 25 |
| Early Project Review | Demonstrate individual understanding and team progress, identify problems early, and leave with concrete next steps for the major implementation work. | 10 |
| Checkpoint 2: Improved Algorithms | Implement and validate the bound, improved exact algorithm, and first heuristic. | 30 |
| Final Project | Experiment across benchmarks and challenges, determine what the algorithms can and cannot do, and synthesize the results. | 30 |
| Total | 100 |
Project Problems
Each team studies one of five NP-complete optimization problems. The diagrams below show the kind of solution each problem asks you to find.
Minimum Vertex Cover
Choose as few vertices as possible to cover every edge.
Minimum Graph Coloring
Color the vertices using as few colors as possible.
Maximum Clique
Find the largest set of pairwise adjacent vertices.
Traveling Salesperson
Find a shortest tour that visits every city exactly once.
Longest Path
Find a longest simple path through the graph.
Teams and Shared Responsibility
Teams normally consist of two or three students; instructor-approved individual projects are permitted. Primary responsibility for one algorithm does not mean exclusive responsibility: every team member must understand the assigned problem, the verifier, and the major ideas used by the team.
The Early Project Review includes a short individual understanding check so that misconceptions can be corrected before the major implementation work of Week 2.