Checkpoint 3: 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 2 established an exhaustive baseline by generating complete candidate solutions before testing them. In Checkpoint 3, 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.

Checkpoint 3 has two parts: Implement and Validate and Analyze and Compare. The written analysis produced in Part B belongs in reports/checkpoint3.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 2 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 2 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 3 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.

Three-person teams may begin developing their second heuristic during this checkpoint, but the second heuristic is not required until Checkpoint 4. 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 3 public tests from the root of your repository:

python tools/run_cp3_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_cp3_tests.py --quiet

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

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

• bridge instances, on which both the Checkpoint 2 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 2.

Discuss:

• whether the implemented algorithm differs from your Checkpoint 2 design and, if so, why;
• which techniques actually proved useful for avoiding work performed by the Checkpoint 2 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 2.

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 2 unless the implemented algorithm changed substantially.

B3. Heuristic reflection

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

Discuss:

• whether the implemented strategy differs from your Checkpoint 2 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 2 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.

Your comparison should include:

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

At minimum, report:

• elapsed running time;
• the Checkpoint 2 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 2 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 2 verifier and exhaustive baseline continue to pass the required tests.
• The improved exact solver remains exact, avoids substantial portions of the Checkpoint 2 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/checkpoint3.pdf contains the four required analysis sections and at least one preliminary table or figure.
• The preliminary comparison includes the Checkpoint 2 complete-candidate count and at least one clearly defined work measure for the improved exact solver.
• python tools/run_cp3_tests.py passes.
• All current work has been committed and pushed to GitHub.
• The repository has been submitted to the Checkpoint 3 Gradescope assessment with all team members included in the Gradescope group.

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.