Build & Test

1 - Quick Reference

This page is the command and workflow reference you are most likely to revisit while developing and evaluating your project. Run all commands from the repository root unless noted otherwise.

Project selection and repository creation

Project Selection (before Checkpoint 1): Follow Getting Started to form your team (or work individually with approval), read the problem definitions, rank three preferences, and submit project.json on Gradescope. There is no repository to create in this stage.

Beginning of Checkpoint 1 (after assignments): Follow Checkpoint 1: Foundation to create or join the team repository through Classroom 50, clone it, transfer project.json, and fill in assigned_problem.

One-time setup after your problem is assigned

Once your team has received its assigned problem, confirm that project.json contains the correct assigned_problem.

Then run:

python tools/setup_project.py

This validates project.json and installs any external benchmark data configured for your assigned problem. It is safe to run the command again later; already-installed benchmark data is reused unless you explicitly force a reinstall.

To verify that course-owned infrastructure has not been accidentally changed:

python tools/check_course_files.py

Run one algorithm on one instance

The common solver interface is:

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

Problem identifiers may be written using the short forms:

mvc   tsp   mgc   lp   mc

Algorithms are:

exhaustive   improved   heuristic1   heuristic2

For example:

python src/solve.py tests/public/minimum_vertex_cover/instances/cycle5.txt \
    --problem mvc \
    --algorithm heuristic1 \
    --seed 17

--seed is available for randomized algorithms. Use the same seed when you want a run to be reproducible.

Run the provided public tests against your code

Checkpoint 1 / Foundation

Run the public Foundation tests for your assigned problem:

python tools/run_cp1_tests.py

Useful options include:

python tools/run_cp1_tests.py --algorithm exhaustive
python tools/run_cp1_tests.py --test star
python tools/run_cp1_tests.py --jobs 4

--test TEXT runs only public tests whose names contain TEXT.

Checkpoint 2 / Improved Algorithms

Run the public tests for the improved exact algorithm, polynomial-time bound, and first heuristic:

python tools/run_cp2_tests.py

To run independent public test cases concurrently:

python tools/run_cp2_tests.py --jobs 4

Are the test runners parallel?

By default, no: --jobs defaults to 1.

When you supply --jobs N, independent solver/bound test cases are run concurrently. Each test executes student code in a separate worker process. Interface/verifier setup and the major Checkpoint 2 test groups are still coordinated sequentially.

Run the benchmark/experiment program

First see which suites exist for your assigned problem:

python tools/run_experiments.py --list-suites

Then run one suite, for example:

python tools/run_experiments.py --suite readiness
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
python tools/run_experiments.py --suite challenge_open

You can run every suite in the manifest with:

python tools/run_experiments.py --all

Be careful: --all can include intentionally expensive experiments.

Results are written under experiments/results/, with one stable JSON/CSV pair per suite. For example, --suite exact_frontier writes:

experiments/results/exact_frontier.json
experiments/results/exact_frontier.csv

Timestamped copies are retained in the same directory. Running another suite does not overwrite the results from earlier suites.

Are benchmark runs parallel?

No. The benchmark runner executes one solver/bound worker at a time. Each individual run is isolated in a child process, but the suite itself is sequential. This makes timing comparisons easier to interpret and avoids multiple benchmark jobs competing for the same CPU at once.

Where do benchmark defaults come from?

For each problem, the course benchmark manifest is:

benchmarks/<problem>/manifest.json

The manifest controls course experiment settings such as:

• which instances belong to each suite;
• which algorithms run on each instance;
• timeouts;
• fixed random seeds;
• repeats;
• known optimum / best-known / published-bound metadata; and
• structural metadata used in the final analysis.

You normally read but do not edit the course manifest.

You can override benchmark timeouts for a local exploratory run:

python tools/run_experiments.py --suite exact_frontier --timeout 30
python tools/run_experiments.py --suite exact_frontier --timeout-scale 0.5

The benchmark timeout is an external safety limit enforced by the runner. It is not an internal heuristic stopping rule.

Where do heuristic/anytime parameters go?

There is currently no project-wide --attempts, --iterations, or --anytime command-line option passed through the benchmark runner.

Algorithm-specific choices such as number of randomized restarts, local-search iterations, or an internal anytime budget belong in your student heuristic implementation, for example:

src/student/problems/<problem>/heuristic1.py
src/student/problems/<problem>/heuristic2.py

If your heuristic uses a tunable budget, make that choice explicit in your code and report it in the returned statistics dictionary so that your experiments are reproducible. The course runner supplies the fixed random seed; your algorithm decides how to use its computation budget.

Do not confuse an internal heuristic budget with the manifest timeout: the timeout terminates a run that takes too long; it is not intended to be the algorithm’s search strategy.

Can I run only some benchmarks?

The standard runner selects benchmarks by suite:

python tools/run_experiments.py --suite quality_known

There is not currently a command-line option that selects arbitrary individual instance IDs within a suite.

For a single benchmark instance, run the solver directly with src/solve.py.

For an instructor-designed or exploratory subset, the runner can use an alternate manifest:

