JAVA-205 · Lesson 12 of 12 · 23 min

Capstone: solving and analysing 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.

PickupPlanner requirements
RequirementInputOutputSize
R1 Riding timesThe pickup road graphThe quickest riding time between every pair of places7 places now, up to 15 by 2030
R2 Round tripThe sites with donations waiting this SaturdayAn order to visit them, starting and ending at the Shop, with the least ridingUsually 3 to 6 sites, never more than 9
R3 Quick planThe same, when Kofi wants an instant answer on his phoneA good order, not necessarily the bestAny number of sites
R4 Trailer loadDonations waiting, with space and valueThe most valuable load that fits 10 unitsUp to 30 items
R5 Typed codesA code as typed and the list of real codesThe nearest real code612 codes of about 10 characters
R6 Cost noteThe algorithms aboveA 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.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(int to, int minutes) {}

    static final String[] PLACES = {"Shop", "Corktown", "Crown Point", "Kirkendall", "Westdale", "Dundas", "Stoney Creek"};

    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]);
        }
    }
}
Output
   0   9  11  21  31  45  29   Shop
   9   0   7  12  22  36  25   Corktown
  11   7   0  19  29  43  18   Crown Point
  21  12  19   0  10  24  37   Kirkendall
  31  22  29  10   0  14  47   Westdale
  45  36  43  24  14   0  61   Dundas
  29  25  18  37  47  61   0   Stoney Creek

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 Dundas 45 minutes away and Stoney Creek 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 travelling 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.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(int to, int minutes) {}

    static final String[] PLACES = {"Shop", "Corktown", "Crown Point", "Kirkendall", "Westdale", "Dundas", "Stoney Creek"};

    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");
    }
}
Output
Shop -> Corktown -> Kirkendall -> Westdale -> Dundas -> Crown Point -> Stoney Creek -> 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 neighbour: 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.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(int to, int minutes) {}

    static final String[] PLACES = {"Shop", "Corktown", "Crown Point", "Kirkendall", "Westdale", "Dundas", "Stoney Creek"};

    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");
    }
}
Output
Shop -> Corktown -> Crown Point -> Stoney Creek -> Kirkendall -> Westdale -> Dundas -> 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 Dundas, the farthest site, until last, and then has the long ride home. The plan takes 140 minutes, five more than the best round trip.

Two copies of the pickup map side by side. Left, labelled best, 135 minutes: Shop to Corktown, Kirkendall, Westdale, Dundas, then back across to Crown Point, Stoney Creek and the Shop. Right, labelled nearest neighbour, 140 minutes: Shop to Corktown, Crown Point, Stoney Creek, Kirkendall, Westdale, Dundas, then the long ride home from Dundas.
The exact round trip and the nearest-neighbour plan for all six sites

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

Java Example · Main.java
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);
        }
    }
}
Output
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.

Java Example · Main.java
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));
    }
}
Output
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

The PickupPlanner cost note
RequirementMethodCostAt today's sizes
R1Dijkstra from every placeO(V (V + E) log V)A few hundred steps
R2Try every order with backtrackingO(k! × k)720 orders for 6 sites; 362,880 for 9
R3Nearest neighbourO(k²)21 comparisons for 6 sites
R40/1 knapsack tableO(n × C)330 cells for 30 items
R5Edit distance against every codeO(N × m²)About 74,000 cell updates
R5 sortRun sheet sorted by arrival time with List.sortO(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 neighbour 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 travelling 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-neighbour 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.
Travelling 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 neighbour
A greedy heuristic that always moves to the closest unvisited place.
Held-Karp algorithm
A dynamic programming method for the travelling 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.

  1. How many visiting orders are there for 8 sites?

    Show answer

    8! = 40,320.

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

  3. How much longer was the nearest-neighbour plan than the best round trip?

    Show answer

    5 minutes: 140 against 135.

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

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

Take the quiz