Projects

1 - Beyond Brute Force

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:

• What makes the problem computationally difficult?
• What work can be reused or safely avoided while preserving optimality?
• When exact computation becomes intractable in practice, how effectively can a heuristic find good solutions?
• What characteristics of an input make a particular algorithm succeed or struggle?

Learning Objectives

By completing this project, you will be able to:

• explain the relationship between an NP-complete decision problem and its optimization version;
• implement and analyze a baseline exhaustive exact algorithm;
• reason about the state of a recursive search and whether repeated subproblems are present;
• improve exact computation using an appropriate algorithm-design technique;
• explain why an improved exact method remains correct;
• design and evaluate a heuristic algorithm for instances where exact computation becomes intractable in practice;
• use exact optima and appropriate bounds to evaluate solution quality;
• perform controlled experiments across a collection of problem instances;
• identify input characteristics that affect computational effort and heuristic solution quality; and
• communicate algorithmic conclusions using experimental evidence.

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.

• An exact algorithm is guaranteed to return an optimal solution when it terminates.
• An improved exact algorithm is still exact, but reduces the computation performed by the exhaustive baseline.
• A heuristic algorithm returns a valid solution but does not necessarily guarantee optimality. For this project, heuristic algorithms must run in polynomial time so that they can scale to instances for which exact computation becomes impractical.

Project Problems

Each team will study one of the following problem families:

• Traveling Salesperson Problem
• Minimum Graph Coloring
• Minimum Vertex Cover
• Longest Path
• Maximum Clique

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.

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.

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:

• theory and algorithmic reasoning;
• correctness and analysis of the exhaustive exact baseline;
• design and evaluation of the improved exact algorithm;
• design and evaluation of the heuristic algorithm or algorithms;
• experimental design, evidence, and interpretation; and
• reproducibility, teamwork, and communication.

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.

1.1 - Checkpoints and Final Submission

The project is organized around four checkpoints followed by the final submission. Each checkpoint now has its own page so that requirements, checklists, and assessment details are easier to navigate.

Checkpoint 1: Project Selection and Setup

Open Checkpoint 1

Checkpoint 2: Foundation

Open Checkpoint 2

Checkpoint 3: Improved Algorithms

Open Checkpoint 3

Checkpoint 4: Experimental Investigation

Open Checkpoint 4

Approved Add-ons and Extensions

Open Add-ons and Extensions

Final Project Submission

Open Final Project Submission

Shared checkpoint conventions

For each checkpoint, commit and push your work to the team GitHub repository and submit the current repository to the corresponding Gradescope assessment. Public tests and experiment infrastructure are included in the project template; Gradescope may also use hidden tests following the documented interfaces. Student algorithm work belongs under src/student/; files under src/course/ are project-maintained infrastructure.

1.1.1 - Checkpoint 1: Getting Started and Project Selection

Checkpoint 1: Getting Started and Project Selection

Goal: Set up your team repository, verify that every team member can work with it, and provide the information needed for project assignment.

Getting Started

Before completing the Checkpoint 1 requirements, review the Project Repository and Infrastructure page. It explains how to create your team repository through Classroom 50, clone it, and understand the organization of the provided course infrastructure and student implementation files.

Once your repository is set up, complete the requirements below.

Requirements

1. Shared repository access

Every team member must be able to work with the shared repository. During Checkpoint 1, each team member should clone the repository and make and push at least one commit.

2. Team and project information

Complete the root-level project.json file with:

• your team name;
• each team member’s name and GitHub username; and
• three distinct project preferences, listed from most preferred to least preferred.

Leave assigned_problem blank until project assignments are announced.

Use the following canonical project identifiers exactly as shown in project_preferences:

Your three preferences must use three different identifiers from this table. These long identifiers are used in project.json; shorter names such as mvc and tsp are command-line aliases used later with src/solve.py.

Submission checklist

• project.json is complete and contains three ranked project preferences.
• Every team member has successfully contributed to the shared repository.
• 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.

Assessment. Gradescope will validate the required repository structure and project.json. The instructor may inspect the repository history to verify team access and participation and will use the ranked preferences to assign projects.

1.1.2 - Checkpoint 4: Experimental Investigation

Goal: Use the completed algorithms and bound to determine where the methods are practical, how solution quality changes when exact computation is no longer available, and what characteristics of an instance affect algorithm behavior.

Checkpoint 4 shifts the emphasis from implementation to controlled experimental investigation. 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.

Part A: Extend the Algorithm Portfolio

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 the underlying method is genuinely different.

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

Part B: Investigate Algorithm Behavior

The project template provides a course-controlled experiment runner and problem-specific benchmark suites. The required suites are organized around different computational regimes and experimental questions. 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 later analysis.

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 Checkpoint 4 requirements.

B1. Exact-search frontier

Use the course-provided exact-search benchmark 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 suites to evaluate the first heuristic (heuristic1.py) and, for three-person teams, the second heuristic (heuristic2.py).

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

B3. Effect of instance structure

Instance structure can affect algorithm behavior for exact solvers and solution quality for heuristic approaches. In this section, you will investigate one such effect using the course-provided structure benchmark suite for your assigned problem.

The benchmark suite identifies the structural characteristic being varied and provides instances designed to vary that 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 the 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.

Checkpoint report

Focus on what the experiments reveal rather than repeating the implementation descriptions from earlier checkpoints. Organize reports/checkpoint4.pdf around the four investigation topics above. For three-person teams, briefly describe the second heuristic where it is needed to interpret the comparison.

The report should emphasize a small number of well-supported observations rather than a large collection of unexamined tables.

Presentation outline

Prepare a concise outline of the final presentation in:

presentation/outline.pdf

The outline should identify the intended story of the presentation: the problem, where straightforward exhaustive search became impractical, what the improved exact method changed, how the heuristic or heuristics behaved, the role of the bound when OPT was unavailable, the most informative structural or instance-level result, and the conclusions the team expects to emphasize.

Submission checklist

• Three-person teams have a meaningfully different second heuristic.
• 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/checkpoint4.pdf is complete.
• presentation/outline.pdf is complete.
• All current work and generated experiment results have been committed and pushed to GitHub.
• The repository has been submitted to the Checkpoint 4 Gradescope assessment with all team members included in the Gradescope group.

Assessment. Gradescope will verify the required algorithm interfaces, bound interface, experiment-result artifacts, and other mechanical requirements. Instructor review will focus on the quality of the experimental comparisons, correct interpretation of optima and bounds, evidence about structural effects, and the explanations supported by the observed data.

1.1.3 - 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 3 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 Checkpoint 4 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 existing Checkpoint 4 and 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.

1.1.4 - Final Project Submission

The final project consists of the complete repository, a concise report, a class presentation, and peer questions.

Complete repository.

The repository should contain the final implementations, tests, experimental scripts, results, checkpoint reports, and presentation materials. Someone outside your team should be able to clone the repository and reproduce the important results by following the instructions in README.md. The final Gradescope assessment will perform a cumulative validation of the required repository structure and algorithm interfaces.

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 what you learned around four questions:

1. What approaches did you try? Briefly describe the straightforward exact, improved exact, and heuristic approaches.

2. What happened? Present the most important experimental results.

3. Where did the methods work or fail? Discuss solution quality, computational effort, running time, what the bound can certify 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 interesting or difficult instance should appear in the final report or presentation.

Class presentation.

Tell the story of the investigation rather than reproducing the report section by section. Address the problem studied, where the straightforward exact approach became impractical, how exact computation was improved, the heuristic strategy or strategies, what the bound could certify when OPT was unavailable, the most interesting result or instance, and what surprised the team. Every team member must present a meaningful portion of the project.

Store the final slides in:

presentation/slides.pdf

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 their behavior differs.

1.1.5 - Checkpoint 2: Foundation

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.

1.1.6 - Checkpoint 3: Improved Algorithms

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.

1.2 -

Beyond Brute Force — CP4 Experiment Infrastructure Plan

Design principle

Checkpoint 4 should assess experimental reasoning, not whether students can build a benchmarking framework. The course should provide the required instance collections, runner, timing, validation, metadata, and result-file format. Students run the experiments, inspect the resulting data, and explain what the evidence shows.

The infrastructure should also make instructor validation easy: required results are machine-generated in a standard format, benchmark instances are course-controlled, and Gradescope can rerun a small subset of the same manifest.

Proposed student-visible layout

benchmarks/
  minimum_vertex_cover/
    manifest.json
    exact_frontier/
    quality_known/
    heuristic_scale/
    structure/
  ... one directory per problem ...

tools/
  run_experiments.py
  experiment_framework/
    runner.py
    validation.py
    problem_checks/

experiments/
  results.csv
  results.json
  run_metadata.json

benchmarks/ and tools/experiment_framework/ are COURSE INFRASTRUCTURE. Students should not need to modify them. experiments/ contains generated results that students commit with CP4.

Required benchmark suites

Each problem manifest should define four course-provided suites. The manifest, rather than student code, decides which algorithms run on which instances and what timeout/repeat policy applies. This prevents students from accidentally running exhaustive search on instances where it can never finish.

1. exact_frontier

Purpose: determine where straightforward exhaustive search becomes impractical and how much farther the improved exact solver reaches.

• Runs exhaustive and improved on an ordered family of increasingly challenging instances.
• Uses instructor-controlled wall-clock timing.
• Records TIMEOUT as a legitimate experimental outcome rather than a failed experiment.
• Uses known optima so correctness remains checkable.

2. quality_known

Purpose: measure heuristic quality and bound quality while OPT is still known.

• Runs the required heuristic(s) on instances with known optimum.
• Runs the CP3 bound function on the same instances.
• Records heuristic objective, OPT, bound, and the certified interval.
• Uses a small fixed set of course-provided seeds for randomized heuristics so variability can be observed without students manually managing runs.

3. heuristic_scale

Purpose: evaluate useful solutions after exact computation is no longer practical.

• Runs the heuristic(s) and the bound, not straightforward exhaustive search.
• The improved exact solver may be run only on instances specifically designated as feasible in the manifest.
• OPT may be unknown. The student interprets the feasible heuristic value together with the certified bound rather than claiming optimality.

4. structure

Purpose: examine how one controlled characteristic of the input affects behavior.

