Escape from Exponential Island

4 minute read

Escape from Exponential Island

Abstract

This assignment teaches students how to approach computationally intractable problems from both theoretical and practical perspectives. Working in small groups, students undertake a progression that begins with a straightforward brute-force solution, improves the exact search using techniques such as backtracking and pruning, and culminates in the design and analysis of approximation algorithms.

For many students, this assignment is their first sustained encounter with problems whose input spaces grow beyond the reach of exhaustive computation. Rather than treating NP-completeness only as a formal classification, the assignment asks students to experience the consequences of intractability directly. Students measure how quickly brute-force approaches become infeasible, investigate how pruning changes the practical limits of exact search, and then explore how approximation and anytime algorithms can produce useful solutions when optimal solutions are too expensive to compute.

The assignment also connects empirical experimentation with formal algorithmic reasoning. Students analyze the running time of each approach, study reductions that establish the NP-completeness of the corresponding decision problem, and evaluate the quality of approximate solutions using lower or upper bounds on the optimum. A leaderboard-based competition further motivates students to refine their algorithms, as submissions are evaluated across benchmark instances using an autograder. Because the benchmark suite contains multiple instances rather than a single target input, students are encouraged to design robust strategies instead of tuning their solutions to one case.

Metadata

Section	Details
Summary	In this assignment, students explore NP-complete problems by progressing from brute-force exact search, to improved exact search with pruning and backtracking, to approximation and anytime algorithms. Students analyze runtime behavior, study reductions, evaluate approximation quality, and compare their algorithms on benchmark instances.
Topics	NP-completeness Reductions Brute-force search Backtracking and pruning Approximation algorithms Anytime algorithms Runtime analysis Benchmarking and empirical evaluation
Audience	The assignment serves as the final project in a senior undergraduate algorithms class where students have covered asymptotic analysis, recursion, graph or search algorithms, and the formal definitions of P, NP, and NP-completeness.
Difficulty	Moderate to challenging. The individual programming components are accessible to senior undergraduates, but the full project requires students to connect implementation, empirical measurement, formal reductions, runtime analysis, and approximation quality.
Length	Approximately 3.5 weeks. The assignment is divided into several checkpoints so that students make steady progress and receive feedback before the final benchmark evaluation and presentation.
Strengths	Connects the theory of NP-completeness to the practical experience of confronting problems whose exact solutions quickly become computationally infeasible. Gives students a staged progression from brute force to pruning to approximation, making algorithmic tradeoffs visible. Uses benchmark sets and an autograded leaderboard to motivate robust approximation strategies rather than tuning to a single instance. Includes checkpoints, presentations, and peer critiques that support iterative development and mature algorithmic discussion.
Weaknesses	The project is larger than a typical one-week programming assignment and requires careful scheduling. Students may initially focus too much on leaderboard performance unless the written analysis and critique components are clearly emphasized. Some approximation strategies may be problem-specific, so instructors may need to guide students toward generalizable algorithmic ideas.
Dependencies	Knowledge dependencies: Asymptotic notation and runtime analysis Recursion and recursive search Basic proof techniques Definitions of P, NP, and NP-completeness Familiarity with reductions Software dependencies: Programming language: TODO Autograder: TODO Starter code: TODO Benchmark data format: TODO
Variants	The assignment can be shortened by omitting the formal reduction component or by providing the reduction as part of the handout. The assignment can be made more theoretical by requiring students to prove approximation bounds or justify upper/lower bounds on the optimum. The assignment can be made more implementation-focused by emphasizing heuristic design, anytime behavior, and benchmark performance. The leaderboard can be private, public, or optional depending on the desired classroom culture.
Teaching Notes	The project works best when divided into checkpoints. Early checkpoints can require students to implement a brute-force solver, measure input-space growth, and analyze the relationship between the optimization problem and the NP-complete decision version. Later checkpoints can focus on pruning, approximation, anytime behavior, and benchmark evaluation. The final presentation and peer-critique components are valuable for turning the assignment into a mature algorithmic investigation. Students explain their design choices, interpret empirical results, compare tradeoffs, and ask pointed questions about other groups' approaches.

This is the end of the document.

Last modified June 20, 2026: more npcomplete project work (780a3d4)