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.