• The course supplies the instances and identifies the structural variable.
• Use several instances per structural setting when randomness is involved, rather than drawing conclusions from one graph.
• Keep size and other major variables fixed or documented as closely as practical.

Initial structural-family plan:

The TSP family should be finalized only after instructor pilot runs confirm that it produces an interpretable algorithmic effect; graph density is not meaningful because all TSP instances are complete.

Bound interface used by the runner

Each problem package exposes course-controlled metadata and dispatch:

BOUND_KIND = "lower"   # or "upper"

def get_bound():
    ...                 # returns the student's required bound function

The student implementation remains mathematically natural inside bound.py:

def lower_bound(instance) -> int | float:
    ...

or

def upper_bound(instance) -> int | float:
    ...

Proposed directions for the five current problems:

• Minimum Vertex Cover: lower bound
• Traveling Salesperson: lower bound
• Minimum Graph Coloring: lower bound
• Maximum Clique: upper bound
• Longest Path: upper bound

This lets a student reuse the same function inside branch-and-bound while the experiment runner can call it generically through get_bound().

Runner behavior

The intended commands are simple:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

A convenience --all option can run all required suites.

The runner should:

1. read assigned_problem from project.json;
2. load the course manifest for that problem;
3. run only the algorithms specified for each benchmark row;
4. measure wall-clock time independently with perf_counter();
5. retain student-reported statistics separately rather than trusting them as timing evidence;
6. run the problem’s independent course validator on every returned solution;
7. call the CP3 bound function once per instance;
8. record known OPT when supplied by the manifest;
9. use fixed manifest-provided seeds for randomized runs;
10. write both row-oriented CSV and full JSON results; and
11. never abort an entire suite because one algorithm times out on one instance.

For short-running exact cases, the manifest can request multiple repetitions and the runner can report the median instructor-timed runtime. Long-running cases should normally use one repetition to keep the CP4 workload reasonable.

Proposed result columns

At minimum, each generated row should contain:

problem
suite
instance_id
instance_sha256
size metadata (for example n and m)
structure_name
structure_value
algorithm
seed
status          # OK / TIMEOUT / ERROR
valid           # independent feasibility check
objective
known_optimum
bound_kind
bound_value
wall_time
student_time
statistics_json

The JSON output can preserve additional problem-specific metadata without making the CSV unwieldy.

What students should actually have to analyze

To keep CP4 from becoming overloaded, the required intellectual work should stay to three core comparisons plus one explanatory example:

1. Exact frontier: Where does exhaustive search stop being practical, and what does the improved exact method buy?
2. Heuristic quality: How close are heuristic results to OPT on small instances, and what can the bound certify on larger instances?
3. Structural effect: How does the one course-selected structural variable affect performance or solution quality?
4. Informative instance: Identify and explain one especially revealing case from any of the three analyses.

Students should not be required to invent additional benchmark families, write timing code, write CSV code, or build plotting infrastructure. Additional experiments remain optional extensions.

Instructor / Gradescope validation strategy

The CP4 autograder should not attempt to grade the students’ scientific conclusions. It can cheaply validate the experimental foundation:

• required generated files exist and have the expected schema;
• every required suite and instance ID is represented;
• required algorithms were run where the manifest says they should be run;
• bound values have the correct direction on known-optimum instances;
• reported solution objectives agree with independent validation;
• fixed seeds and instance hashes match the course manifest; and
• a small hidden subset can be rerun to catch fabricated or stale result files.

Instructor review then evaluates the interpretation, plots/tables, structural reasoning, and informative-instance explanation.

Suggested implementation order

1. Finish the MVC path first: create the four MVC CP4 suites and the generic runner.
2. Use MVC to settle the result schema and CP4 autograder checks.
3. Reuse the framework for Clique, Coloring, Longest Path, and TSP by supplying problem adapters, bound metadata, and manifests.
4. Pilot each structural family before publishing it to students; especially pilot the TSP weight-structure family.

1.3 -

Beyond Brute Force — website source snapshot

This directory contains the current Beyond Brute Force Hugo content supplied for the course website.

The current source-tree ownership model is documented in repository.md and program-interface.md:

• src/course/ — course-owned infrastructure;
• src/student/ — student-owned implementations; and
• src/solve.py — course-owned command-line launcher.

Checkpoint requirements are split across the pages in checkpoints/.

Files with names such as checkpoints-monolithic-backup.md, _index copy.md, and the older specs_*.md files appear to be retained working/archive copies. They should not be treated as the authoritative pages unless intentionally published.

1.4 -

Website update notes — course/student source split

This revision uses the supplied bbf.zip as the authoritative starting snapshot.

Architecture established

• src/course/ is course-owned infrastructure.
• src/student/ is student-owned implementation code.
• src/solve.py remains a course-owned launcher.
• project.json remains at the repository root and its schema is unchanged by this restructuring.

Pages changed

• _index.md
• repository.md
• program-interface.md
• graph-interface.md
• minimum-vertex-cover.md
• traveling-salesperson.md
• graph-coloring.md
• longest-path.md
• maximum-clique.md
• checkpoints/_index.md
• README.md

Also corrected

The main _index.md now links directly to the split Checkpoint 1 and Final pages and uses the current names/descriptions for Checkpoints 3 and 4. The Classroom 50 link is also resolved to the current assignment URL used on repository.md.

Files worth reviewing/removing from published Hugo content

The supplied snapshot contains apparent older/archive copies, including:

• _index copy.md
• checkpoints.md
• checkpoints-monolithic-backup.md
• several specs_*.md files

They were preserved in this returned snapshot rather than deleted automatically. If they live directly in the Hugo content directory, consider moving them outside published content so they cannot create duplicate/stale pages.

1.5 - Benchmark Suites

The course provides benchmark collections and experiment-running infrastructure so that Checkpoint 4 can focus on algorithmic interpretation, not on writing a benchmark harness.

The benchmark definitions live in the team repository under:

benchmarks/

and are controlled by problem-specific manifest.json files. The manifest records which algorithms should run, time limits, fixed random seeds, structural metadata, and a known optimum when the exact value is available.

Required suites

Each fully supported problem provides:

• readiness — a small Checkpoint 3 smoke test;
• exact_frontier — straightforward exhaustive versus improved exact;
• quality_known — heuristic and bound quality where OPT is known;
• heuristic_scale — large instances where exact computation may be unavailable;
• structure — a course-selected structural comparison.

Run a suite from the repository root:

python tools/run_experiments.py --suite readiness
python tools/run_experiments.py --suite exact_frontier

Generated results are written under experiments/ in CSV and JSON form.

Known answers and bounds

A manifest field named known_optimum is instructor benchmark metadata. The bound_value in generated results is not supplied by the course; it is the value returned by your Checkpoint 3 bound function.

For a minimization problem, if a row reports:

known_optimum = null
bound_value   = 117
objective     = 126

then the evidence certifies only:

Established external benchmarks

The required core suites are already present in the repository and do not need network access. The course also provides optional installation tools for established public benchmark collections:

• PACE 2019 Vertex Cover Exact instances for additional large/hard MVC experiments;
• selected TSPLIB95 TSP instances with published proven optima; and
• selected University of Waterloo National TSP instances, including both proven-optimal instances and larger open instances with published best-known tours and certified lower bounds.

Install optional collections with:

python tools/install_external_benchmarks.py pace2019-vc
python tools/install_external_benchmarks.py tsplib
python tools/install_external_benchmarks.py waterloo-tsp

Large Euclidean TSP instances remain in coordinate form. The course WeightedGraph computes the required integer edge weight when graph.weight(u, v) is called rather than expanding a complete graph into $\binom{n}{2}$ stored edges.

For a TSP instance with a proven optimum, experiment output may report a percentage gap from OPT. For an open instance, the output instead identifies its published best-known tour and published lower bound. A best-known tour must not be described as optimal unless optimality has been proven.

The optional TSP leaderboard aggregates repeated randomized trials by taking the median percentage gap for each known-OPT instance and then averaging those instance medians. The open reach suite is reported separately and is never scored as though its best-known tours were proven optimal.

Randomized heuristic trials

Required heuristic suites use several fixed course-provided seeds. The runner preserves every run rather than collapsing them into one number. Your analysis should therefore consider variation across runs, especially variation in returned solution value and, where meaningful, wall-clock time.

You are not required to perform formal statistical inference. Useful summaries may include the best and worst result, mean or median, range, or another clearly explained summary that helps characterize how stable the heuristic is.

geng and non-isomorphic graphs

For the four unweighted graph problems, the course wrapper can call Brendan McKay’s geng program from nauty to generate non-isomorphic graphs. Core CP4 does not require geng; required structural instances are already supplied.

geng is not used for TSP benchmark generation. Every symmetric TSP instance in this project is a complete graph, so if weights are ignored the underlying graph is simply $K_n$ and there is only one unweighted graph up to isomorphism. The important TSP variation is in the edge weights: geometric layout, clustering, weight distribution, and related structure. TSP benchmark families are therefore generated by varying those weight-producing mechanisms rather than by enumerating non-isomorphic unweighted graphs.

After installing nauty, an optional graph-problem suite can be generated with, for example:

python tools/generate_geng_suite.py \
    --n 9 --edges 12:20 --connected --limit 300

The wrapper detects both the geng command used by Homebrew installations and the nauty-geng command used by Ubuntu packages.

1.6 - Experimental Evaluation

The experimental study is a team activity and is the point where the different algorithmic approaches come back together.

Your team will compare:

• the exhaustive exact algorithm;
• the improved exact algorithm;
• heuristic 1; and
• heuristic 2, for three-person teams.

The goal is not simply to determine which program is fastest or which heuristic wins the most benchmark cases. The goal is to understand where each approach works, where it struggles, and why.

Ground Truth and Bounds

Whenever possible, compare heuristic solutions with an exact optimum.

The instructor may provide precomputed optimal values for part of the benchmark collection. These values allow heuristic development and analysis to proceed independently of the speed of your team’s exact implementation.

When an exact optimum is unavailable, use a valid lower or upper bound when appropriate for your problem.

Coverage

For a heuristic, one useful measurement is the fraction of benchmark instances on which the heuristic finds an optimal solution:

