Checkpoint 2: Foundation

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

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

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 2 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 2 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 3.

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 2 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 2 baseline.

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

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 2 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 2 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 2 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 3 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 2 candidate space.

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 2 does not require the bound function to be implemented, and the Checkpoint 2 public tests do not call it.

Heuristic plan

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

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 2 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/checkpoint2.pdf contains the six required analysis sections.
• The improved exact design explains how the Checkpoint 3 solver will avoid portions of the 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_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.

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 design meeting. Shortly after Checkpoint 2, 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 2 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.