Project Stages

1 - Project Selection

Points: 5 · Submission: Gradescope

Project Selection is the first required stage of Beyond Brute Force, before Checkpoint 1.

To form your team (or work individually with instructor approval), review the problem definitions, rank three projects, and submit project.json on Gradescope, follow Getting Started / Project Selection.

After assignments are announced, continue to Checkpoint 1: Foundation to create your repository and start programming.

2 - Checkpoint 1: Foundation

Goal: Understand the theoretical and computational structure of your problem and establish a trustworthy exhaustive baseline whose search space is measurable.

Points: 25

Checkpoint 1 has two parts: Build and Validate the Baseline and Analyze and Plan. The written analysis produced in Part B belongs in reports/checkpoint1.pdf Organize the report using clearly labeled sections corresponding to the six analysis topics in Part B.

First: Create and Configure Your Team Repository

Your team should already have completed Getting Started / Project Selection on Gradescope and received its assigned problem.

1. Create the team repository. Use the Beyond Brute Force Classroom 50 assignment. Create or join your existing course team so that there is one shared repository per team.

2. Check access. Every team member should confirm that they can access the repository on GitHub and clone it locally:

   git clone YOUR_TEAM_REPOSITORY_URL
   cd YOUR_TEAM_REPOSITORY_DIRECTORY
   

3. Transfer your project information. Copy the project.json submitted on Gradescope into the repository root, preserving the supplied field names (only student names are required). Enter the instructor-assigned project identifier in assigned_problem; do not change your originally ranked project_preferences.

4. Run the one-time setup from the repository root:

   python tools/setup_project.py
   

   This checks the assigned project and installs the external benchmark data used for it. See Quick Reference for related commands.

5. Verify and commit the setup. Confirm the selected project and team information are correct, commit project.json, and push it. Every team member should be able to pull the resulting changes. See Repository & Gradescope for the folder structure, ownership rules, and Git expectations.

Note: The standalone check_project_selection.py validates the pre-assignment Gradescope upload while assigned_problem is blank. After project assignment, use tools/setup_project.py for repository setup and validation. Do not use the pre-assignment checker on the updated repository file.

Once repository setup is complete, proceed to Part A and begin your verifier and exhaustive baseline.

Part A: Build and Validate the Baseline

A1. Decision-problem verifier (verifier.py)

Implement the required problem-specific verifier. The verifier corresponds directly to the polynomial-time certificate verifier for the decision version of your problem. Its inputs include:

• the problem instance;
• a proposed certificate or solution; and
• the decision threshold $k$.

The verifier must return True exactly when the proposed certificate proves that the decision instance is a YES instance. The verifier must run in polynomial time. It checks the certificate and the threshold condition; it does not determine whether the certificate is optimal. The exact verifier signature and the meaning of $k$ for your assigned problem are documented on the corresponding problem page and on the Program Interface page.

A2. Straightforward exhaustive solver (exhaustive.py)

Checkpoint 1 establishes an exhaustive baseline that uses brute-force enumeration to identify the optimal solution.

Your solver must work by enumerating complete candidate solutions and then testing each completed candidate. The purpose of this restriction is to make the size and structure of the underlying search space directly measurable before you develop techniques for avoiding unnecessary work.

Use the following exhaustive enumeration strategy for your assigned problem:

Python utilities such as itertools.combinations, itertools.permutations, and itertools.product are appropriate for this checkpoint.

Each complete candidate must be tested using the required problem verifier. The exhaustive solver may compute the candidate’s objective value separately when needed to compare solutions, but it must use the verifier to determine whether the completed candidate satisfies the problem requirements.

Your Checkpoint 1 exhaustive solver should NOT use techniques whose purpose is to avoid generating portions of the complete candidate space. In particular, do not use:

• backtracking that rejects a partial candidate before it is complete;
• branch-and-bound;
• pruning based on partial solutions;
• memoization;
• dynamic programming; or
• another problem-specific technique that skips complete candidates because of information discovered while constructing them.