python tools/run_experiments.py --manifest path/to/my_manifest.json --suite my_suite

This is mainly useful for custom experiments; the required project experiments should use the course-provided manifest.

9. A useful workflow while developing

A typical cycle is:

edit algorithm
    ↓
run one small instance with src/solve.py
    ↓
run the relevant public test suite
    ↓
run a small benchmark suite such as readiness or quality_known
    ↓
inspect the corresponding files under experiments/results/
    ↓
make one algorithmic change and repeat

For the final experimental analysis, use the course-provided fixed seeds and benchmark suites so comparisons remain reproducible.

2 - Repository & Gradescope

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.

Repository Setup Happens in Checkpoint 1

Your team creates the shared repository after project assignments are released, at the beginning of Checkpoint 1: Foundation. That page provides the Classroom 50 invitation link, clone instructions, and steps for transferring project.json from Gradescope and setting assigned_problem.

Once the repository is created, it is the working copy for the entire project. The template includes course infrastructure, student implementation files, public tests, validation tools, benchmark collections, and standard directories for reports and presentations.

Course-provided public tests are under tests/public/; local checkpoint test runners are under tools/. Gradescope uses additional hidden tests. There is no separate student test-suite download.

For setup commands after your assigned problem is recorded, see Quick Reference.

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             # Same file submitted during Project Selection
│
├── 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_cp1_tests.py
python tools/run_cp2_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 the team name, student names (one to three), project preferences, and the assigned problem. GitHub usernames are not needed in project.json.

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/; downloaded external benchmark files live under benchmarks/<problem>/external/ and are also not part of normal Git submissions. Neither belongs in 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 Project Stages 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.

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

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 1 so that teams can design the bound and discuss it during the Early Project Review. Checkpoint 1 public tests do not call the bound. The implementation is required and tested beginning in Checkpoint 2.

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.

4 - Testing & Autograders

The project uses three complementary kinds of checking.

Local public tests

Run the supplied public test programs while developing. They are designed to catch interface, correctness, verifier, bound, and basic scalability problems before submission.

The exact commands and useful options are collected in Quick Reference.

Gradescope

Gradescope uses additional tests that follow the same documented interfaces and input formats. The hidden tests are intended to verify correctness independently rather than reward solutions that are tailored only to the public examples.

Checkpoint pages identify which requirements are checked mechanically and which are reviewed by the instructor.

Course-owned versus student-owned code

The project distinguishes between course infrastructure and student implementations:

src/course/     course-owned
src/student/    student-owned

Local tests can help detect accidental changes to course-owned files. The authoritative grading environment may also use its own copy of course infrastructure so that the algorithms being assessed are evaluated against the documented project contract.

A productive development cycle

A typical cycle is:

make one algorithmic change
    ↓
run one small instance
    ↓
run the relevant public tests
    ↓
inspect the result
    ↓
make the next change

Use the benchmark runner for experimental evidence after the implementation is stable; do not use large benchmark sweeps as a substitute for small correctness tests.

5 - 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.

6 - 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

Milestone 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.

Weighted Graph Files

Traveling Salesperson uses complete, undirected weighted graphs. The standard weighted edge-list format begins with:

n m

followed by m lines of the form:

u v weight

For example:

4 6
0 1 8
0 2 5
0 3 9
1 2 6
1 3 4
2 3 7

Weights are nonnegative integers. As with unweighted graphs, vertices are numbered from 0 through n-1, self-loops are not permitted, and parallel edges are not permitted.

A Traveling Salesperson instance must describe a complete graph, so every pair of distinct vertices must have a weight. For an n-vertex TSP instance, there are therefore

undirected edges.

TSPLIB-Style TSP Files

The course reader also supports a subset of TSPLIB-style symmetric TSP files. Files with a .tsp extension (including .tsp.gz) are detected automatically.

The supported coordinate format is:

TYPE: TSP
DIMENSION: n
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 x1 y1
2 x2 y2
...
EOF

TSPLIB node labels are conventionally numbered 1 through n. The course reader converts them to the 0-based vertex IDs used by the project API. Edge weights are computed using the standard TSPLIB EUC_2D rounding rule.

You are not expected to implement TSPLIB parsing or distance conversion. Your algorithm receives the same course-provided weighted-graph representation regardless of whether the input came from an explicit weighted edge list or a TSPLIB coordinate file.

Course-Generated Random TSP Files

Some large TSP benchmarks use a compact course-generated format instead of storing all $O(n^2)$ edge weights explicitly. These files use TSPLIB-style headers with:

EDGE_WEIGHT_TYPE: BBF_RANDOM_UNIFORM
BBF_RANDOM_SEED: ...
BBF_WEIGHT_MIN: ...
BBF_WEIGHT_MAX: ...

The course support code uses this metadata to generate the complete weighted graph deterministically. The same file therefore produces the same edge weights on every run without requiring a large explicit edge list.

You are not expected to generate or parse this format yourself. Treat these instances exactly like other weighted TSP instances through the course-provided weighted-graph interface described on the Program Interface page.