where $N_{\mathrm{opt}}$ is the number of benchmark instances on which the heuristic finds an optimal solution and $N_{\mathrm{tested}}$ is the number of instances tested.

Coverage is not sufficient by itself. Two heuristics can have the same coverage while behaving very differently on the instances they miss. You should also measure the magnitude of the error or gap from the optimum.

Depending on your problem, useful measurements may include:

• absolute gap from OPT;
• relative or percentage gap from OPT;
• best, worst, mean, and median result across repeated trials;
• time to first feasible solution;
• improvement as additional trials or time are allowed; and
• variability across random seeds.

Input Structure

Input size alone may not explain algorithm difficulty.

Your experiments should therefore examine at least one meaningful structural characteristic of the input in addition to its size.

For an undirected graph $G=(V,E)$, graph density is:

A density of 0 represents a graph with no edges, while a density of 1 represents a complete graph.

For graph problems, benchmark collections may include all non-isomorphic graphs of selected sizes. This permits a systematic study of questions such as:

• Does the heuristic behave differently on sparse, intermediate-density, and dense graphs?
• Are there density ranges where finding an optimum is unusually difficult?
• Does pruning effectiveness depend on density or another structural feature?
• Do two different heuristics fail on the same graphs?
• Is the number of vertices alone a good predictor of difficulty?

Do not assume in advance that sparse, intermediate, or dense instances must be easier or harder. Treat these as empirical questions and let the data support your conclusions.

Problem specifications for non-graph problems will identify analogous structural measurements when appropriate.

Exact-Search Measurements

Running time is important, but it often does not explain why an improved exact algorithm performs differently.

Collect statistics appropriate to your implementation, such as:

• recursive calls;
• states expanded;
• branches pruned;
• candidate solutions considered;
• bound computations;
• maximal partial solutions reached; or
• another meaningful measure of search effort.

Use these measurements to compare the exhaustive and improved exact algorithms.

Interesting and Difficult Instances

Your team must identify at least one benchmark instance that helps explain an important feature of your algorithms.

Examples include:

• a small instance that causes a heuristic to perform poorly;
• an instance where two heuristics behave very differently;
• an instance where pruning is unusually effective;
• an instance where pruning provides almost no benefit;
• an instance that takes much longer than other inputs of similar size; or
• another surprising or informative case.

You should be able to show or describe this instance and explain what happens algorithmically.

For a graph problem, this may mean drawing the graph and tracing the choices that cause a heuristic to succeed or fail.

Where Experiment Files Belong

The repository provides three student-owned experiment locations:

experiments/
├── scripts/
├── results/
└── local/

Use experiments/scripts/ for team-created scripts that run, summarize, or analyze experiments. Commit scripts needed to reproduce important results.

Use experiments/results/ for results that are required by a checkpoint or needed to support the conclusions in your report or presentation. These files are part of the repository and should be committed when appropriate.

Use experiments/local/ only for disposable or machine-local intermediate files. Except for the README already in that directory, its contents are ignored by Git. Files placed there are therefore not backed up by GitHub and are not included in normal repository submissions. Do not place required code, benchmark instances, required results, or anything needed to reproduce your conclusions there.

Course-provided benchmark collections remain under benchmarks/ and are part of the repository.

Reproducibility

Your repository should contain the scripts and instructions needed to reproduce the important experiments reported in the final submission.

You do not need to commit enormous temporary files or every intermediate run. You do need to preserve enough information that another person can determine:

• which benchmark instances were used;
• which algorithm and parameters were run;
• which random seeds were used when relevant; and
• how the reported tables or figures were produced.

Benchmark Evaluation

Some benchmark evaluation may be run using instructor-provided infrastructure.

The benchmark is intended to provide a consistent collection of inputs and to encourage robust algorithm design. A leaderboard may be used, but leaderboard position is not the primary goal of the project.

A strong final analysis explains the behavior behind the numbers rather than merely reporting a score.

1.7 - Graph Interface

Several Beyond Brute Force problems use the same course-provided representation for a simple, undirected graph.

The class is defined in:

src/course/common/graph.py

Algorithms that use this representation may import it with:

from course.common.graph import Graph

The course-provided input routines construct the Graph object before calling your algorithm. In most cases, your code will therefore use a Graph rather than read or construct one itself.

This page defines the public interface that student code may rely on.

Graph Representation

A Graph contains vertices numbered consecutively from 0 through num_vertices - 1.

For example, if:

graph.num_vertices == 5

then the vertex set is:

The graph is simple and undirected:

• self-loops are not permitted;
• parallel edges are not permitted; and
• an edge $(u,v)$ is the same edge as $(v,u)$.

The supplied Graph object should be treated as read-only. Algorithms should maintain their own state rather than modifying the graph.

Public Attributes

graph.num_vertices

graph.num_vertices

is an integer containing the number of vertices in the graph.

For example:

for v in range(graph.num_vertices):
    ...

iterates over every vertex.

Accessing num_vertices takes constant time.

graph.edges

graph.edges

is a tuple containing all edges in the graph.

Each edge is represented as a two-element tuple of integers:

(u, v)

The stored representation uses u < v.

For example:

for u, v in graph.edges:
    ...

iterates over every edge.

Iterating over the complete collection takes $O(|E|)$ time.

Student code should not depend on the order in which edges appear.

Public Methods

graph.neighbors(vertex)

graph.neighbors(vertex)

returns a frozenset containing the vertices adjacent to vertex.

For example:

for u in graph.neighbors(v):
    ...

iterates over all neighbors of v.

The returned collection is read-only.

Retrieving the neighbor collection takes constant time. Iterating over all neighbors takes $O(\deg(v))$ time.

Membership testing such as:

u in graph.neighbors(v)

uses Python’s hash-based set representation and therefore takes expected constant time.

graph.degree(vertex)

graph.degree(vertex)

returns the degree of vertex.

For example:

if graph.degree(v) == 0:
    ...

tests whether v is isolated.

This operation takes constant time.

graph.has_edge(u, v)

graph.has_edge(u, v)

returns True if the graph contains the edge between vertices u and v, and False otherwise.

For example:

if graph.has_edge(2, 4):
    ...

Because the graph is undirected:

graph.has_edge(2, 4)

and

graph.has_edge(4, 2)

produce the same result.

Edge lookup uses the graph’s hash-based adjacency representation and therefore takes expected constant time.

len(graph)

Python’s built-in len() function may also be used:

len(graph)

It returns the number of vertices and is equivalent to:

graph.num_vertices

This operation takes constant time.

Constructing Graphs for Tests

The course input routines normally construct graph objects for you. However, you may also construct small graphs directly when writing your own tests.

Use:

Graph.from_edges(num_vertices, edges)

For example:

graph = Graph.from_edges(
    5,
    [
        (0, 1),
        (0, 2),
        (1, 2),
        (2, 3),
        (2, 4),
        (3, 4),
    ],
)

This constructs the same graph used in the Minimum Vertex Cover example.

from_edges() rejects:

• vertex numbers outside the valid range;
• self-loops; and
• duplicate edges.

The construction process takes $O(|V|+|E|)$ expected time.

Graph construction is support functionality and is not part of the running time of a solver once the parsed graph has been passed to solve().

Example

Suppose graph represents:

0 ----- 1
 \     /
   \ /
    2 ----- 3

The following expressions illustrate the public interface:

graph.num_vertices
# 4

len(graph)
# 4

graph.edges
# tuple containing the graph's edges

graph.neighbors(2)
# frozenset containing 0, 1, and 3

graph.degree(2)
# 3

graph.has_edge(0, 2)
# True

graph.has_edge(0, 3)
# False

The exact printed order of sets or edges should not be used as part of an algorithm.

Private Implementation Details

The Graph class may contain attributes whose names begin with an underscore, such as:

_adjacency

These are implementation details and are not part of the student-facing interface.

Do not access them directly.

For example, use:

graph.neighbors(v)

rather than:

graph._adjacency[v]

Only the attributes and methods documented on this page are guaranteed to remain available to student code.

1.8 - Input Files

Beyond Brute Force uses standard input formats shared by multiple project problems.

The course-provided support code reads these files and converts each input into the representation passed to your algorithm.

You need to understand the formats well enough to inspect supplied instances and create your own test cases, but you are not expected to write the low-level parsing code yourself.

Each invocation of src/solve.py processes one problem instance.

Instance Names

Unless an explicit identifier is supplied on the command line, an instance is identified by the name of its input file without the filename extension.

For example:

tests/example-01.txt

has the instance identifier:

example-01

The directory containing the file is not part of the identifier.

The identifier may be overridden using the --instance option described on the Program Interface page.

Unweighted Graph Files

Several project problems use simple, unweighted graphs.

The standard text representation begins with two integers:

n m

where:

• n is the number of vertices; and
• m is the number of edges.

Vertices are numbered consecutively beginning with 0:

The next m lines each contain two integers identifying the endpoints of one edge.

For example:

5 6
0 1
0 2
1 2
2 3
2 4
3 4

describes a graph with five vertices and six edges.

For an undirected graph, endpoint order is not significant. Thus:

0 2

and

2 0

describe the same edge.

Unless a problem specification explicitly states otherwise, graph instances are simple:

• self-loops are not permitted; and
• parallel edges are not permitted.

The supplied reader will report malformed input rather than silently changing the graph.

Text edge-list files use the .txt filename extension.

graph6 Files

Some experimental graph collections will be produced using Brendan McKay’s geng program.

geng represents graphs using the graph6 format.

Course-provided support code will decode graph6 instances into the same internal graph representation used for ordinary unweighted edge-list files. Your solving algorithms therefore do not need to know which representation was used to store the original graph.

You are not expected to implement graph6 encoding or decoding.

A .g6 input file passed to src/solve.py contains one graph6 instance.

When geng is used to generate many graphs, the provided experimental tools may separate its output into individual instances before invoking your solver.

Creating Your Own Test Instances

You are expected to create additional test cases while developing and evaluating your algorithms.

For an unweighted graph instance:

1. choose the number of vertices;
2. choose the edges;
3. place the correct values of n and m on the first line; and
4. place one edge on each subsequent line.

For example:

4 3
0 1
1 2
2 3

represents a path on four vertices.