Those ideas belong to the improved exact algorithm beginning in Checkpoint 2.

The exhaustive solver must:

• follow the common program interface;
• be exact: it must return an optimal solution;
• generate a complete candidate before deciding whether that candidate is feasible; and
• complete within the allowed time on the small instances used for Checkpoint 1 testing.

The search may stop once the order in which candidates are explored proves that the first feasible candidate found has the optimal objective value.

This implementation is intentionally not expected to be efficient. It establishes the baseline against which later algorithms will be compared.

A3. Count complete candidates (exhaustive.py)

Your exhaustive solver must record:

statistics["candidates"]

as the number of complete candidate solutions examined during the search.

Increment this count once each time a complete candidate has been generated and tested for feasibility.

For example:

• an MVC subset that is tested as a possible cover is one candidate;
• a vertex subset that is tested as a possible clique is one candidate;
• a complete assignment of all vertices to colors is one coloring candidate;
• a complete TSP tour that is tested is one candidate; and
• a complete ordered vertex sequence tested as a possible path is one candidate.

Do not use this field to count partial assignments, recursive calls, loop iterations that do not produce complete candidates, or other implementation details.

Elapsed time should continue to be reported through the common statistics interface. The candidates count provides a more direct description of the combinatorial work performed by the Checkpoint 1 baseline.

A4. Public testing and validation

Run the Checkpoint 1 public tests from the root of your repository: python tools/run_cp1_tests.py. The local checker displays detailed student-code diagnostics, including file and line information, by default. To request a more compact display, use: python tools/run_cp1_tests.py --quiet

The public tests exercise the student verifier directly. Solver tests check the required output structure and known objective values and use the already-tested student verifier to validate returned certificates.

Use the public tests to correct interface, verifier, solver, and statistics problems before submitting to Gradescope.

Part B: Analyze and Plan

B1. Problem formulation and NP-completeness

Define the decision version of your problem precisely.

Identify:

• the input, including the role of $k$;
• the YES/NO question;
• an appropriate certificate; and
• the polynomial-time verification procedure.

Explain how your implemented verifier corresponds to this certificate-verification procedure.

Outline the reduction used to establish NP-hardness, and explain how the decision problem relates to the optimization problem your team is implementing.

B2. Complete-candidate search space

Describe the search space represented by your Checkpoint 1 implementation.

Your discussion should address:

• What constitutes one complete candidate solution?
• For a fixed candidate size, path length, number of colors, or other relevant parameter $k$, how many complete candidates are possible?
• How does the number of candidates change as $k$ changes?
• Which values of $k$ or candidate sizes create the largest portions of the search space?
• In what order does your exhaustive solver explore the different values of $k$, candidate sizes, or candidate lengths?
• Why can the solver stop when it does and still guarantee an optimal answer?
• How rapidly does the total candidate space grow as the input size increases?

Where appropriate, express the candidate-space size mathematically. For example, subset-based searches naturally involve quantities such as $\binom{n}{k}$, while complete color assignments for a fixed number of colors involve $k^n.$

The goal is to connect the implementation to the combinatorial structure of the search space, not merely to state that the algorithm is exponential.

B3. State, repeated subproblems, and dynamic programming

The Checkpoint 1 implementation deliberately enumerates complete candidates, but later algorithms may reason about partial solutions or subproblems.

Describe what information would completely characterize one such partial state or subproblem for your problem.

Consider:

• Can different sequences of choices lead to the same remaining subproblem?
• If memoization were used, what information would need to appear in a memoization key?
• Could memoization eliminate repeated work?
• Could the same subproblem structure be evaluated bottom-up using dynamic programming?
• Even if repeated work can be eliminated, how does the number of distinct states grow?

The purpose of this analysis is not to require a dynamic-programming implementation. It is to connect the complete enumeration used in Checkpoint 1 with backtracking, memoization, dynamic programming, and other techniques studied in class.

