Beyond Brute Force: a progression from recursive exhaustive search through memoization, dynamic programming, pruning, branch-and-bound, and heuristics.

Overview

Beyond Brute Force is an integrative algorithms project that asks you to study one NP-complete problem from theory through implementation and experimentation.

You will begin with the decision version of your problem: define it precisely, explain why it is in NP, and study the reduction that establishes NP-completeness. You will then work with the corresponding optimization version, beginning with an exhaustive algorithm that provides a trustworthy exact baseline.

From there, the project asks a broader algorithm-design question: how can we make meaningful, measurable improvements over exhaustive search? You will investigate ways to reduce the computational effort required by an exact algorithm and then develop a heuristic for instances where exact computation becomes intractable in practice. Finally, you will compare the approaches experimentally, measuring both computational performance and solution quality and examining what kinds of inputs make each approach succeed or struggle.

The central questions of the project are:

Learning Objectives

By completing this project, you will be able to:

Terminology

The theoretical portion of this project focuses on the decision version of your problem, while the programming and experimental portions focus on the corresponding optimization version. For a decision problem, an exact algorithm simply returns the correct yes/no answer. The terminology below therefore refers primarily to optimization algorithms.

Project Problems

Each team will study one of the following problem families:

Separate problem specifications will provide exact input/output formats, required statistics, and problem-specific guidance.

Teams and Shared Responsibility

Teams will consist of two or three students. All team members share responsibility for the theoretical foundation, test cases, and exhaustive baseline. One student will take primary responsibility for the improved exact algorithm and another for a heuristic algorithm.

A three-person team will develop and implement a second heuristic algorithm that is meaningfully different from the first. Changing only a parameter, time limit, number of restarts, random seed, or other tuning choice does not constitute a second heuristic algorithm. Primary responsibility does not mean exclusive responsibility: all team members must understand the complete project and participate in the final experimental analysis.

Project Progression

The four areas below are workstreams, not checkpoints. They overlap as the project develops; the checkpoints are formal submission points that capture your progress at particular stages.

Checkpoint 1 is devoted to getting started and project selection. The algorithmic progression begins with Checkpoint 2, as shown below. Bold cells indicate the primary focus of each workstream at that stage.

Workstream CP2 Foundation CP3 Algorithms CP4 Experiments Final Submission
Theory + baseline Build Refine Compare Report
Improved exact Plan Build Compare Report
Heuristic(s) Plan Build Compare Report
Experiments Plan Pilot Run Report

Theory and exact baseline. Begin with the decision problem and its NP-completeness argument, then connect it to the optimization problem your team will implement. Build and validate a baseline exhaustive solver using small instances with known answers. As part of this work, consider whether different search paths can lead to the same remaining subproblem.

Improved exact algorithm. Develop an exact method that performs less computation than the exhaustive baseline while still guaranteeing an optimal answer. Possible approaches include memoization, dynamic programming, pruning, branch-and-bound, stronger bounds, improved branching decisions, or another problem-specific exact technique. Measure the computation itself, not running time alone.

Heuristic algorithm(s). Develop at least one polynomial-time heuristic algorithm for producing good feasible solutions when exact computation becomes intractable in practice. Three-person teams develop a second, meaningfully different heuristic algorithm. Detailed implementation requirements for heuristic1 are provided in Checkpoint 3.

Experimental evaluation. Bring the approaches back together and compare them across a broad collection of benchmark instances. Examine not only overall performance, but also how performance changes with meaningful input structure. The project provides benchmark instances and known optimal values where appropriate so that heuristic evaluation does not depend on the speed of your team’s exact solver. See Experimental Evaluation for details.

Checkpoints

The project is worth 100 points and is organized around four checkpoints followed by the final submission. The point value shown for each checkpoint is its actual contribution to the project grade; checkpoint scores are not rescaled later. See the complete Checkpoints and Final Submission page for assessment details and submission expectations.

Checkpoint Main Goal Points
Checkpoint 1: Getting Started and Project Selection Verify shared repository access, record team information and three ranked project preferences, and pass the automated setup checks. 5
Checkpoint 2: Foundation Establish and demonstrate the theory, exhaustive baseline, test cases, and state analysis. 25
Checkpoint 3: Improved Algorithms Complete and validate the improved exact algorithm, polynomial-time bound, and first heuristic, then begin comparing them with the exhaustive baseline. 10
Checkpoint 4: Experimental Investigation Use the completed algorithms and bound to investigate exact-search limits, heuristic quality, and the effect of instance structure. 30
Final Project Submit the reproducible repository, concise report, presentation, and peer questions, with emphasis on the synthesis and interpretation of the completed work. 30
Total 100

Optional extensions are integrated into the checkpoint where the additional work naturally belongs rather than creating additional checkpoints.

Project Deliverables

By the end of the project, each team will produce a shared repository containing the exact and heuristic implementations, test and benchmark materials, experimental scripts and results, required checkpoint artifacts, a concise final report, and final presentation materials.

In this course, team repositories will be created through Classroom 50. GitHub records the project’s development history and contains the project artifacts; Gradescope provides the required submission and assessment workflow, including automated validation where appropriate and an opportunity to correct mechanical problems before a deadline.

Required filenames, interfaces, repository structure, and the submission workflow are described on the Repository and Gradescope Requirements page.

Grading Focus

Each checkpoint rubric evaluates the work that should be mature at that stage of the project. Once a component has been substantially graded, later checkpoints generally use or build on that work rather than grade the same component again from the beginning.

Across the project, assessment focuses on:

Gradescope will identify which checkpoint requirements are checked automatically and which require instructor review. The detailed checkpoint page serves as the source of truth for what is being assessed.