Creating your own instances is useful for testing:

• very small graphs whose answers can be determined by hand;
• boundary cases;
• disconnected graphs;
• graphs containing isolated vertices; and
• graph structures that you expect to be especially easy or difficult for an algorithm.

Supplied and Gradescope Test Instances

Checkpoint instructions may include public test instances whose expected answers are known.

These files are provided so that you can test your implementation before submitting it.

Gradescope may also use additional test instances that are not included in the public collection. Hidden tests will follow the same documented input formats and assumptions as the public instances.

Your implementation should therefore solve the documented problem rather than depend on particular supplied test files.

Additional Input Formats

Some project problems require additional information that cannot be represented by an unweighted edge list. For example, Traveling Salesperson instances require edge weights.

Additional shared formats will be documented on this page as they are defined, rather than being independently redefined on each problem specification page.

1.9 - Longest Path

Given an undirected graph $G=(V,E)$, a simple path is a sequence of vertices

such that every consecutive pair of vertices is connected by an edge and no vertex appears more than once.

More formally,

for every $0 \le i < k$, and the vertices $v_0,v_1,\ldots,v_k$ are all distinct.

The length of a path is the number of edges it contains. Therefore, the path above has length $k$.

The goal of Longest Path is to find a simple path containing the largest possible number of edges.

Throughout this specification, Longest Path is abbreviated LP.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

LP instances use simple, unweighted, undirected graphs.

• Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$.
• Graphs are not necessarily connected.
• Isolated vertices may appear.
• A path may begin and end at any vertices in the graph.
• A vertex may appear at most once in a valid path.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below.

Example graph                                  example-01.txt

0 ------- 1 ------- 2 ------- 3                    5 5
           \       /                               0 1
            \     /                                1 2
              4                                    2 3
                                                   1 4
                                                   2 4

One valid path is

It uses four edges:

Because the graph contains five vertices, no simple path can contain more than four edges. Therefore, this path is a longest path.

For comparison,

is also a valid path, but it has length 3 and is therefore not optimal for this instance.

The sequence

is not a valid simple path because vertex 1 appears more than once.

LP Solution Format

LP uses longest_path as its project-wide problem identifier. The short command-line alias is lp.

The solution dictionary contains the vertices in the reported path and its length:

{
  "length": 4,
  "vertices": [0, 1, 4, 2, 3]
}

The vertices list gives the vertices in path order. Therefore, unlike a set of vertices, the order of this list is significant.

No vertex may appear more than once. Consecutive entries in the list must be connected by an edge in the graph.

For a nonempty path,

A path consisting of a single vertex is valid and has length 0.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem lp \
    --algorithm exhaustive

could produce a solution containing the path shown above.

Your program is required to report only one longest path. If an instance has multiple longest paths, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

A path and the same path written in reverse order represent the same undirected path. For example,

and

