JAVA-205 · Lesson 12 of 12 · 23 min
Capstone: solving and analyzing algorithm problems
▶ Video coming soon A video version of this lesson is on the way.
The term's last project is the one Kofi has been waiting for since September: a Saturday pickup planner. Hamza builds it from Monday, December 6 to Thursday, December 9, 2027, and reviews it with Ingrid and Kofi on Tuesday, December 14, before the shop's winter schedule starts. The program, PickupPlanner, reuses almost everything from the term: Dijkstra for riding times, a search over visiting orders, a greedy shortcut, the knapsack table for the trailer and edit distance for typed codes. This lesson follows how Hamza turns Kofi's wishes into algorithms, checks them and writes down what each one costs, which is the real skill the course has been building.
Step 1: state the problems precisely
Kofi's wishes start vague: plan the Saturday run, do not overload the trailer, catch my typos. Ingrid's first rule is that you cannot choose an algorithm until the problem is precise: what is the input, what exactly is the output, and how large can the input get? Hamza writes six numbered requirements, with sizes, and agrees them with Kofi before writing any code.
| Requirement | Input | Output | Size |
|---|---|---|---|
| R1 Riding times | The pickup road graph | The quickest riding time between every pair of places | 7 places now, up to 15 by 2030 |
| R2 Round trip | The sites with donations waiting this Saturday | An order to visit them, starting and ending at the Shop, with the least riding | Usually 3 to 6 sites, never more than 9 |
| R3 Quick plan | The same, when Kofi wants an instant answer on his phone | A good order, not necessarily the best | Any number of sites |
| R4 Trailer load | Donations waiting, with space and value | The most valuable load that fits 10 units | Up to 30 items |
| R5 Typed codes | A code as typed and the list of real codes | The nearest real code | 612 codes of about 10 characters |
| R6 Cost note | The algorithms above | A written Big-O for each, checked by counting | — |
Step 2: R1, the riding times
R1 asks for all-pairs shortest riding times. The graph has non-negative weights, so Dijkstra applies, and running it once from every place gives the whole table. That is V runs of O((V + E) log V), which for 7 places and 10 roads is a few hundred steps. The table is computed once each Saturday morning and then used by everything else, which is the classic move of precomputing an answer many later steps need.
import java.util.*;
public class Main {
record Edge(int to, int minutes) {}
static final String[] PLACES = {"Shop", "German Village", "Bexley", "Short North", "Grandview", "Hilltop", "Clintonville"};
static int[][] distances() {
int[][] roads = {{0, 1, 9}, {0, 2, 11}, {1, 2, 7}, {1, 3, 12}, {0, 3, 23},
{3, 4, 10}, {4, 5, 14}, {3, 5, 26}, {2, 6, 18}, {0, 6, 31}};
int n = PLACES.length;
List<List<Edge>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] r : roads) { g.get(r[0]).add(new Edge(r[1], r[2])); g.get(r[1]).add(new Edge(r[0], r[2])); }
int[][] d = new int[n][];
for (int s = 0; s < n; s++) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[1]).thenComparingInt(a -> a[0]));
pq.add(new int[] {s, 0});
boolean[] done = new boolean[n];
while (!pq.isEmpty()) {
int[] top = pq.poll();
if (done[top[0]]) continue;
done[top[0]] = true;
for (Edge e : g.get(top[0])) {
if (top[1] + e.minutes() < dist[e.to()]) {
dist[e.to()] = top[1] + e.minutes();
pq.add(new int[] {e.to(), dist[e.to()]});
}
}
}
d[s] = dist;
}
return d;
}
public static void main(String[] args) {
int[][] d = distances();
for (int i = 0; i < d.length; i++) {
StringBuilder row = new StringBuilder();
for (int x : d[i]) row.append(String.format("%4d", x));
System.out.println(row + " " + PLACES[i]);
}
}
}0 9 11 21 31 45 29 Shop 9 0 7 12 22 36 25 German Village 11 7 0 19 29 43 18 Bexley 21 12 19 0 10 24 37 Short North 31 22 29 10 0 14 47 Grandview 45 36 43 24 14 0 61 Hilltop 29 25 18 37 47 61 0 Clintonville
What this code does
distances runs Dijkstra from each of the seven places using int arrays in the priority queue, and stores each result as one row of the table. The table is symmetric because every road can be ridden both ways. The Shop's row repeats lesson 9's results, with Hilltop 45 minutes away and Clintonville 29.
Step 3: R2, the best round trip
R2 is a famous problem: find the shortest round trip through a set of places, returning to the start. It is the traveling salesman problem, and no algorithm is known that solves it efficiently for large inputs; it belongs to the class of problems called NP-hard. But Kofi's sizes are small. With k sites there are k! visiting orders, so 6 sites have 720 orders and 9 have 362,880, which a laptop checks in a fraction of a second. Hamza therefore uses an exact method, trying every order recursively, for R2.
import java.util.*;
public class Main {
record Edge(int to, int minutes) {}
static final String[] PLACES = {"Shop", "German Village", "Bexley", "Short North", "Grandview", "Hilltop", "Clintonville"};
static int[][] distances() {
int[][] roads = {{0, 1, 9}, {0, 2, 11}, {1, 2, 7}, {1, 3, 12}, {0, 3, 23},
{3, 4, 10}, {4, 5, 14}, {3, 5, 26}, {2, 6, 18}, {0, 6, 31}};
int n = PLACES.length;
List<List<Edge>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] r : roads) { g.get(r[0]).add(new Edge(r[1], r[2])); g.get(r[1]).add(new Edge(r[0], r[2])); }
int[][] d = new int[n][];
for (int s = 0; s < n; s++) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[1]).thenComparingInt(a -> a[0]));
pq.add(new int[] {s, 0});
boolean[] done = new boolean[n];
while (!pq.isEmpty()) {
int[] top = pq.poll();
if (done[top[0]]) continue;
done[top[0]] = true;
for (Edge e : g.get(top[0])) {
if (top[1] + e.minutes() < dist[e.to()]) {
dist[e.to()] = top[1] + e.minutes();
pq.add(new int[] {e.to(), dist[e.to()]});
}
}
}
d[s] = dist;
}
return d;
}
static int[][] d;
static int bestLength = Integer.MAX_VALUE, tried = 0;
static int[] bestOrder;
static void tryOrders(int[] order, int k, boolean[] used, int[] sites) {
if (k == sites.length) {
tried++;
int len = 0, at = 0;
for (int s : order) { len += d[at][s]; at = s; }
len += d[at][0];
if (len < bestLength) { bestLength = len; bestOrder = order.clone(); }
return;
}
for (int i = 0; i < sites.length; i++) {
if (used[i]) continue;
used[i] = true;
order[k] = sites[i];
tryOrders(order, k + 1, used, sites);
used[i] = false;
}
}
public static void main(String[] args) {
d = distances();
int[] sites = {1, 2, 3, 4, 5, 6};
tryOrders(new int[sites.length], 0, new boolean[sites.length], sites);
StringBuilder route = new StringBuilder(PLACES[0]);
for (int s : bestOrder) route.append(" -> ").append(PLACES[s]);
System.out.println(route + " -> " + PLACES[0]);
System.out.println("best " + bestLength + " minutes, " + tried + " orders tried");
}
}Shop -> German Village -> Short North -> Grandview -> Hilltop -> Bexley -> Clintonville -> Shop best 135 minutes, 720 orders tried
What this code does
tryOrders builds every order of the six sites one position at a time, marking each site used while it is in the order and freeing it again afterwards, which is called backtracking. Each complete order is measured from the Shop round to the Shop using the R1 table. All 720 orders are tried, and the best round trip takes 135 minutes.
Step 4: R3, a quick plan
For R3 Kofi wants an answer instantly for any number of sites, even if it is not perfect. The obvious greedy rule is nearest neighbor: from where you are, ride to the closest site not yet visited, and when none are left, ride home. It is O(k²) for k sites. The review question is how good it is, and the only honest way to know is to compare it with the exact answer where both can be computed.
import java.util.*;
public class Main {
record Edge(int to, int minutes) {}
static final String[] PLACES = {"Shop", "German Village", "Bexley", "Short North", "Grandview", "Hilltop", "Clintonville"};
static int[][] distances() {
int[][] roads = {{0, 1, 9}, {0, 2, 11}, {1, 2, 7}, {1, 3, 12}, {0, 3, 23},
{3, 4, 10}, {4, 5, 14}, {3, 5, 26}, {2, 6, 18}, {0, 6, 31}};
int n = PLACES.length;
List<List<Edge>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] r : roads) { g.get(r[0]).add(new Edge(r[1], r[2])); g.get(r[1]).add(new Edge(r[0], r[2])); }
int[][] d = new int[n][];
for (int s = 0; s < n; s++) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[1]).thenComparingInt(a -> a[0]));
pq.add(new int[] {s, 0});
boolean[] done = new boolean[n];
while (!pq.isEmpty()) {
int[] top = pq.poll();
if (done[top[0]]) continue;
done[top[0]] = true;
for (Edge e : g.get(top[0])) {
if (top[1] + e.minutes() < dist[e.to()]) {
dist[e.to()] = top[1] + e.minutes();
pq.add(new int[] {e.to(), dist[e.to()]});
}
}
}
d[s] = dist;
}
return d;
}
public static void main(String[] args) {
int[][] d = distances();
List<Integer> left = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
int at = 0, total = 0;
StringBuilder route = new StringBuilder(PLACES[0]);
while (!left.isEmpty()) {
int next = left.get(0);
for (int s : left) if (d[at][s] < d[at][next]) next = s;
total += d[at][next];
route.append(" -> ").append(PLACES[next]);
left.remove(Integer.valueOf(next));
at = next;
}
total += d[at][0];
System.out.println(route + " -> " + PLACES[0]);
System.out.println("greedy plan: " + total + " minutes");
}
}Shop -> German Village -> Bexley -> Clintonville -> Short North -> Grandview -> Hilltop -> Shop greedy plan: 140 minutes
What this code does
From each place the loop picks the unvisited site with the smallest riding time and moves there. It leaves Hilltop, the farthest site, until last, and then has the long ride home. The plan takes 140 minutes, five more than the best round trip.
Five minutes out of 135 is about 4 in 100, and Kofi decides that is fine for a quick phone plan, provided the planner says which method it used. Hamza adds one more check that the review asks for: on smaller sets of sites, such as three or four, nearest neighbor often finds the best route exactly. A greedy heuristic is not wrong; it just needs its quality measured and reported.
Step 5: why trying every order stops working
The exact method is fine at Kofi's sizes, but the review asks what happens if the scheme grows to 15 sites by 2030. Counting gives the answer before any code runs. k! grows faster than any power and faster even than 2ᵏ. A cleverer exact method, the Held-Karp dynamic programming algorithm, needs about k² × 2ᵏ steps, which is far better but still exponential. For large inputs, real route planners use heuristics, improved by local tweaks such as swapping two legs of the route, and accept answers that are very close to the best.
public class Main {
public static void main(String[] args) {
System.out.println("sites orders (k!) Held-Karp (k^2 2^k)");
long fact = 1;
for (int k = 1; k <= 15; k++) {
fact *= k;
long hk = (long) k * k * (1L << k);
if (k >= 4) System.out.printf("%-7d %-18d %d%n", k, fact, hk);
}
}
}sites orders (k!) Held-Karp (k^2 2^k) 4 24 256 5 120 800 6 720 2304 7 5040 6272 8 40320 16384 9 362880 41472 10 3628800 102400 11 39916800 247808 12 479001600 589824 13 6227020800 1384448 14 87178291200 3211264 15 1307674368000 7372800
What this code does
The program prints how the number of visiting orders grows, next to the step count of the Held-Karp algorithm. Nine sites mean 362,880 orders, which is quick, but 15 sites mean more than a trillion. Held-Karp brings 15 sites down to about 7.4 million steps, while staying exponential.
Step 6: R4 and R5, reusing earlier work
R4 is exactly lesson 11's 0/1 knapsack: at most 30 items and 10 units of space make a 31 × 11 table, a few hundred cells. R5 is lesson 11's edit distance, compared against all 612 codes: 612 tables of about 11 × 11 cells, roughly 74,000 cell updates per typed code, which is instant. Hamza's main work for both is wrapping existing, tested methods in clear interfaces, which is the point of building a toolkit of algorithms. Kofi asks one improvement: suggest only when the distance is at most 2, and otherwise say the code is unknown, so the planner never confidently suggests a wrong part.
import java.util.*;
public class Main {
static int distance(String a, String b) {
int[] prev = new int[b.length() + 1], cur = new int[b.length() + 1];
for (int j = 0; j <= b.length(); j++) prev[j] = j;
for (int i = 1; i <= a.length(); i++) {
cur[0] = i;
for (int j = 1; j <= b.length(); j++) {
int same = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
cur[j] = Math.min(Math.min(prev[j] + 1, cur[j - 1] + 1), prev[j - 1] + same);
}
int[] t = prev; prev = cur; cur = t;
}
return prev[b.length()];
}
static String suggest(String typed, List<String> codes) {
String best = null;
int bestD = 3;
for (String c : codes) {
int dd = distance(typed, c);
if (dd < bestD) { bestD = dd; best = c; }
}
return best == null ? typed + ": unknown code" : typed + ": did you mean " + best + "?";
}
public static void main(String[] args) {
List<String> codes = List.of("BELL", "CABLE-BRAKE", "CHAIN-11", "GRIPS", "PAD-DISC", "PAD-ROAD", "TUBE-700x25");
for (String t : List.of("CHIAN-11", "PAD-RAOD", "SADDLE", "BEL")) System.out.println(suggest(t, codes));
}
}CHIAN-11: did you mean CHAIN-11? PAD-RAOD: did you mean PAD-ROAD? SADDLE: unknown code BEL: did you mean BELL?
What this code does
This edit distance keeps only two rows of the table, because each row needs only the one before it, so memory drops from m times n cells to two short arrays. suggest starts its best distance at 3, so only codes within 2 edits are offered. SADDLE is far from every real code and is reported as unknown instead of being matched to something wrong.
Step 7: R6, the cost note
| Requirement | Method | Cost | At today's sizes |
|---|---|---|---|
| R1 | Dijkstra from every place | O(V (V + E) log V) | A few hundred steps |
| R2 | Try every order with backtracking | O(k! × k) | 720 orders for 6 sites; 362,880 for 9 |
| R3 | Nearest neighbor | O(k²) | 21 comparisons for 6 sites |
| R4 | 0/1 knapsack table | O(n × C) | 330 cells for 30 items |
| R5 | Edit distance against every code | O(N × m²) | About 74,000 cell updates |
| R5 sort | Run sheet sorted by arrival time with List.sort | O(k log k) | Trivial |
Writing the cost note is where Big-O stops being an exam topic. It tells Kofi what will still work when the scheme grows and what will not. R1, R3, R4 and R5 will scale comfortably for years. R2 is fine up to about 10 sites and then needs to switch to the heuristic, and the planner now does that automatically, saying so on screen. The review also records two follow-ups for next term's courses: storing the road graph in a database, and offering the planner as a web service.
A checklist for any algorithm problem
- Make the problem precise: inputs, outputs and realistic sizes.
- Recognize the problem: is it a search, a sort, a shortest path, a scheduling, a knapsack or a matching problem you already know?
- Write the simplest correct method first, often brute force, and use it to check faster ones on small inputs.
- Estimate the cost by counting before running, and compare it with the real sizes.
- Reuse library code and earlier tested methods; write new code only where the problem is new.
- Test edge cases: empty inputs, one element, ties, unreachable places, duplicate codes.
- Write down what each part costs and where it will stop scaling.
Try it yourself
Length of a round trip
Complete tourLength(int[][] d, int[] order), which returns the riding time of a round trip that starts at place 0, visits the places in order, and returns to place 0, using the distance table d.
The program should print 135 and 140, one per line.
public class Main {
static int tourLength(int[][] d, int[] order) {
int total = 0;
for (int i = 0; i + 1 < order.length; i++) total += d[order[i]][order[i + 1]];
return total;
}
public static void main(String[] args) {
int[][] d = {
{0, 9, 11, 21, 31, 45, 29}, {9, 0, 7, 12, 22, 36, 25}, {11, 7, 0, 19, 29, 43, 18},
{21, 12, 19, 0, 10, 24, 37}, {31, 22, 29, 10, 0, 14, 47}, {45, 36, 43, 24, 14, 0, 61},
{29, 25, 18, 37, 47, 61, 0}};
System.out.println(tourLength(d, new int[] {1, 3, 4, 5, 2, 6}));
System.out.println(tourLength(d, new int[] {1, 2, 6, 3, 4, 5}));
}
}Try it yourself
Nearest neighbor on a smaller run
Write nearestNeighbor(int[][] d, int[] sites), which starts at place 0, repeatedly rides to the closest unvisited site (taking the first one in sites when two are equally close), and returns the order as a List.
For sites 2, 4 and 6 the program should print [2, 6, 4].
import java.util.*;
public class Main {
static List<Integer> nearestNeighbor(int[][] d, int[] sites) {
List<Integer> order = new ArrayList<>();
for (int s : sites) order.add(s);
return order;
}
public static void main(String[] args) {
int[][] d = {
{0, 9, 11, 21, 31, 45, 29}, {9, 0, 7, 12, 22, 36, 25}, {11, 7, 0, 19, 29, 43, 18},
{21, 12, 19, 0, 10, 24, 37}, {31, 22, 29, 10, 0, 14, 47}, {45, 36, 43, 24, 14, 0, 61},
{29, 25, 18, 37, 47, 61, 0}};
System.out.println(nearestNeighbor(d, new int[] {4, 6, 2}));
}
}Common mistakes
MistakeChoosing an algorithm before the problem and its sizes are precise.
InsteadWrite down inputs, outputs and realistic sizes first.
MistakeUsing brute force without counting how many cases it will try.
InsteadWork out k! or 2ᵏ for the real sizes before running it.
MistakeTrusting a heuristic without measuring it.
InsteadCompare it with an exact method on inputs small enough for both.
MistakeWriting every method from scratch.
InsteadReuse tested methods and library code, and wrap them in clear interfaces.
MistakeSuggesting a typed code however far away it is.
InsteadSet a limit on the edit distance and report unknown codes.
Summary and key terms
- The capstone turns vague wishes into six precise requirements with inputs, outputs and sizes, then chooses an algorithm for each.
- All-pairs riding times come from running Dijkstra from every place and are precomputed once.
- The best round trip is the traveling salesman problem, NP-hard in general, but at 6 to 9 sites trying every order with backtracking is fast, finding a 135-minute trip from 720 orders.
- The nearest-neighbor heuristic is O(k²) and gave 140 minutes, about 4 in 100 longer, which Kofi accepts for quick plans because its quality was measured.
- Counting shows k! orders explode beyond about 10 sites, and Held-Karp's k² × 2ᵏ is better but still exponential.
- The trailer load reuses the knapsack table and typed codes reuse edit distance with a distance limit and two-row memory.
- A written cost note records each method's Big-O and where it stops scaling.
- Requirement
- A precise statement of an input, the output wanted and its realistic size.
- Precomputing
- Computing an answer once so that many later steps can reuse it.
- Traveling salesman problem
- Finding the shortest round trip through a set of places.
- NP-hard
- Describes problems for which no efficient algorithm is known for large inputs.
- Backtracking
- Building candidate solutions step by step and undoing each choice to try the next.
- Heuristic
- A fast method that usually gives a good answer but is not guaranteed to give the best.
- Nearest neighbor
- A greedy heuristic that always moves to the closest unvisited place.
- Held-Karp algorithm
- A dynamic programming method for the traveling salesman problem in about k² × 2ᵏ steps.
- Cost note
- A written record of each part of a system's algorithm and how its cost grows.
Practice problems
Work each problem on paper first, then reveal the answer to check.
How many visiting orders are there for 8 sites?
Show answer
8! = 40,320.
Why does R1 run Dijkstra once from every place?
Show answer
To build the full table of quickest times between all pairs, which R2 to R5 reuse.
How much longer was the nearest-neighbor plan than the best round trip?
Show answer
5 minutes: 140 against 135.
Why does the planner limit typo suggestions to a distance of 2?
Show answer
So it never confidently suggests a code that is far from what was typed.
What does the cost note say about R2 beyond about 10 sites?
Show answer
Trying every order becomes too slow, so the planner switches to the heuristic.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.