B4. Baseline validation and growth

Describe how you validated the exhaustive solver using instances whose optimal solutions are known.

Present initial evidence showing how the computational effort of the solver grows. At minimum, report:

• input size or other relevant instance parameters;
• the number of complete candidates examined; and
• elapsed running time.

Briefly explain what the measurements suggest about the practical limits of straightforward complete-candidate enumeration.

At this checkpoint, you are establishing a baseline rather than trying to explain every difficult-instance pattern. More systematic questions about which instances are difficult will be investigated later in the project.

B5. Improved exact algorithm design

Checkpoint 2 replaces complete-candidate enumeration with a more selective exact search.

Develop a concrete design for an improved exact algorithm that can use information about a partial solution, subproblem, bound, or previous computation to avoid generating substantial portions of the Checkpoint 1 candidate space. This algorithm will be implemented in Checkpoint 2.

Your discussion should identify:

• the state of one partial solution or subproblem;
• the base case or cases;
• the choices or branches that generate smaller subproblems;
• a recurrence, branching relation, or equivalent mathematical or pseudocode description of the decomposition;
• conditions under which a partial solution, branch, or subproblem can be abandoned;
• any bounds, memoization, dominance rules, structural observations, or other information that can avoid additional work; and
• why eliminating that work cannot eliminate an optimal solution.

Your eventual implementation does not need to use recursive Python function calls. This requirement concerns the structure of the algorithm, not a required programming style.

B6. Bound and heuristic plans

Bound design

Develop a concrete plan for the required polynomial-time method for bounding the optimal solution value. The problem specification identifies whether your required function is a lower bound or an upper bound.

Your discussion should identify:

• the quantity your bound will compute;
• the algorithm used to compute it;
• why the returned value is guaranteed to remain on the correct side of the optimum;
• the asymptotic running time of the bound computation; and
• whether and how the same bound could be useful inside the improved exact algorithm for pruning or branch-and-bound.

The project template already contains the required bound-function signature. Checkpoint 1 does not require the bound function to be implemented, and the Checkpoint 1 public tests do not call it.

Heuristic plan

Develop a concrete plan for the first heuristic that you intend to implement in Checkpoint 2.

Describe:

• the basic strategy;
• where randomized choices will occur;
• how multiple attempts or restarts will be organized;
• how the best valid solution found so far will be retained; and
• why the default amount of work is bounded by a polynomial in the input size.

For three-person teams, also identify a possible second heuristic that is meaningfully different from the first. Changing only parameters, time limits, restart counts, random seeds, or other tuning choices is not sufficient.

These plans may change as you learn more about the problem.

Submission checklist

• The required decision-problem verifier is implemented and passes the public tests.
• The exhaustive solver uses complete-candidate enumeration rather than backtracking, pruning, memoization, dynamic programming, or branch-and-bound.
• The exhaustive solver is exact and completes the Checkpoint 1 test instances within the allowed time.
• statistics["candidates"] records the number of complete candidates examined.
• Initial validation and computational-growth measurements have been collected.
• reports/checkpoint1.pdf contains the six required analysis sections.
• The improved exact design explains how the Checkpoint 2 solver will avoid portions of the Checkpoint 1 complete-candidate search.
• The bound design identifies a polynomial-time upper or lower bound and explains why it is valid.
• The heuristic plan describes its randomized strategy, repeated attempts or restarts, and best-so-far behavior.
• python tools/run_cp1_tests.py passes.
• All current work has been committed and pushed to GitHub.
• The repository has been submitted to the Checkpoint 1 Gradescope assessment with all team members included in the Gradescope group.

Grading

Assessment. Gradescope will check the required programming interfaces, the decision verifier, the straightforward exhaustive solver, required statistics, and the required PDF artifact. The instructor will review the written analysis, evidence that the baseline is trustworthy, the description of the complete candidate space, and the proposed improved-exact, bound, and heuristic designs.

