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.