Start Here

1 - Getting Started

Goal: Form your team and submit your three ranked project preferences.
Points: 5 · Submission: Gradescope

Project Selection comes before Checkpoint 1. Follow the four steps below in order.

1. Form your team

Work in a team of two or three students, and choose a team name. Students who have instructor approval to work individually may submit as a one-person team. You will need the name of every team member for your submission.

2. Select your preferred problems

Read the five problem definitions before making your choices. Discuss them with your teammates and rank three distinct projects from most preferred (1) to least preferred (3). You are selecting preferences; you are not choosing your final assigned problem.

3. Complete the JSON file

Download the following files (also available with the Gradescope assignment):

• project.json
• Local validation script

Open it in a plain-text editor and fill in:

• team_name: your team name (individual students should also choose a name);
• team_members: exactly one entry per student, each containing only a name field;
• project_preferences: your three different project identifiers, ordered from first choice to third choice;
• assigned_problem: leave as the empty string ("") until your assignment is announced.

The starter file has two blank name entries. Adjust the team_members array to match your actual team:

• One student (instructor-approved): delete one of the two name entries, including the extra comma. Keep just one {"name": "..."} object.
• Two students: fill in the two existing name entries.
• Three students: add a third {"name": "..."} object after the second, separated by a comma. The example below shows the required syntax.

Example: three students

{
  "team_name": "Graph Gurus",
  "team_members": [
    {"name": "Ada Example"},
    {"name": "Grace Example"},
    {"name": "Edsger Example"}
  ],
  "project_preferences": [
    "minimum_vertex_cover",
    "maximum_clique",
    "traveling_salesperson"
  ],
  "assigned_problem": ""
}

Check your file locally by placing check_project_selection.py beside project.json and running:

python3 check_project_selection.py

The checker prints PASS when the file is formatted correctly. It uses the same validation rules as the Gradescope autograder.

4. Submit on Gradescope

BBF - Problem and Group Selection Open BBF - Problem and Group Selection on Gradescope. One student uploads project.json directly. For teams of two or three, include all teammates in the Gradescope group submission. Review the automatic feedback and resubmit if necessary before the deadline.

Submission checklist

• We have a team name and the names of every student (one student only when approved by the instructor).
• We ranked three distinct projects using the required identifiers.
• assigned_problem is "".
• The file is named project.json and the local checker reports PASS.
• We submitted on Gradescope and included all teammates in the group submission, when applicable.

Grading (5 points)

4. The instructor assigns your project

The instructor will review the class’s ranked preferences, assign one of the five projects to each team or individual, and announce the assignments. Preferences are not guaranteed.

After your project is assigned, you will receive instructions for creating your shared repository through Classroom 50 as part of Checkpoint 1: Foundation. Do not create a project repository during Project Selection.

2 - Learning Objectives

By completing Beyond Brute Force, you should be able to:

• explain the relationship between an NP-complete decision problem and its optimization version;
• identify what constitutes a feasible solution and explain how a proposed solution can be verified efficiently;
• implement and analyze a straightforward exhaustive exact algorithm;
• reason about the state of an exact search and whether repeated subproblems are present;
• improve exact computation using an appropriate algorithm-design technique while preserving optimality;
• construct and justify a valid polynomial-time bound for an optimization problem;
• design and evaluate a polynomial-time heuristic for instances where exact computation becomes impractical;
• use reproducible randomized experiments and best-so-far behavior to evaluate heuristic approaches;
• compare heuristic results with known optima when available and with valid bounds or best-known solutions when OPT is unknown;
• perform controlled experiments across a collection of problem instances;
• identify input characteristics that affect computational effort or solution quality; and
• communicate algorithmic conclusions using appropriately qualified experimental evidence.

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

• 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 bound is an efficiently computed value guaranteed to lie on the appropriate side of the optimum.
• A heuristic algorithm returns a valid solution but does not necessarily guarantee optimality. For this project, heuristics must run in polynomial time so they can scale beyond the practical range of exact computation.

The checkpoint pages translate these project-wide objectives into concrete work for each stage.