Algorithm Early Project Review. Shortly after Checkpoint 1, each team will meet with the instructor to discuss its proposed improved exact algorithm, bound, and heuristic plan. Come prepared to explain what the Checkpoint 1 solver enumerates, which portions of that search the proposed improved exact method should avoid, why the improved method remains exact, why the proposed bound is valid, whether the bound can contribute to pruning, and how the heuristic will search for good solutions.

3 - Early Project Review

Goal: Catch misconceptions and lack of progress early enough that the feedback can guide the major implementation work of Week 2.

Points: 10

Reviews begin near the end of Week 1. They intentionally overlap the transition from Checkpoint 1 into Checkpoint 2 rather than creating a separate phase of project work.

The review has two parts.

Part A: Individual understanding check

Each team member will answer one or two short questions independently about the team’s assigned problem.

These questions are intentionally basic. Examples include:

• Is this proposed coloring legal? If not, identify a conflicting edge.
• Is this set a vertex cover? If not, identify an uncovered edge.
• Is this set a clique?
• Is this sequence a legal simple path?
• Is this sequence a legal TSP tour, and what is its cost?
• Is the optimization problem a minimization or maximization problem?
• What must the verifier check?
• Does a feasible solution have to be optimal?

The purpose is to verify that every project member understands the problem being studied, not to create a high-pressure oral examination.

Part B: Team progress review

The team should be prepared to:

1. show the working verifier;
2. show the exhaustive baseline on a small example;
3. explain how the baseline was validated;
4. identify where the exhaustive approach begins to grow rapidly;
5. explain the proposed improved exact strategy;
6. explain the proposed bound;
7. explain the proposed first heuristic; and
8. identify what each team member is working on next.

You are not expected to have the improved exact algorithm or heuristic completed before the review.

However, the team should be able to show that work has moved beyond merely discussing the project. If you have already started implementing the next algorithms, bring that work even if it is incomplete.

After the review

Record the important feedback and use it immediately during Checkpoint 2. The instructor may recommend that the team revise an algorithmic approach, correct a misunderstanding, replace an invalid or unhelpful bound, simplify a heuristic, or prioritize a particular implementation or testing task.

Grading

4 - Checkpoint 2: Improved Algorithms

Goal: Move beyond complete-candidate enumeration by implementing a more selective exact algorithm, developing a polynomial-time method for bounding the optimal solution value, and implementing the first scalable heuristic.

Checkpoint 1 established an exhaustive baseline by generating complete candidate solutions before testing them. In Checkpoint 2, you will use information about partial solutions or subproblems to fail early and avoid generating large portions of that candidate space. The improved algorithm must remain exact—that is, it must still return an optimal solution.

Points: 30

Checkpoint 2 has two parts: Implement and Validate and Analyze and Compare. The written analysis produced in Part B belongs in reports/checkpoint2.pdf. Organize the report using clearly labeled sections corresponding to the four analysis topics in Part B.

Part A: Implement and Validate

A1. Improved exact solver (improved.py)

Implement a fully functioning improved exact solver that:

• follows the common programming interface;
• remains exact: whenever it terminates, it returns an optimal solution;
• uses an exact technique such as backtracking, pruning, branch-and-bound, memoization, dynamic programming, or problem-specific structural reasoning;
• demonstrates a clear measurable improvement over the Checkpoint 1 exhaustive baseline; and
• completes selected larger instances that are beyond the practical range of straightforward complete enumeration.

A recursive implementation is not required. What matters is the algorithmic distinction: the improved solver must use information discovered during the search to avoid work that the Checkpoint 1 complete-enumeration solver would have performed.

The improved solver must not simply repackage the same complete-candidate enumeration in a recursive function.

A2. Polynomial-time bound (bound.py)

Implement the required bound function using the interface provided in your problem package.

A bound is a value that is guaranteed to lie on one side of the optimal solution value. A lower bound can never exceed the optimum, while an upper bound can never be smaller than the optimum. Your problem specification identifies which type of bound you must compute, and your implementation must produce a valid bound for every input instance. The function must:

• return a numeric bound on the optimum in the direction documented for your problem;
• be valid for every legal input instance;
• run in polynomial time; and
• be strong enough to provide useful information on the representative Checkpoint 2 tests.

The public tests check the bound independently of the solvers. On instances whose optimum is known, they verify that the bound does not cross the optimum in the wrong direction. Selected tests also check that the bound is nontrivial and that it scales to substantially larger instances.

You may reuse the bound inside the improved exact solver when it is useful for pruning or branch-and-bound. The improved solver is not required to use the supplied bound function if another exact strategy is more appropriate, but your report should explain the relationship between the bound and the exact search. The bound may also be useful inside your improved exact algorithm. For example, it may provide information that allows a branch or partial solution to be pruned without further exploration.

A3. First heuristic (heuristic1.py)

Implement a fully functioning heuristic1 that:

• follows the common programming interface;
• always returns a valid solution;
• runs in polynomial time and completes within the allowed time on instances substantially larger than those used for exact search;
• uses a randomized component and performs multiple starts, restarts, or repeated randomized attempts;
• retains the best valid solution found so far as additional attempts are performed;
• supports reproducible execution using --seed; and
• does something meaningfully more sophisticated than returning a trivial valid solution.

For any heuristic that uses randomness, multiple starts, restarts, or repeated attempts, best-so-far behavior is required. Once a valid solution has been found, additional work may improve the result, but the algorithm must not discard a better solution found earlier.

This requirement is intentional. A simple greedy solution may be the first feasible answer your heuristic finds, but later challenge benchmarks ask how much better you can do through randomized restarts, iterative improvement, local search, or other repeated attempts. The algorithm should therefore behave sensibly as an anytime method: it can return the best solution found so far, and additional allowed work has the opportunity to improve that solution.

Three-person teams should also begin developing their second heuristic during this checkpoint, but heuristic2 is not graded as a completed algorithm until the Final Project. The second heuristic must be meaningfully different from the first; it may be deterministic if its algorithmic strategy is genuinely different.

A4. Public testing and validation

Run the Checkpoint 2 public tests from the root of your repository:

python tools/run_cp2_tests.py

The local checker displays detailed student-code diagnostics, including file and line information, by default. To request a more compact display, use:

python tools/run_cp2_tests.py --quiet

Use the public tests to correct interface, correctness, bound, heuristic, and performance problems before submitting to Gradescope.

The Checkpoint 2 exact-solver tests use two kinds of instances:

• bridge instances, on which both the Checkpoint 1 exhaustive solver and the improved exact solver can finish, allowing their computational behavior to be compared; and
• separation instances, selected to be beyond the practical range of straightforward complete-candidate enumeration but solvable by a reasonable improved exact approach.

Gradescope uses additional private instances, instructor-controlled timing, and independent solution validation. Student-reported counters are useful for analysis but are not trusted as the sole evidence of correctness or performance.

Part B: Analyze the Algorithms

B1. Bound analysis

Analyze the polynomial-time bound that you implemented in bound.py.

Explain:

• what value the bound computes;
• why the value is guaranteed to be a valid upper or lower bound on the optimal solution value;
• the asymptotic running time of the bound computation; and
• whether and how your improved exact solver uses the bound.

If your improved exact solver does not use the bound, briefly explain why not.

B2. Improved exact algorithm reflection

Compare the improved exact algorithm you implemented with the design you proposed in Checkpoint 1.

Discuss:

• whether the implemented algorithm differs from your Checkpoint 1 design and, if so, why;
• which techniques actually proved useful for avoiding work performed by the Checkpoint 1 exhaustive baseline;
• where the algorithm is able to fail early, prune, reuse previous results, or otherwise avoid generating complete candidates;
• what you learned while implementing and testing the algorithm; and
• any weaknesses or types of instances that remain difficult.