are equivalent solutions.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_valid_path(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/longest_path/verifier.py

This is the verifier for the decision version of Longest Path. It returns True exactly when vertices is a valid simple path in graph whose length is at least k.

For the example graph:

is_valid_path(graph, [0, 1, 4, 2, 3], 4)   # True
is_valid_path(graph, [0, 1, 4, 2, 3], 5)   # False
is_valid_path(graph, [0, 1, 4, 1, 2], 3)   # False: repeated vertex
is_valid_path(graph, [0, 4, 2], 2)         # False: (0,4) is not an edge

The verifier checks the supplied certificate. It does not determine whether that path is optimal and must not call one of the solving algorithms.

Gradescope may import and test is_valid_path() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Longest Path, a complete candidate is an ordered sequence of distinct vertices.

A natural exact baseline considers longer candidate sequences before shorter ones and sends each complete candidate to is_valid_path(). Once a valid candidate of a given length is found, that path is optimal because all longer candidate lengths have already been exhausted.

The Checkpoint 2 baseline should not use recursive path extension, fail-early rejection of partial candidates, branch-and-bound, or other pruning techniques. Those are precisely the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Upper Bound

Longest Path is a maximization problem, so the required polynomial-time bound is an upper bound on the optimal path length:

from course.common.graph import Graph


def upper_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/longest_path/bound.py

If the optimum is $OPT$, a valid result must satisfy

A bound may be loose, but it should provide useful information beyond blindly returning a very large number. The public tests include disconnected graphs so that you can test whether your bound takes basic graph structure into account.

Course Benchmark Suites

The supplied Longest Path benchmark manifest is located at:

benchmarks/longest_path/manifest.json

The required suites are run with the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three families with known optima:

• three-arm trees — sparse graphs with very limited valid path extensions;
• imbalanced complete bipartite graphs — connected graphs with many choices but no Hamiltonian path when the two parts differ by more than one; and
• two disconnected cliques — dense local structure combined with a global connectivity restriction.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Structural experiment

The required structural study holds the graph size fixed at 300 vertices and varies the probability of adding extra edges. Every instance contains a hidden, randomly labeled Hamiltonian path, so the optimum is always 299. This lets you study the effect of edge density without simultaneously changing graph size or the optimal objective value.

See:

benchmarks/longest_path/structure.md

for the full description.

1.10 - Maximum Clique

Given an undirected graph $G=(V,E)$, a clique is a subset of vertices $C \subseteq V$ in which every pair of distinct vertices is connected by an edge.

More formally, for every pair of distinct vertices $u,v \in C$,

The goal of Maximum Clique is to find a clique containing the largest possible number of vertices.

Throughout this specification, Maximum Clique is abbreviated MC.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

MC instances use simple, unweighted, undirected graphs.

• Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$.
• Graphs are not necessarily connected.
• Isolated vertices may appear.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below. Filled vertices are members of one maximum clique.

Example graph                                  example-01.txt

       ● 0 ------- ● 1                               5 6
           \       /                                 0 1
            \     /       ● = in the clique          0 2
              ● 2         ○ = not in the clique      1 2
            /     \                                  2 3
           /       \                                 2 4
       ○ 3 ------- ○ 4                               3 4

The filled vertices represent the clique

Every pair of vertices in $C$ is connected by an edge: $(0,1)$, $(0,2)$, and $(1,2)$ are all present.

This graph contains no clique of size 4, so $C$ is a maximum clique. The graph also contains another maximum clique, $\{2,3,4\}$.

For comparison, $\{0,1,3\}$ is not a clique because vertices 0 and 3 are not adjacent.

MC Solution Format

MC uses maximum_clique as its project-wide problem identifier. The short command-line alias is mc.

The solution dictionary contains the vertices in the reported clique and the size of that clique:

{
  "size": 3,
  "vertices": [0, 1, 2]
}

The vertices list represents a set. Its order is not significant. Duplicate vertices are not permitted, and size must equal the number of entries in the list.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem mc \
    --algorithm exhaustive

could produce a solution containing $[0,1,2]$.

Your program is required to report only one maximum clique. If an instance has multiple maximum cliques, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_clique(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/maximum_clique/verifier.py

This is the verifier for the decision version of Maximum Clique. It returns True exactly when vertices forms a clique in graph containing at least k vertices.

For the example graph:

is_clique(graph, [0, 1, 2], 3)   # True
is_clique(graph, [0, 1, 2], 4)   # False
is_clique(graph, [0, 1, 3], 3)   # False: (0,3) is not an edge

A valid certificate must contain only vertices from the graph, with no duplicates, and every pair of distinct supplied vertices must be adjacent.

The verifier checks the supplied certificate. It does not determine whether that clique is maximum and must not call one of the solving algorithms.

Gradescope may import and test is_clique() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Maximum Clique, a complete candidate is a subset of vertices.

A natural exact baseline considers candidate sizes from large to small, enumerates every subset of the current size, and sends each complete candidate to is_clique(). Once a valid candidate of size $k$ is found, it is optimal because every larger candidate size has already been exhausted.

The Checkpoint 2 baseline should not reject partial subsets, recursively grow only promising cliques, prune branches, or use branch-and-bound. Those are the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Improved Exact Search

A natural improved exact strategy builds a clique incrementally. If C is the clique currently being constructed and P is the set of vertices that may still be added, every vertex in P must be adjacent to every vertex already in C.

After choosing a vertex v from P, a recursive search can continue with:

C' = C ∪ {v}
P' = (P - {v}) ∩ neighbors(v)

This immediately discards vertices that cannot extend the current clique. A simple branch-and-bound rule can also stop whenever the current clique plus all remaining candidates cannot improve the best clique already found.

These are examples rather than required implementations; your improved solver must remain exact and you must justify why any work it avoids cannot eliminate an optimal solution.

Checkpoint 3 Upper Bound

Maximum Clique is a maximization problem, so the required polynomial-time bound is an upper bound on the optimal clique size:

from course.common.graph import Graph


def upper_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/maximum_clique/bound.py

If the optimum is $OPT$, a valid result must satisfy

There are several possible polynomial-time upper bounds. For example, $\Delta(G)+1$ is valid because a vertex in a clique of size $k$ has at least $k-1$ neighbors. A proper coloring also gives an upper bound because a clique can contain at most one vertex of each color.

You are not required to use either particular bound, but the returned value must be valid and computed in polynomial time.

Course Benchmark Suites

The supplied Maximum Clique benchmark manifest is located at:

benchmarks/maximum_clique/manifest.json

The required suites use the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three families with known optima:

• balanced complete bipartite graphs — the maximum clique has size 2, so a large fraction of larger subsets must be rejected by the exhaustive baseline;
• complete multipartite graphs with parts of size 3 — a maximum clique contains exactly one vertex from each part; and
• two disconnected equal cliques — dense local structure combined with a complete absence of edges between the two components.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Heuristic scale

The scale suite uses sparse graphs containing a planted clique together with many independent distractor vertices. Required instances extend to 5,000 vertices while retaining a known optimum by construction.

Structural experiment

The required structural study holds both graph size and optimum fixed:

• $n=300$;
• $OPT=10$.

Every instance is a complete 10-partite graph. The part-size distribution is changed to vary edge density while preserving the exact optimum. This lets you investigate whether density affects heuristic quality, runtime, variation across seeds, or the tightness of your upper bound without simultaneously changing problem size or the optimal clique size.

See:

benchmarks/maximum_clique/structure.md

for the full description.

1.11 - Minimum Graph Coloring

Given an undirected graph $G=(V,E)$, a proper vertex coloring assigns a color to every vertex such that no two adjacent vertices receive the same color.

More formally, if $c(v)$ denotes the color assigned to vertex $v$, then for every edge $(u,v) \in E$,

The goal of Minimum Graph Coloring is to find a proper coloring that uses the smallest possible number of colors. The minimum number of colors required to properly color a graph is called its chromatic number.

Throughout this specification, Minimum Graph Coloring is abbreviated MGC.

Your goal throughout the project will be to investigate algorithms involving graph colorings. The specific algorithmic tasks required at each stage are described in the corresponding checkpoint.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

MGC instances use simple, undirected graphs.

• Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$.
• Graphs are not necessarily connected.
• Isolated vertices may appear.
• Every vertex must be assigned exactly one color.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below.

The number in parentheses beside each vertex indicates its assigned color.

Example graph                                  example-01.txt

               1 (1)                               5 5
              /     \                               0 1
             /       \                              1 2
          0 (0)     2 (0)                           2 3
             \       /                              3 4
              \     /                               4 0
               4 (2) --- 3 (1)

This coloring uses three colors:

Every pair of adjacent vertices has a different color, so this is a valid coloring.

This graph is an odd cycle and cannot be properly colored using only two colors. Therefore, the coloring shown above is a minimum coloring and the chromatic number of the graph is 3.

For comparison, the assignment

is not a valid coloring because vertices 0 and 4 are adjacent and are both assigned color 0.

MGC Solution Format

MGC uses minimum_graph_coloring as its project-wide problem identifier.

The solution object contains the number of colors used and the color assigned to each vertex:

"solution": {
  "num_colors": 3,
  "colors": [0, 1, 0, 1, 2]
}

The entry colors[v] gives the color assigned to vertex $v$. Therefore, the colors list must contain exactly one entry for every vertex in the graph.

Color numbers begin with 0. If a solution uses $k$ colors, the colors must be numbered consecutively:

The actual numbers used as color labels have no special meaning. Only whether two vertices have the same or different colors matters.

num_colors must equal the number of distinct colors appearing in the colors list.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem minimum_graph_coloring \
    --algorithm exhaustive

could produce:

{
  "problem": "minimum_graph_coloring",
  "algorithm": "exhaustive",
  "instance": "example-01",
  "solution": {
    "num_colors": 3,
    "colors": [0, 1, 0, 1, 2]
  },
  "statistics": {}
}

Your program is required to report only one minimum coloring. If an instance has multiple minimum colorings, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Different assignments of color numbers may represent equivalent colorings. For example, replacing every color 0 with color 1 and every color 1 with color 0 does not create a fundamentally different coloring.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_valid_coloring(graph: Graph, colors: list[int], k: int) -> bool:
    ...

in:

src/student/problems/minimum_graph_coloring/verifier.py

This is the verifier for the decision version of Minimum Graph Coloring. It returns True exactly when colors is a proper coloring of graph that uses at most k distinct colors.

For the example graph:

is_valid_coloring(graph, [0, 1, 0, 1, 2], 3)   # True
is_valid_coloring(graph, [0, 1, 0, 1, 2], 2)   # False: uses 3 colors
is_valid_coloring(graph, [0, 1, 0, 1, 0], 3)   # False: edge (0,4) conflicts

A certificate must assign exactly one nonnegative integer color to every vertex. Adjacent vertices must receive different colors. The verifier does not need to require consecutive color labels; for example, [4,7,4,7,9] can be a valid certificate using three colors. Solver output, however, must normalize its labels to 0,1,...,k-1.

The verifier checks the supplied certificate and threshold. It does not determine whether the coloring is minimum and must not call a solving algorithm.

Gradescope may import and test is_valid_coloring() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Minimum Graph Coloring, try k = 1, 2, 3, .... For each k, enumerate complete assignments of all n vertices to the k available colors. Each completed assignment is then tested with is_valid_coloring().

Once the first feasible k is found, that coloring is optimal because every smaller number of colors has already been exhausted.

The Checkpoint 2 baseline should not reject a coloring while it is still only partially assigned, choose the next vertex adaptively, prune impossible partial assignments, or use branch-and-bound. Those are the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Improved Exact Search

A natural improved exact strategy assigns colors incrementally and rejects a partial coloring as soon as it creates a conflict. More sophisticated exact methods may choose the next vertex using degree or saturation information and may use bounds to avoid trying color counts that cannot succeed.

For example, a recursive search can maintain a partial color assignment and, for the next vertex, consider only colors not already used by its colored neighbors. This avoids generating many complete assignments that the Checkpoint 2 exhaustive baseline would generate and reject only at the end.

These are examples rather than required implementations. Your improved solver must remain exact and you must justify why any work it avoids cannot eliminate an optimal coloring.

Checkpoint 3 Lower Bound

Minimum Graph Coloring is a minimization problem, so the required polynomial-time bound is a lower bound on the chromatic number:

from course.common.graph import Graph


def lower_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/minimum_graph_coloring/bound.py

If the optimum chromatic number is $OPT$, a valid result must satisfy

One useful source of lower bounds is a clique that you can find in polynomial time: if you find a clique of size $r$, then at least $r$ colors are required. The bound routine does not need to find a maximum clique; that would itself be an NP-hard problem. A greedily constructed clique, a detected triangle, or another polynomial-time argument can provide a valid lower bound.

You are not required to use a particular technique, but the returned value must be valid and computed in polynomial time.

Course Benchmark Suites

The supplied Minimum Graph Coloring benchmark manifest is located at:

benchmarks/minimum_graph_coloring/manifest.json

The required suites use the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three graph families with known chromatic numbers by construction:

• odd cycles — sparse graphs with chromatic number 3;
• complete graphs — K_n requires exactly n colors; and
• planted four-color graphs — each graph contains a K_4 but all other edges are placed between four known color classes, proving that the chromatic number is exactly 4.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Heuristic quality and scale

The known-quality and scale suites use planted k-colorable graphs that also contain a K_k. Therefore their chromatic number is exactly k, even for the largest instances. The scale suite extends through 5,000 vertices.

Structural experiment

The required structural study holds both graph size and optimum fixed:

• $n=300$;
• $OPT=8$.

Each graph is built from eight planted color classes and contains an explicit K_8. Additional edges are added only between different color classes, so an 8-coloring always exists. The benchmark varies the probability of these additional cross-class edges, producing low-, medium-, and high-density graphs while keeping both n and the chromatic number fixed.

This lets you investigate whether edge density affects heuristic solution quality, runtime, variation across seeds, or the tightness of your lower bound without simultaneously changing graph size or the optimum.

See:

benchmarks/minimum_graph_coloring/structure.md

for the full description.

1.12 - Minimum Vertex Cover

Given a simple undirected graph $G=(V,E)$, a vertex cover is a set $C\subseteq V$ such that every edge has at least one endpoint in $C$:

The optimization problem asks for a vertex cover of minimum size. Throughout this project, Minimum Vertex Cover is abbreviated MVC and uses the problem identifier minimum_vertex_cover (short command-line alias mvc).

Before implementing your algorithms, review the project-wide Program Interface and Input Files pages.

Graph assumptions

MVC instances use the shared course Graph representation.

• Vertices are numbered $0,1,\ldots,n-1$.
• Graphs are simple and undirected.
• Graphs need not be connected.
• Isolated vertices may appear.

MVC solution format

A solver returns one vertex cover:

{
  "size": 3,
  "vertices": [0, 2, 3]
}

vertices represents a set, so its order is not significant and duplicates are not permitted. size must equal len(vertices). If several minimum covers exist, any one of them is acceptable.

For example:

python src/solve.py example-01.txt \
    --problem mvc \
    --algorithm exhaustive

runs the MVC exhaustive solver through the common course driver.

Solution verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_vertex_cover(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/minimum_vertex_cover/verifier.py

This is the verifier for the decision version of MVC. It returns True exactly when all of the following hold:

1. vertices contains only valid graph vertices and contains no duplicates;
2. every edge has at least one endpoint in vertices; and
3. the certificate contains at most k vertices.

The verifier checks the supplied certificate and threshold. It does not determine whether the cover is minimum and must not call a solving algorithm. Gradescope may import and test the verifier independently of src/solve.py.

A direct implementation can convert the list to a set once and then scan all edges, giving polynomial running time.

Checkpoint 2 exhaustive baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For MVC:

1. try candidate sizes $k=0,1,2,\ldots$ from small to large;
2. for each $k$, enumerate every vertex subset of size $k$; and
3. test each completed subset with is_vertex_cover().

Once the first valid cover is found, it is optimal because every smaller candidate size has already been exhausted.

The Checkpoint 2 baseline should not reject partial subsets, branch on uncovered edges, prune, memoize, use dynamic programming, or use branch-and-bound. Those techniques belong to the improved exact algorithm.

The exhaustive solver must also record:

statistics["candidates"]

Increment this counter exactly once for each complete vertex subset that is actually tested as a candidate cover. Partial states and loop iterations that do not produce a tested complete subset are not candidates.

Checkpoint 3 improved exact search

MVC has a useful structural observation. If an edge $\{u,v\}$ is currently uncovered, every vertex cover must contain at least one of its endpoints. Therefore an exact search may branch into two subproblems:

include u
or
include v

and continue on the remaining uncovered edges. This can avoid enormous portions of the complete-subset search performed by the Checkpoint 2 baseline.

Additional exact improvements may include better edge/vertex selection, reduction rules, an incumbent solution, lower-bound pruning, memoization, or other justified techniques. These are examples rather than a mandated implementation. Your solver must remain exact and you must explain why any pruned work cannot contain a better solution.

Checkpoint 3 lower bound

MVC is a minimization problem, so the required polynomial-time bound is a lower bound:

from course.common.graph import Graph


def lower_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/minimum_vertex_cover/bound.py

If the optimum is $OPT$, the returned value must always satisfy

One natural source of a lower bound is a maximal matching. The edges of a matching share no endpoints, and covering each matched edge requires selecting at least one distinct endpoint. Therefore the size of any matching is a valid lower bound on the minimum vertex-cover size. A greedily constructed maximal matching is polynomial-time and is sufficient as one possible design.

You are not required to use that particular bound. The returned value must be valid for every legal instance, polynomial-time computable, and sufficiently informative for the checkpoint tests.

Checkpoint 3 heuristic

heuristic1 must always return a valid cover and must run in polynomial time. It must also include a randomized component, perform multiple attempts or restarts, retain the best valid cover found so far, and reproduce the same result when run with the same --seed.

A single deterministic greedy construction followed immediately by return is not sufficient for heuristic1.

Course benchmark suites

The supplied MVC benchmark manifest is located at:

benchmarks/minimum_vertex_cover/manifest.json

Run the common experiment tool with, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three known-optimum families:

• balanced complete bipartite graphs;
• disjoint star forests; and
• disjoint triangles.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After one algorithm times out on a member of a frontier family, larger members of that same family are skipped for that algorithm. Gradescope uses shorter safety ceilings; the local frontier is where you study when each exact method becomes impractical.

Heuristic scale

The scale suite uses bipartite graphs with certified optima at 500, 2,000, and 5,000 vertices. In each graph, one side of the bipartition is a cover of size $k$, while a matching of size $k$ proves that no smaller cover exists.

Structural experiment

The required structural family holds both size and optimum fixed:

• $n=300$;
• $OPT=120$.

The amount of additional cross-edge structure is changed to produce sparse, medium, and dense instances. This lets you investigate the effect of edge density without simultaneously changing the number of vertices or the known optimal cover size.

See:

benchmarks/minimum_vertex_cover/structure.md

for the construction and interpretation details.

1.13 - Program Interface

All Beyond Brute Force implementations use the same command-line interface and output structure. This allows the same testing, Gradescope, and experimental tools to work with every project problem.

The repository separates project-maintained infrastructure from team implementation code:

src/course/     course-owned infrastructure
src/student/    student-owned implementations

The common entry point remains:

src/solve.py

You implement the algorithms under src/student/. You are not expected to recreate the command-line parser, problem dispatch, input readers, or JSON-output infrastructure under src/course/.

The complete ownership model and repository layout are described on the Repository page.

Source-Code Layout

For an MVC team, the source involved in executing an algorithm looks conceptually like this:

src/
├── solve.py                                  # COURSE
│
├── course/                                   # COURSE-OWNED
│   ├── driver.py
│   ├── common/
│   │   ├── graph.py
│   │   ├── graph_io.py
│   │   ├── graph6.py
│   │   ├── weighted_graph.py
│   │   └── weighted_graph_io.py
│   └── problems/
│       ├── __init__.py
│       └── minimum_vertex_cover.py
│
└── student/                                  # STUDENT-OWNED
    └── problems/
        └── minimum_vertex_cover/
            ├── __init__.py
            ├── verifier.py
            ├── bound.py
            ├── exhaustive.py
            ├── improved.py
            ├── heuristic1.py
            └── heuristic2.py

Course code reads and validates the input instance and then calls the requested student implementation. Files under src/student/ contain the algorithmic work your team owns.

Shared Graph Interface

The unweighted graph problems use the course-provided immutable graph type:

from course.common.graph import Graph

A Graph represents a simple undirected graph whose vertices are numbered from 0 through graph.num_vertices - 1. Student code should treat the graph as read-only. Algorithms may create their own lists, sets, dictionaries, and other working state, but they should not attempt to modify the input graph.

The shared interface is:

Iterate over every vertex with:

for v in range(graph.num_vertices):
    ...

The course-provided readers construct these objects. Student implementations should use this interface rather than maintaining a separate graph parser or reconstructing the graph representation.

Shared Weighted Graph Interface

Weighted problems such as Traveling Salesperson use:

from course.common.weighted_graph import WeightedGraph

A WeightedGraph is read-only and uses vertex IDs from 0 through graph.num_vertices - 1. TSP instances may be stored explicitly as edge lists or implicitly from coordinates or a course-provided weight generator. Student algorithms receive the same graph interface regardless of the file format.

The most important operations for TSP are:

For small explicitly stored weighted graphs, graph.edges is also available as a tuple of (u, v, weight) triples. Do not rely on graph.edges in TSP algorithms. Large coordinate-backed TSP instances may contain thousands or tens of thousands of cities, so explicitly storing all $\binom{n}{2}$ edges would use unnecessary quadratic space. Use graph.weight(u, v) or, when a complete edge scan is truly necessary, graph.iter_edges().

The TSP input layer accepts both the original course n m / u v weight format and supported TSPLIB-style coordinate files. For EUC_2D instances, edge weights are computed on demand using the TSPLIB integer-distance rule. Student algorithms should not parse TSPLIB files themselves.

Implementation Rules

Unless a checkpoint explicitly states otherwise:

• Submitted project code may use the Python standard library and course-provided support code.
• NetworkX may not be used anywhere in the submitted project code.
• Other third-party graph-processing libraries may not be used unless explicitly approved.
• You may not call a library routine that solves or approximates your assigned problem.
• You may not invoke an integer-programming, SAT, constraint-programming, or other general-purpose optimization solver to obtain a solution.
• The algorithms submitted for this project must perform the required algorithmic work themselves.

Course-owned infrastructure may perform routine tasks such as reading input files, processing command-line arguments, dispatching to the requested algorithm, and writing JSON results.

Running an Algorithm

The general invocation is:

python src/solve.py INPUT_FILE --problem PROBLEM --algorithm ALGORITHM

The command explicitly identifies the input instance, the computational problem, and the algorithm that should execute.

For example:

python src/solve.py example-01.txt \
    --problem minimum_vertex_cover \
    --algorithm exhaustive

requests the exhaustive Minimum Vertex Cover algorithm on example-01.txt.

Both --problem and --algorithm are required.

Problem Identifiers

The value supplied to --problem selects the problem adapter and corresponding student implementation directory.

Problem identifiers are standardized across:

• project.json;
• the command-line interface;
• Gradescope;
• experimental tools; and
• JSON result files.

The authoritative list is stored in:

tools/valid_projects.json

For example:

minimum_vertex_cover

uses the course adapter:

src/course/problems/minimum_vertex_cover.py

and student implementations under:

src/student/problems/minimum_vertex_cover/

The requested problem must agree with the team’s assigned_problem value in project.json.

Algorithm Identifiers

The value supplied to --algorithm selects the student solver implementation.

The following identifiers are reserved:

exhaustive    straightforward exhaustive exact algorithm
improved      improved exact algorithm
heuristic1    first heuristic algorithm
heuristic2    second heuristic algorithm, when required

For an MVC team:

--problem minimum_vertex_cover --algorithm exhaustive

selects:

src/student/problems/minimum_vertex_cover/exhaustive.py

while:

--problem minimum_vertex_cover --algorithm heuristic1

selects:

src/student/problems/minimum_vertex_cover/heuristic1.py

Gradescope requests only algorithms required for the corresponding checkpoint and team.

Dispatching to an Algorithm

The course-owned driver uses the problem identifier to load a course adapter. The adapter reads the instance and locates the requested student solver.

Conceptually:

problem = get_problem(args.problem)

instance = problem.read_instance(
    args.input_file,
    args,
)

solver = problem.get_solver(
    args.algorithm,
)

solution, statistics = solver(
    instance,
    args,
)

For MVC, the path is conceptually:

--problem minimum_vertex_cover
        ↓
src/course/problems/minimum_vertex_cover.py
        ↓
parsed Graph instance
        ↓
--algorithm exhaustive
        ↓
src/student/problems/minimum_vertex_cover/exhaustive.py
        ↓
solve(instance, args)

Every solving algorithm implements:

def solve(instance, args):
    ...

The instance argument contains the parsed problem instance.

The args argument contains the complete parsed command-line arguments.

Algorithms should use the supplied args object rather than parsing sys.argv themselves.

Solver Return Values

A solver returns:

solution, statistics

Both values are Python dictionaries.

For example, an MVC exhaustive solver might eventually return:

solution = {
    "size": 3,
    "vertices": [0, 2, 3],
}

statistics = {
    "candidates": 17,
}

The required contents of solution are defined by the corresponding problem specification.

The required contents of statistics are defined by the corresponding checkpoint.

Common Optional Arguments

Instance Identifier

By default, the instance identifier is derived from the input filename as described on the Input Files page.

It may be overridden using:

--instance ID

For example:

python src/solve.py graph.txt \
    --problem minimum_vertex_cover \
    --algorithm exhaustive \
    --instance mvc-n12-m28-0047

Random Seed

Algorithms that use randomness must support:

--seed INTEGER

For example:

python src/solve.py graph.txt \
    --problem minimum_vertex_cover \
    --algorithm heuristic1 \
    --seed 412

The value is available to the solver as:

args.seed

Using the same input, algorithm, and seed should make a randomized experiment reproducible.

Deterministic algorithms may ignore this value.

Output File

By default, the result is written to standard output.

The optional argument:

--output FILE

also writes the result to the specified file.

For example:

python src/solve.py example-01.txt \
    --problem minimum_vertex_cover \
    --algorithm exhaustive \
    --output result.json

Additional Optional Arguments

The supplied driver provides a documented mechanism for algorithms to register additional optional command-line arguments when useful for experimentation.

Such arguments must remain optional. The standard invocations described on this page must continue to work without them.

Passing the complete args object to solve() allows these additional values to reach an algorithm without changing the solver function signature.

Program Output

A successful execution writes exactly one JSON result to standard output (stdout).

Diagnostic messages, debugging information, warnings, and error messages must not be written to stdout, because doing so would corrupt the JSON result.

Diagnostic information should instead be written to standard error (stderr).

For example:

print("Beginning exhaustive search...", file=sys.stderr)

is acceptable, while:

print("Beginning exhaustive search...")

is not.

The common JSON structure is:

{
  "problem": "minimum_vertex_cover",
  "algorithm": "exhaustive",
  "instance": "example-01",
  "solution": {},
  "statistics": {}
}

The fields have the following meanings:

• problem identifies the requested problem;
• algorithm identifies the requested algorithm;
• instance identifies the input instance;
• solution contains the solution returned by the solver; and
• statistics contains measurements returned by the solver.

The contents of solution are problem-specific.

The contents of statistics may change as the project progresses. Until a checkpoint requires specific statistics, the solver may return an empty dictionary.

If --output FILE is specified, the JSON written to that file must be identical to the JSON written to stdout.

Solution Verifiers

Verification is not another command-line mode of src/solve.py.

Each student problem directory contains the verifier required by that problem. Gradescope and course tools may import this verifier directly.

For example, the MVC verifier belongs at:

src/student/problems/minimum_vertex_cover/verifier.py

and uses the course graph type:

from course.common.graph import Graph

def is_vertex_cover(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

The candidate cover is passed as a list[int]. If fast membership tests are useful, converting it once with cover = set(vertices) takes $O(|vertices|)$ expected time. Scanning every edge and testing its endpoints then takes $O(|E|)$ expected time.

A verifier checks whether a proposed solution satisfies the constraints of the problem. It must not obtain its answer by calling one of the solving algorithms.

The corresponding problem specification remains authoritative for the exact solution representation and verifier contract for each project problem.

Polynomial-Time Bounds

The bound is not another command-line mode of src/solve.py. It is a student-implemented, problem-specific function that course tools, Gradescope, experimental tools, and an improved exact algorithm may import directly.

For Minimum Vertex Cover, the implementation belongs at:

src/student/problems/minimum_vertex_cover/bound.py

and has the required signature:

from course.common.graph import Graph

def lower_bound(graph: Graph) -> int:
    ...

For every legal MVC instance, the returned value must satisfy:

$$ \operatorname{lower_bound}(G) \leq OPT(G). $$

The bound must run in polynomial time. The function signature is included in the starter repository during Checkpoint 2 so that teams can design the bound and discuss it during the algorithm-design meeting. Checkpoint 2 public tests do not call the bound. The implementation is required and tested beginning in Checkpoint 3.

The course adapter exposes the student’s bound to shared infrastructure and records whether the problem uses a lower or upper bound. Students implement bound.py; they do not modify the course adapter.

A team may also reuse its bound inside improved.py. For example, a branch-and-bound implementation may apply the same valid bound to a residual subproblem to determine that a branch cannot improve the best solution already known. Using the bound inside the improved exact solver is encouraged when it fits the algorithm, but the bound remains an independently testable function.

Each problem specification defines whether its required bound is an upper or lower bound and gives the exact function contract.

Course Infrastructure and Student Templates

The template repository contains course-owned infrastructure such as:

src/solve.py
src/course/driver.py
src/course/common/
src/course/problems/

and student-owned implementation templates under:

src/student/problems/

Course updates may replace files under src/course/ and other documented course-owned locations. They will not overwrite files under src/student/.

The starter code distributed in the repository is the authoritative interface used by Gradescope.

Error Behavior

If the program cannot process a requested execution because of an invalid argument, malformed input, inconsistent problem identifier, or another unrecoverable error, the supplied driver should:

1. write a useful error message to stderr;
2. exit with a nonzero exit status; and
3. avoid writing partial or invalid JSON to stdout.

Much of this behavior is implemented by the course-owned driver so that your work can focus on the algorithms themselves.

1.14 - Project Options

Project Options

MAX 3-SAT

Solve Problem using Independent Set Approximation

For this option, you must develop code that transforms the 3-SAT input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.

You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.

Enumerate Clauses and Showcase Results (in development)

For all values of $$3 \ge n \ge 5$$, enumerate all possible input clauses and then show the ratio of unsatisfiable sets versus satisfiable sets.

Max Clique

TSP

Advanced Approximation Strategies

Augment the approximation strategy to:

• Many approximations reach a local min and can’t improve from there. Augment the approximation code to detect this local min and restart the approximation. Track each approximation and show the variance encountered by your program as well as the quality of the best solution as a function of time. Plot these results and discuss.

Longest Path

Test Cases

Generate at least 1000 interesting test cases and perform a comprehensive comparison of how the optimal solution/code differs from the approximation codes results.

Min Vertex Cover

Perform a reduction to Independent Set

For this option, you must develop code that transforms the Min Vertex Cover input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.

You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.

1.15 - Project Repository and Infrastructure

Each team uses one shared GitHub repository for the Beyond Brute Force project. The repository is created through Classroom 50 and is used throughout all checkpoints and the final submission.

The repository has an explicit ownership boundary. Course-owned files provide common infrastructure and may be updated during the semester. Student-owned files contain your team’s algorithm implementations and will not be overwritten by a course infrastructure update.

Do not rename required files or directories unless the project instructions explicitly tell you to do so. Gradescope and the supplied project tools depend on this structure.

Creating Your Repository

Use the Classroom 50 assignment below to create your team’s Beyond Brute Force repository:

Start the Beyond Brute Force repository: Classroom 50 assignment

After the repository has been created, open it on GitHub, copy the clone URL, and clone it in the usual way:

git clone YOUR_REPOSITORY_URL
cd YOUR_REPOSITORY_DIRECTORY

The repository is the working copy for the entire project. It contains the course infrastructure, student implementation files, public test instances, local validation tools, benchmark collections, and the standard directories for experiments, reports, and presentation materials.

Public tests are included directly in the repository under:

tests/public/

and local checkpoint test runners are provided under:

tools/

Gradescope uses additional hidden tests, but students do not need to download a separate hidden or public test bundle.

Course-Owned and Student-Owned Files

The most important ownership rule is visible directly in the source tree:

src/course/     COURSE-OWNED
src/student/    STUDENT-OWNED

Course-owned source

Everything under:

src/course/

is maintained as part of the project. These files implement common data structures, input handling, problem dispatch, command-line support, and other infrastructure. Do not modify files under src/course/ unless the project instructions explicitly tell you to do so.

If a correction or infrastructure update is needed during the semester, the course may replace files under src/course/. Such an update will not overwrite files under src/student/.

The launcher:

src/solve.py

is also course-owned.

Student-owned source

Everything under:

src/student/

belongs to your team. This is where you implement the verifier, exhaustive solver, improved exact solver, heuristic algorithms, and bound required by the checkpoints.

Course infrastructure updates will not replace or overwrite files under src/student/.

Other repository locations

The ownership of other important paths is:

Repository Layout

The following tree shows the important parts of the repository. All five student problem directories are included in the template; the Minimum Vertex Cover directory is expanded here as an example.

beyondbruteforce/
├── README.md
├── project.json
│
├── examples/
│   ├── project_2_person.json
│   └── project_3_person.json
│
├── src/
│   ├── solve.py                              # COURSE
│   │
│   ├── course/                              # COURSE-OWNED
│   │   ├── __init__.py
│   │   ├── driver.py
│   │   │
│   │   ├── common/
│   │   │   ├── __init__.py
│   │   │   ├── graph.py
│   │   │   ├── graph_io.py
│   │   │   ├── graph6.py
│   │   │   ├── weighted_graph.py
│   │   │   └── weighted_graph_io.py
│   │   │
│   │   └── problems/
│   │       ├── __init__.py
│   │       ├── minimum_vertex_cover.py
│   │       ├── traveling_salesperson.py
│   │       ├── minimum_graph_coloring.py
│   │       ├── longest_path.py
│   │       └── maximum_clique.py
│   │
│   └── student/                             # STUDENT-OWNED
│       ├── __init__.py
│       └── problems/
│           ├── __init__.py
│           ├── traveling_salesperson/
│           ├── minimum_graph_coloring/
│           ├── longest_path/
│           ├── maximum_clique/
│           └── minimum_vertex_cover/
│               ├── __init__.py
│               ├── verifier.py
│               ├── bound.py
│               ├── exhaustive.py
│               ├── improved.py
│               ├── heuristic1.py
│               └── heuristic2.py
│
├── tests/
│   ├── public/                              # COURSE
│   └── student/                             # STUDENT
│
├── benchmarks/                              # COURSE core benchmark suites
├── experiments/                             # STUDENT
│   ├── scripts/                             # tracked
│   ├── results/                             # tracked when needed
│   └── local/                               # NOT tracked (except README)
├── reports/                                 # STUDENT
├── presentation/                            # STUDENT
│
└── tools/                                   # COURSE infrastructure

The exact set of course-owned support files may grow as later checkpoints introduce additional infrastructure. Required paths and public interfaces remain documented on the project website.

Python Packages and Imports

Student algorithms use data structures from the course package. For example, an unweighted graph algorithm imports:

from course.common.graph import Graph

and a weighted graph algorithm imports:

from course.common.weighted_graph import WeightedGraph

Student implementations live in packages such as:

src/student/problems/minimum_vertex_cover/
src/student/problems/traveling_salesperson/

Course infrastructure is responsible for selecting the assigned problem, reading the input, and locating the appropriate student solver. Student algorithm files should not implement their own command-line parser or input-file parser.

Common Driver

The command-line entry point remains:

src/solve.py

This small course-owned launcher invokes the shared driver under src/course/. The course infrastructure is responsible for:

• processing command-line arguments;
• selecting the requested problem;
• selecting the requested student algorithm;
• reading the input instance;
• constructing the common JSON result;
• writing output; and
• handling common errors.

Students should not reproduce this infrastructure in their algorithm files.

The command-line interface is defined on the Program Interface page.

Problem Implementations

Each problem has two complementary pieces.

The course-owned adapter handles routine infrastructure. For Minimum Vertex Cover, that adapter is:

src/course/problems/minimum_vertex_cover.py

The student-owned implementation directory contains the algorithmic work being assessed:

src/student/problems/minimum_vertex_cover/

For MVC, students implement:

src/student/problems/minimum_vertex_cover/verifier.py
src/student/problems/minimum_vertex_cover/exhaustive.py
src/student/problems/minimum_vertex_cover/improved.py
src/student/problems/minimum_vertex_cover/heuristic1.py
src/student/problems/minimum_vertex_cover/bound.py

Three-person teams also implement:

src/student/problems/minimum_vertex_cover/heuristic2.py

The same pattern is used for the other four project problems. The specification page for each problem defines the exact verifier, solution representation, and bound interface.

Tests

Course-provided test instances are stored under:

tests/public/

For an MVC team, for example:

tests/public/minimum_vertex_cover/

contains public instances that can be used while developing and validating the algorithms.

Your team should place additional tests that you create under:

tests/student/

Gradescope may use additional test instances that are not included in the repository. Hidden tests follow the same documented input formats and problem assumptions as the public tests.

Local checkpoint checks

Run checkpoint-specific public tests from the root of the repository. For example:

python tools/run_cp2_tests.py
python tools/run_cp3_tests.py

The local test runners show detailed diagnostics by default when student code raises an exception. When possible, the output identifies the student-owned file, line number, function, and source line that caused the exception. This is intended to make the local checker useful as a development and debugging tool.

If you want only compact PASS/FAIL messages, add --quiet:

python tools/run_cp2_tests.py --quiet

For Checkpoint 2, the public runner first tests the student verifier directly. Once those tests pass, public solver tests reuse that verifier to check the certificate returned by the solver while also checking the expected objective value and required result structure. If verifier tests fail, dependent solver tests are skipped. The private Gradescope grader validates solver results independently and does not trust the student verifier.

Input formats are documented on the Input Files page.

Project Information

The root-level:

project.json

contains team information, project preferences, and the assigned problem. The source-tree ownership change does not change the project.json schema.

The valid project identifiers are stored in:

tools/valid_projects.json

The same problem identifier is used by project.json, the command-line interface, Gradescope, experimental tools, and JSON result files.

After project assignment, the value of assigned_problem must agree with the problem identifier supplied to src/solve.py.

Experiments and Reports

Use the experiment directory according to this layout:

experiments/
├── scripts/     experiment or analysis scripts that should be committed
├── results/     results that should be preserved with the project
└── local/       machine-local files that are intentionally not committed

Files under experiments/scripts/ and experiments/results/ are normal repository files. Commit scripts and results that are required by a checkpoint or needed to reproduce the important conclusions of the project.

experiments/local/ is different. Except for its README, that directory is excluded by the repository’s .gitignore. Files placed there are not backed up by GitHub and are not included in normal repository submissions. Use it only for disposable or machine-local intermediate files. Do not place required source code, benchmark instances, final experimental results, checkpoint artifacts, or anything needed to reproduce your conclusions there.

Course-provided benchmark collections remain under benchmarks/; they should not be copied into experiments/local/.

Use:

reports/

for checkpoint reports and final written materials required by the assignment.

Use:

presentation/

for final presentation materials.

Your repository should contain enough information and supporting material for another person to reproduce the important experimental results described in your final submission.

Git and Submission Workflow

This is a shared team repository. Every team member must be able to clone, edit, commit, and push.

Commit work regularly rather than waiting until a checkpoint deadline.

At each checkpoint that uses Gradescope, submit the current GitHub repository to the corresponding Gradescope assessment and include all team members in the Gradescope group.

The Gradescope autograder may check repository structure, required interfaces, basic correctness, and other mechanical requirements appropriate to that checkpoint.

Instructor-reviewed portions of the checkpoint are described on the Checkpoints and Final Submission page.

Responsibility for Submitted Work

Regardless of which tools or resources contributed to the project, your team is responsible for the contents of the repository.

Team members should be prepared to explain submitted code, verify that it is correct, modify it when necessary, and defend conclusions based on its output.

1.16 - Traveling Salesperson Problem

Given a weighted graph $G=(V,E)$, a tour is a cycle that visits every vertex exactly once before returning to its starting vertex.

If a tour visits the vertices in the order

then its total cost is the sum of the weights of the edges used by the tour:

The goal of the Traveling Salesperson Problem is to find a tour with the smallest possible total cost.

Throughout this specification, Traveling Salesperson Problem is abbreviated TSP.

Your goal throughout the project will be to investigate algorithms involving TSP tours. The specific algorithmic tasks required at each stage are described in the corresponding checkpoint.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

TSP instances use weighted, undirected, complete graphs.

• Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$.
• Every pair of distinct vertices is connected by exactly one edge.
• Edge weights are nonnegative integers.
• Because the graph is undirected, $w(u,v)=w(v,u)$.
• A valid tour visits every vertex exactly once and then returns to its starting vertex.

The weighted graph format and supplied input routines are described on the Input Files page.

Example

Consider the following complete weighted graph instance:

example-01.txt

4 6
0 1 10
0 2 15
0 3 20
1 2 35
1 3 25
2 3 30

The first line indicates that the graph contains four vertices and six edges. Each remaining line gives two endpoints followed by the weight of that edge.

One tour is

Its total cost is

For this instance, the three distinct tours beginning at vertex 0, ignoring reversal, have costs:

Therefore, the tour $[0,1,3,2,0]$ is a minimum-cost tour.

For comparison,

is not a valid TSP tour because vertex 3 is never visited.

TSP Solution Format

TSP uses traveling_salesperson as its project-wide problem identifier.

The solution object contains the reported tour and its total cost:

"solution": {
  "cost": 80,
  "tour": [0, 1, 3, 2, 0]
}

The order of vertices in tour is significant.

For a graph containing $n$ vertices, the tour list must contain exactly $n+1$ entries. The first and last entries must be the same, and every graph vertex must appear exactly once among the first $n$ entries.

cost must equal the sum of the weights of the $n$ edges traversed by the tour.

The starting vertex is not significant. For example,

and

represent the same cycle. Because the graph is undirected, traversing the cycle in the opposite direction also represents the same tour.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem tsp \
    --algorithm exhaustive

could produce:

{
  "problem": "traveling_salesperson",
  "algorithm": "exhaustive",
  "instance": "example-01",
  "solution": {
    "cost": 80,
    "tour": [0, 1, 3, 2, 0]
  },
  "statistics": {}
}

Your program is required to report only one minimum-cost tour. If an instance has multiple minimum-cost tours, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Decision-Problem Verifier

The verifier you implement corresponds directly to the polynomial-time certificate verifier for the decision version of TSP:

Given a weighted graph $G$ and a threshold $k$, does $G$ contain a tour whose total cost is at most $k$?

The proposed tour is the certificate. Your implementation must provide:

from course.common.weighted_graph import WeightedGraph

def is_valid_tour(graph: WeightedGraph, tour: list[int], k: int) -> bool:
    ...

in:

src/student/problems/traveling_salesperson/verifier.py

Two WeightedGraph interface details are especially useful when implementing this verifier:

n = graph.num_vertices       # integer attribute -- no parentheses
w = graph.weight(u, v)       # weight of edge (u, v)

Thus, for example, iterate over the vertices with range(graph.num_vertices) rather than calling graph.num_vertices(). The complete shared weighted-graph interface is documented on the Program Interface page.

The verifier must return True exactly when:

1. tour is a valid TSP tour of graph; and
2. the total cost of that tour is at most k.

The verifier must compute the tour cost from graph and tour; it must not trust a separately reported solution cost.

For the example graph, [0, 1, 3, 2, 0] has cost 80. Therefore:

is_valid_tour(graph, [0, 1, 3, 2, 0], 80)  # True
is_valid_tour(graph, [0, 1, 3, 2, 0], 79)  # False

A malformed tour must still be rejected regardless of the threshold:

is_valid_tour(graph, [0, 1, 2, 0], 1000)    # False: vertex 3 is missing

The verifier does not determine whether the tour is minimum-cost. It checks whether the supplied certificate proves a YES answer for the particular decision threshold k, and it must run in polynomial time without calling one of the solving algorithms.

Gradescope may import is_valid_tour() directly and test both tour feasibility and the threshold condition independently of src/solve.py.

Checkpoint 3 Bound Function

TSP is a minimization problem, so the required bound is a lower bound on the minimum tour cost. Implement:

from course.common.weighted_graph import WeightedGraph

def lower_bound(graph: WeightedGraph) -> int | float:
    ...

in:

src/student/problems/traveling_salesperson/bound.py

The function must run in polynomial time and never return a value larger than the true optimal tour cost. An MST-based lower bound is one natural design to consider during Checkpoint 2. Teams may propose a different valid polynomial-time bound during the algorithm-design meeting.

The same bound may be reused inside an improved exact branch-and-bound solver, but the experiment framework also calls it independently so that it can be used to evaluate heuristic solutions when OPT is unavailable.

Course Benchmark Suites

The project template contains TSP benchmark suites under:

benchmarks/traveling_salesperson/

The required suites are designed around different experimental questions:

• readiness checks the Checkpoint 3 interfaces on small instances;
• exact_frontier compares exhaustive and improved exact search over increasing sizes and three different edge-weight structures;
• quality_known evaluates early heuristic and bound quality where OPT is known;
• heuristic_scale checks heuristic behavior on coordinate-backed instances far beyond the practical exact-search range; and
• structure holds n fixed while comparing uniform Euclidean, clustered Euclidean, and non-geometric random-weight instances.

For randomized heuristics, the course runner uses several fixed seeds and preserves every run. This allows Checkpoint 4 to examine variation in both solution value and running time instead of drawing conclusions from one lucky or unlucky run.

Large coordinate-backed instances

Large Euclidean TSP benchmarks are stored as coordinates rather than as an explicit list of all $\binom{n}{2}$ weighted edges. Student code still receives the normal course WeightedGraph and calls:

graph.weight(u, v)

to obtain the integer edge weight. Students do not parse TSPLIB files or compute TSPLIB rounding themselves.

Optional leaderboard and reach instances

The benchmark manifest also defines optional public TSP challenges from the University of Waterloo National TSP Collection.

• leaderboard_known contains increasingly large instances whose optimal tour values have been proven. These can be scored by percentage gap from OPT.
• reach_known contains still larger proven-optimal instances.
• reach_open contains very large open instances. These have a published best-known tour and a published certified lower bound, but no known OPT.

Install the optional Waterloo files with:

python tools/install_external_benchmarks.py waterloo-tsp

For an open instance, report a gap to the published best-known tour, not a gap to OPT. The course-generated result data records the published lower bound separately so that the status of the instance remains clear.

For the known-OPT leaderboard, each instance is run under the same fixed course seeds. The recommended scoreboard score is the median percentage gap to OPT for each instance, averaged equally across the leaderboard instances. Lower is better. This reduces the influence of one unusually lucky randomized run. The best tour found and runtime summaries are reported separately.

See the Benchmark Suites page and benchmarks/traveling_salesperson/README.md in the repository for the complete suite definitions.