Use your experimental results to support the discussion. In particular, explain at least one clearly defined work measure for the improved exact algorithm and how it compares with the complete-candidate count from Checkpoint 1.

Briefly explain why the implemented algorithm remains exact—that is, why the techniques used to avoid work cannot eliminate an optimal solution.

You do not need to repeat the full algorithm design from Checkpoint 1 unless the implemented algorithm changed substantially.

B3. Heuristic reflection

Compare the heuristic you implemented with the plan you proposed in Checkpoint 1.

Discuss:

• whether the implemented strategy differs from your Checkpoint 1 plan and, if so, why;
• what you learned while implementing and testing the heuristic;
• how randomness and repeated attempts affect the solutions produced;
• how solution quality varies across the instances you have tested; and
• any weaknesses or failure patterns you have observed so far.

You do not need to repeat the full algorithm description from Checkpoint 1 unless the implemented strategy changed substantially.

Discuss the quality of the solutions produced by the heuristic on the instances you have tested so far.

B4. Preliminary experimental comparison

Compare the algorithms developed so far using a small collection of appropriate test instances. The Experimental Evaluation page outlines guidance on running, recording, and interpreting experimental comparisons that will be required to complete this section.

Your comparison should include:

• the Checkpoint 1 exhaustive solver;
• the improved exact solver; and
• heuristic1.

At minimum, report:

• elapsed running time;
• the Checkpoint 1 complete-candidate count;
• at least one clearly defined work measure for the improved exact solver; and
• the solution value returned by each algorithm where comparison is meaningful.

Include at least one table or figure summarizing the results.

Use your results to discuss:

• how much work the improved exact algorithm avoids relative to the Checkpoint 1 baseline;
• how the practical range of the improved exact algorithm compares with the exhaustive baseline; and
• how the speed and solution quality of the heuristic compare with the exact algorithms.

Submission checklist

• The Checkpoint 1 verifier and exhaustive baseline continue to pass the required tests.
• The improved exact solver remains exact, avoids substantial portions of the Checkpoint 1 candidate space, and shows measurable improvement on the required bridge and separation instances.
• The required polynomial-time bound function is implemented and passes the public validity, nontriviality, and scalability tests.
• heuristic1 always returns a valid solution and runs in polynomial time on the required larger instances.
• heuristic1 uses randomness and repeated attempts or restarts, retains the best valid solution found so far, and supports reproducible execution with --seed.
• reports/checkpoint2.pdf contains the four required analysis sections and at least one preliminary table or figure.
• The preliminary comparison includes the Checkpoint 1 complete-candidate count and at least one clearly defined work measure for the improved exact solver.
• python tools/run_cp2_tests.py passes.
• All current work has been committed and pushed to GitHub.
• The repository has been submitted to the Checkpoint 2 Gradescope assessment with all team members included in the Gradescope group.

Grading

Previously graded Checkpoint 1 work is used as a baseline and may be checked mechanically for continuity, but it is not assigned a second set of points here.

Assessment. The Gradescope assessment is cumulative. Automated checks will verify the existing baseline and programming interfaces, exact correctness of the improved solver, instructor-measured improvement on bridge instances, successful completion of selected larger separation instances, correctness and scalability of the bound function, heuristic validity and scalability, reproducibility where required, and the required PDF artifact.

Student-reported work counters support the analysis but are not used as the sole evidence that an algorithm is faster or correct.

The written report will be reviewed for the implemented exact-search strategy, explanation of what complete-candidate work is avoided, the exactness argument, the bound argument, the heuristic design, and the quality of the preliminary comparison.

5 - Final Project: Experimental Investigation and Synthesis

Goal: Use the completed algorithms and bound to determine where the methods are practical, how heuristic solution quality behaves, what characteristics of an instance affect algorithm behavior, and what conclusions are justified by the evidence.

Points: 30

The Final Project combines the experimental investigation and final synthesis into one submission. The course provides the required benchmark collections and experiment-running infrastructure. You are not required to write a benchmark harness or create the required benchmark universe yourself.

Checkpoint 1 and Checkpoint 2 already assessed the exhaustive baseline, improved exact solver, bound, and first heuristic. Those components remain necessary because the final experiments depend on them, and the final submission may run mechanical continuity checks, but the Final Project does not award a second set of points simply for re-demonstrating work that was already graded.

Part A: Complete the Remaining Team-Size Requirement

A1. Second heuristic for three-person teams (heuristic2.py)

Three-person teams must implement a functioning heuristic2 that is meaningfully different from heuristic1.

A second heuristic must differ in algorithmic strategy, not merely in parameters, time limits, restart counts, random seeds, or other tuning choices. It may be deterministic if its algorithmic strategy is genuinely different.

Two-person teams are not required to implement a second heuristic. They may do so as an approved extension.

The goal is not to guarantee that the second heuristic is better. A well-motivated heuristic that performs poorly on some instances can still produce valuable experimental evidence. For three-person teams, the Final Project assesses whether heuristic2 is valid, meaningfully different, and incorporated thoughtfully into the experimental comparison.

Part B: Investigate Algorithm Behavior

The project template provides a course-controlled experiment runner and problem-specific benchmark suites. The runner records the instance, algorithm, seed, course-controlled wall-clock time, returned objective value, bound value, known optimum when available, and other metadata needed for analysis.

Before beginning the final investigation, review Experimental Evaluation for guidance on benchmark comparisons, repeated randomized trials, bounds, structural experiments, and reproducibility.

Students are responsible for running the required experiments, checking the resulting data, and interpreting what the data means. You may add your own instances or experiments, but the course-provided suites are sufficient to satisfy the core Final Project requirements.

B1. Exact-search frontier

Use the course-provided exact_frontier suite to compare the exhaustive solver (exhaustive.py) with the improved exact solver (improved.py).

Identify where exhaustive search becomes impractical and how much farther the improved exact method extends exact computation. Your analysis should focus on the change in practical solvability, not merely on reporting individual running times.

B2. Heuristic quality and certified bounds

Use the course-provided quality and scale suites to evaluate heuristic1 and, for three-person teams, heuristic2.

For instances whose optimum is known, compare heuristic solution quality directly with the optimum and examine how informative the implemented bound is.

For larger instances where the exact optimum is not available within the allowed computation time, use the bound on the optimal solution value implemented in Checkpoint 2 (bound.py) together with the best feasible solution found by the heuristic. Interpret the resulting interval correctly. Do not describe an unknown value as optimal merely because the exact solver did not finish.

For randomized heuristics, use the repeated course-provided seeds to discuss variability rather than drawing conclusions from a single lucky or unlucky run.

Optional challenge/leaderboard results may strengthen this analysis, especially when they show how a heuristic improves with additional restarts, local search, or algorithm revisions. Leaderboard position alone is not sufficient evidence. For open instances, clearly distinguish a best-known feasible solution from a proven optimum and use the appropriate bound to describe what remains unknown.

B3. Effect of instance structure

Use the course-provided structure benchmark suite for your assigned problem. The benchmark suite varies one meaningful structural characteristic while controlling other important aspects of the instances as much as practical.

Analyze how that characteristic affects at least one of the following:

• exhaustive or improved-exact computational effort;
• the practical boundary of exact computation;
• heuristic solution quality; or
• the gap between a feasible heuristic solution and the certified bound.

The required structural characteristic is specified with the benchmark family for your problem. You are not required to invent a structural variable or generate the required instances yourself.

B4. Informative instance and explanation

Select at least one instance or small group of related instances that reveals something important about the algorithms. Examples include an unexpectedly difficult instance, an unexpectedly easy instance, a case where a heuristic performs unusually well or poorly, a sharp change in exact running time, or a case where the bound is particularly strong or weak.

Explain what the evidence shows and give a plausible algorithmic explanation. Distinguish measured evidence from hypotheses about why the behavior occurred.

Part C: Synthesize and Communicate the Investigation

C1. Final report

Store the report in:

reports/final.pdf

Aim for approximately three pages of text, not counting figures, tables, and references. Do not repeat the checkpoint reports. Instead, synthesize the investigation around four questions:

1. What approaches did you try? Briefly identify the exhaustive exact, improved exact, and heuristic approaches needed to understand the results.
2. What happened? Present the most important experimental evidence rather than an inventory of every run.
3. Where did the methods work or fail? Discuss the exact-search frontier, heuristic quality, what the bound certifies when OPT is unavailable, and the effect of input structure.
4. What did you learn? State the most important conclusions supported by the evidence.

Your informative instance or related group of instances should appear in the final report or presentation.

C2. Class presentation

Tell the story of the investigation rather than reproducing the report section by section. Address the problem studied, where exhaustive search became impractical, what the improved exact approach changed, how the heuristic strategy or strategies behaved, what the bound could certify when OPT was unavailable, the most informative structural or instance-level result, and what surprised the team.

Every team member must present a meaningful portion of the project. Figures, tables, or example instances should be readable and chosen because they support the story rather than because they happen to be available.

Store the final slides in:

presentation/slides.pdf

C3. Peer questions and discussion

Each team will be assigned at least one other team’s problem or presentation to examine and will submit three substantive questions:

• one about an algorithmic decision;
• one about experimental evidence; and
• one about whether an idea could transfer between the two problems, or why the problems behave differently.

Formative Experimental Check

Before the Final Project is due, there will be a lightweight formative check rather than another graded checkpoint. Be prepared to show that the required experiment pipeline is running, bring at least one preliminary result or figure, and explain the story you currently expect the final presentation to tell.

The purpose of this check is to identify experimental or presentation problems while there is still time to correct them. It does not create another Gradescope submission or another set of project points.

Grading

Submission checklist

• The previously graded required algorithms and bound still run through the documented interfaces so that the final experiments are reproducible.
• Three-person teams have a valid, meaningfully different heuristic2 and include it in the heuristic comparison.
• The required course-provided experimental suites have been run using the provided infrastructure.
• The exact-search frontier is analyzed using the exhaustive and improved exact solvers.
• Heuristic quality is evaluated against known optima where available.
• On larger instances, heuristic results are interpreted together with the implemented bound rather than treating an unknown optimum as known.
• The required problem-specific structural benchmark family is analyzed.
• At least one informative instance or related group of instances is identified and explained.
• reports/final.pdf is complete.
• presentation/slides.pdf is complete.
• All current work and generated experiment results have been committed and pushed to GitHub.
• The repository has been submitted to the Final Project Gradescope assessment with all team members included in the Gradescope group.

Assessment. Gradescope may be used for mechanical validation of interfaces, required artifacts, and experiment-result structure. The substantive Final Project points are instructor-reviewed according to the table above.

6 - Approved Add-ons and Extensions

Optional add-ons allow a team to pursue an idea beyond the core requirements without creating another checkpoint or an alternate path around required work. Examples include a polynomial-time special case, a stronger exact method, an additional heuristic, adversarial-instance generation, parameter-sensitivity analysis, a reduction experiment, a larger benchmark universe, or parallel benchmark execution.

A team that wants to pursue an add-on should propose it no later than the Checkpoint 2 submission. The proposal should identify what will be built or investigated, how success will be evaluated, and how the work complements the required project. The instructor must approve the scope before the team treats it as part of the project plan.

Approved add-ons should appear naturally in the Final Project experiments and, when they produce a meaningful result, in the final report or presentation. They do not replace core checkpoint requirements. Unless the instructor explicitly designates an add-on as extra credit, add-on work is evaluated within the Final Project criteria and does not increase the project beyond its published 100 points.

For three-person teams, the required second heuristic is part of the core project and is not an add-on.