Phase 5: Advanced Algorithms & Graphs

Everything so far has been about one structure at a time: a list, a tree, a heap. This phase is about the two ideas that turn those structures into real algorithms. The first is the graph: nodes joined by edges, which describes road networks, prerequisites, social networks, and (less obviously) grids and word puzzles. The second is a family of problem-solving paradigms: dynamic programming, backtracking and greedy choice. They are not data structures; they are ways of organising a search through a space of possibilities so that it finishes in your lifetime.

By the end of this phase you will be able to look at a problem and say "this is a BFS on an implicit graph", "this needs a topological order", or "the state is a pair of prefixes, so it is a 2D DP", and then write the code from a template you know by heart. Every section ends with problems from this phase that practise exactly that template.

Graph representations

A graph is a set of nodes (also called vertices) and a set of edges between them. Edges can be directed (u -> v only) or undirected (u -- v, both ways), and can carry a weight (a cost, a distance, a time).

Problems usually give you a graph as n plus a list of edges, because that is the smallest honest description. Almost no algorithm works on an edge list directly, so the first line of nearly every graph solution converts it to an adjacency list: for each node, the list of its neighbours.

n = 4
edges = [[0, 1], [1, 2], [2, 3], [0, 3]]

adj = [[] for _ in range(n)]      # NOT [[]] * n  (that makes n aliases of one list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)              # undirected: record both directions
print(adj)

[[1, 3], [0, 2], [1, 3], [2, 0]]

For a directed graph drop the second append. For a weighted graph store pairs: adj[u].append((v, w)). When node labels are strings or non-contiguous integers, use defaultdict(list) instead of a list of lists.

The alternative is an adjacency matrix, an n x n table where matrix[u][v] is 1 (or the weight) when the edge exists. It answers "is u joined to v?" in O(1) but costs O(n^2) memory and makes "list the neighbours of u" an O(n) scan, so it is only worth it for small dense graphs. You will meet it as an input format (for instance the "Number of Provinces" problem) more often than you will choose it yourself.

The third representation is one you never build at all. A grid is an implicit graph: each cell is a node, and its up/down/left/right neighbours are its edges. You compute neighbours on the fly with a list of direction offsets:

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbours(grid, r, c):
    m, n = len(grid), len(grid[0])
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n:     # bounds check first, always
            yield nr, nc

print(list(neighbours([[0, 0, 0], [0, 0, 0]], 0, 0)))

[(1, 0), (0, 1)]

Word Ladder pushes the idea further: the nodes are words and the "edges" are generated by changing one letter. If you can answer "what are the neighbours of this thing?" you have a graph, whether or not anyone wrote it down.

Common mistakes: [[]] * n creates one list referenced n times, so appending to adj[0] also changes adj[3]. Forgetting to add the reverse direction for undirected edges silently turns the graph into a directed one. Indexing a grid before checking bounds raises IndexError on the bottom and right edges and, worse, wraps around silently on the top and left edges because Python allows grid[-1].

Practice: Build an Adjacency List

BFS vs DFS

Both searches visit every node reachable from a start node exactly once; they differ only in the order. Breadth-first search (BFS) uses a queue and explores in rings: everything 1 step away, then everything 2 steps away, and so on. Depth-first search (DFS) uses a stack (or recursion) and follows one path as far as it goes before backing up.

The templates are nearly identical. The only structural difference is popleft() versus pop():

from collections import deque

def bfs(adj, start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for w in adj[u]:
            if w not in seen:
                seen.add(w)          # mark when ENQUEUED, not when popped
                q.append(w)
    return order

def dfs(adj, start):
    seen = {start}
    stack = [start]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for w in adj[u]:
            if w not in seen:
                seen.add(w)
                stack.append(w)
    return order

adj = [[1, 2], [0, 3], [0, 3], [1, 2]]
print(bfs(adj, 0))
print(dfs(adj, 0))

[0, 1, 2, 3]
[0, 2, 3, 1]

The seen set is not optional. Trees have no cycles so Phase 4 could get away without it; graphs do, and without seen the loop runs forever. Mark a node as seen the moment you push it, not when you pop it, or the same node can be pushed many times from different neighbours.

When to use which. BFS is the tool for shortest path in an unweighted graph, because the first time you reach a node you reached it by a shortest route. If the question mentions "minimum number of steps", "fewest moves" or "how many minutes until", reach for BFS and count levels. The level-by-level trick is to process len(q) nodes per outer iteration:

def shortest_steps(adj, start, target):
    seen = {start}
    q = deque([start])
    steps = 0
    while q:
        for _ in range(len(q)):       # exactly one level
            u = q.popleft()
            if u == target:
                return steps
            for w in adj[u]:
                if w not in seen:
                    seen.add(w)
                    q.append(w)
        steps += 1
    return -1

print(shortest_steps([[1, 2], [0, 3], [0, 3], [1, 2]], 0, 3))

2

Multi-source BFS is a small twist with a big payoff: if several things spread at the same speed (several rotten oranges, several fire sources, several exits), put all of them in the queue before the loop starts. The level count is then the time for the nearest source to reach each cell, for free.

DFS is the tool for reachability and structure: does a path exist, how many connected components are there, does the graph have a cycle, flood-fill this region. It is also the shape of backtracking. Recursive DFS is shorter to write, but Python's default recursion limit (6000 in this grader, 1000 in a normal interpreter) means a long chain of nodes can blow the stack; when in doubt, use the explicit-stack version above.

Counting components combines the outer loop with the search: every time the outer loop finds an unvisited node, that node starts a new component, and the inner search swallows everything in it.

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v); adj[v].append(u)
    seen = [False] * n
    count = 0
    for s in range(n):
        if not seen[s]:
            count += 1
            stack = [s]; seen[s] = True
            while stack:
                u = stack.pop()
                for w in adj[u]:
                    if not seen[w]:
                        seen[w] = True; stack.append(w)
    return count

print(count_components(5, [[0, 1], [1, 2], [3, 4]]))

2

Common mistakes: using a list as a queue (list.pop(0) is O(n), use deque). Returning the level after the loop instead of the level at which the target was popped. Forgetting that in a grid the "visited" marking can simply overwrite the cell (grid[r][c] = "0") if you are allowed to mutate the input.

Practice: Count Connected Components, Number of Islands, Rotting Oranges, Word Ladder

Topological sort (Kahn's algorithm)

A directed acyclic graph (DAG) is a directed graph with no cycles. Dependencies are DAGs: course prerequisites, build systems, spreadsheet formulas. A topological order lists the nodes so that every edge points from earlier to later; it is the order in which you can safely do the tasks. A topological order exists if and only if the graph is acyclic, so the same algorithm both finds the order and detects cycles.

Kahn's algorithm is BFS driven by in-degrees (how many edges point into a node). A node with in-degree 0 has no unmet prerequisites, so it can go first. Remove it, decrement the in-degrees of its successors, and repeat:

def topo_order(n, edges):          # edges are (before, after)
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for b, a in edges:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for w in adj[u]:
            indeg[w] -= 1
            if indeg[w] == 0:      # last prerequisite just got done
                q.append(w)
    return order if len(order) == n else []   # [] means a cycle

print(topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))
print(topo_order(2, [(0, 1), (1, 0)]))

[0, 1, 2, 3]
[]

If the queue runs dry before every node has been output, the leftovers all have in-degree at least 1, which is only possible if they are in a cycle. That is the whole cycle test.

Note the edge direction carefully. Course-schedule style problems usually give pairs [a, b] meaning "b before a", so the edge is b -> a. Reading it backwards produces the reverse of a valid order, which is not a valid order.

Common mistakes: pushing a node when its in-degree is decremented rather than when it reaches zero (it gets output before its prerequisites). Checking len(order) == n is easy to forget, and then a cyclic input returns a partial order that looks plausible.

Practice: Course Schedule, Course Schedule II

Union-find

Union-find (also called disjoint set union, DSU) maintains a partition of nodes into groups and supports two operations: find(x) returns a representative of x's group, and union(a, b) merges two groups. It is the right tool whenever edges arrive one at a time and you keep asking "are these two already connected?", which a fresh BFS would answer in O(n) each time.

Every node stores a parent; the root of each tree (a node that is its own parent) represents the group. Two optimisations make both operations effectively O(1) amortised:

• Path compression in find: as you walk up to the root, re-point every node you pass directly at the root (or at its grandparent, which is nearly as good and shorter to write).
• Union by size / rank: always attach the smaller tree under the larger one, so trees stay shallow.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False            # already connected: this edge closes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

d = DSU(5)
print(d.union(0, 1), d.union(1, 2), d.union(0, 2))
print(d.find(2) == d.find(0), d.find(3) == d.find(0))

True True False
True False

Because union returns False exactly when the edge joins two nodes that were already connected, union-find gives you undirected cycle detection in one line. Counting components is n minus the number of successful unions. Kruskal's MST algorithm (next section) is union-find plus a sort.

Common mistakes: comparing parent[a] == parent[b] instead of find(a) == find(b); parents are only representatives after compression, roots are the truth. Off-by-one on 1-indexed node labels: allocate n + 1 slots and ignore index 0.

Practice: Redundant Connection

Dijkstra with heapq

BFS finds shortest paths when every edge costs 1. When edges have different positive weights, the nearest unexplored node is no longer the one you enqueued first, so replace the queue with a min-heap keyed by distance. That is Dijkstra's algorithm: repeatedly settle the closest unsettled node and relax its outgoing edges.

import heapq, math

def dijkstra(adj, src):            # adj[u] = list of (v, w)
    dist = [math.inf] * len(adj)
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue               # stale entry: we already found a better route
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

adj = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
print(dijkstra(adj, 0))

[0, 3, 1, 4]

Python's heapq has no "decrease key" operation, so the standard trick is lazy deletion: push a new (distance, node) pair whenever you find a shorter route, and when you pop a pair whose distance is worse than the best known, skip it. The if d > dist[u]: continue line is what makes the algorithm correct and O(E log V); without it you re-relax nodes needlessly and, in graphs with many equal-length paths, become quadratic.

Dijkstra assumes non-negative weights. With a negative edge, a node you settled early might later become cheaper, and the algorithm has no way to revisit it. (Bellman-Ford handles that case; it is beyond this phase.) The heap tuples must be ordered by distance first, so always put the distance in position 0 of the tuple.

Common mistakes: pushing (node, distance) instead of (distance, node). Marking a node visited when pushed (that is BFS logic; in Dijkstra a node may be pushed several times and is settled when popped). Forgetting that unreachable nodes still have dist == inf at the end, which the problem usually wants reported as -1.

Practice: Network Delay Time

Minimum spanning trees

A spanning tree of a connected undirected graph uses n - 1 of its edges to connect all n nodes with no cycles. The minimum spanning tree (MST) is the one with the smallest total weight. "Connect all the cities with the least cable" and "connect all points as cheaply as possible" are MST problems.

Two greedy algorithms find the MST, and both are provably correct because of the cut property: the cheapest edge crossing any division of the nodes into two groups belongs to some MST.

Kruskal's algorithm sorts every edge by weight and adds each one whose endpoints are not yet connected. Union-find makes the "not yet connected" check nearly free:

def kruskal(n, edges):             # edges are (w, u, v)
    d = DSU(n)
    total = 0
    for w, u, v in sorted(edges):
        if d.union(u, v):
            total += w
    return total

print(kruskal(4, [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 2, 3), (5, 1, 3)]))

6

Prim's algorithm grows a single tree: start anywhere, keep a heap of the edges leaving the tree, and repeatedly add the cheapest edge to a node not yet in the tree. It looks exactly like Dijkstra with w in place of d + w:

def prim(adj):                     # adj[u] = list of (v, w), connected graph
    in_tree = [False] * len(adj)
    heap = [(0, 0)]
    total = 0
    while heap:
        w, u = heapq.heappop(heap)
        if in_tree[u]:
            continue
        in_tree[u] = True
        total += w
        for v, wt in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (wt, v))
    return total

adj = [[(1, 1), (2, 4)], [(0, 1), (2, 3), (3, 5)], [(0, 4), (1, 3), (3, 2)], [(1, 5), (2, 2)]]
print(prim(adj))

6

Use Kruskal when you already have an edge list (it is a sort plus a loop). Use Prim when the graph is dense or implicit, such as "every pair of points is an edge with cost equal to the distance", where you can generate the outgoing edges of a node on demand instead of building all O(n^2) of them.

Common mistakes: in Prim, pushing the accumulated distance from the start (that is Dijkstra) instead of just the edge weight. In Kruskal, forgetting to skip an edge whose union returned False.

Practice: Min Cost to Connect All Points

Dynamic programming

Dynamic programming (DP) is recursion with a memory. It applies when a problem has two properties: optimal substructure (the best answer for the whole is built from best answers for parts) and overlapping subproblems (the same parts get asked about many times). Recognising the second one is the trigger: if your recursive solution calls itself on the same arguments over and over, DP will turn an exponential algorithm into a polynomial one.

The clearest example is climbing stairs. To reach step n you came from step n - 1 or n - 2, so ways(n) = ways(n - 1) + ways(n - 2). Written naively:

calls = 0
def ways(n):
    global calls
    calls += 1
    if n <= 2:
        return n
    return ways(n - 1) + ways(n - 2)

print(ways(20), "in", calls, "calls")

10946 in 13529 calls

There are only 20 distinct inputs, yet the function is called 13,529 times because ways(18) is computed once inside ways(20) and again inside ways(19), and so on down. There are two standard fixes.

Top-down memoization keeps the recursion and caches results. In Python functools.lru_cache does it in one line:

from functools import lru_cache

@lru_cache(maxsize=None)
def ways(n):
    if n <= 2:
        return n
    return ways(n - 1) + ways(n - 2)

print(ways(45))

1836311903

It is the fastest way to write a DP: write the plain recursion, make sure its arguments are hashable, decorate it. Its limits are the recursion depth (a chain of 10,000 calls will overflow) and some overhead per call.

Bottom-up tabulation replaces the recursion with a loop that fills a table from the base cases upwards, so each value is ready before anything needs it:

def ways(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(ways(45))

1836311903

Once the table exists you often notice that only the last one or two entries are ever read, and you can shrink the memory to O(1) by keeping just those.

A reliable recipe for any DP:

1. State. What does dp[i] (or dp[i][j]) mean, in a sentence? "The fewest coins to make amount i." "The LCS length of the first i characters of A and the first j of B."
2. Recurrence. How is dp[i] computed from smaller states? This is where the thinking happens.
3. Base cases. What is known without any work? dp[0] = 0, an empty string matches nothing, and so on.
4. Order. Fill the table so that everything a cell depends on is already filled: increasing i, then increasing j.
5. Answer. Which cell holds the result? Usually the last one, but for "longest increasing subsequence" it is the maximum over the whole table.

1D example: coin change. State: dp[a] is the fewest coins making amount a. Recurrence: try every coin as the last one, dp[a] = 1 + min(dp[a - c]). Unreachable amounts need a sentinel that is bigger than any real answer.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 3, 4], 6), coin_change([2], 3))

2 -1

This is also the place to see greedy fail: taking the biggest coin first gives 4 + 1 + 1 for amount 6, three coins; the DP finds 3 + 3.

2D example: longest common subsequence. State: dp[i][j] is the LCS length of a[:i] and b[:j]. Padding the table with an extra row and column of zeros means the base cases (an empty prefix) need no special handling.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1          # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip a char from either
    return dp[m][n]

print(lcs("abcde", "ace"))

3

Edit distance uses the same table shape with three transitions instead of two (replace, delete, insert), and the base cases are dp[i][0] = i and dp[0][j] = j rather than zeros. If you can explain in words why each of those three transitions costs exactly one edit, you understand 2D DP.

Common mistakes: a state that does not capture enough information (the recurrence then needs something the table does not store). Off-by-one between "first i characters" and "index i": with the padded table, cell dp[i][j] looks at characters a[i-1] and b[j-1]. Initialising unreachable states to 0 instead of infinity, which makes them look like the best option. Building [[0] * n] * m (row aliasing, the same bug as the adjacency list).

Practice: Climbing Stairs, Coin Change, Longest Common Subsequence, Edit Distance

Backtracking

Backtracking is DFS over decisions instead of over nodes. You build a partial solution one choice at a time, recurse to complete it, and when you return you undo the choice so the same partial solution can be extended differently. The template is three lines that every backtracking solution shares:

def backtrack(state):
    if complete(state):
        record(copy of state)
        return
    for choice in choices(state):
        make(choice)          # choose
        backtrack(state)      # explore
        undo(choice)          # un-choose

Subsets is the purest instance: for each element, either it is in the subset or it is not. Using a start index guarantees each subset is generated exactly once, in increasing index order:

def subsets(nums):
    out, path = [], []
    def backtrack(start):
        out.append(path[:])            # every node of the tree is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            backtrack(i + 1)           # explore
            path.pop()                 # un-choose
    backtrack(0)
    return out

print(subsets([1, 2, 3]))

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Permutations use the same shape but the loop runs over all unused elements, with a used set (or list of booleans) instead of a start index. Combination sum lets you reuse an element by recursing with i instead of i + 1.

The power of backtracking comes from pruning: abandoning a partial solution the moment it can no longer lead to a valid one. N-Queens without pruning would try all n^n column choices; with a quick "is this square attacked?" check, the search for n = 8 explores only a few thousand boards. Keeping sets of used columns and diagonals makes that check O(1):

def total_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    count = 0
    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for c in range(n):
            if c in cols or row - c in d1 or row + c in d2:
                continue                                   # prune
            cols.add(c); d1.add(row - c); d2.add(row + c)
            backtrack(row + 1)
            cols.discard(c); d1.discard(row - c); d2.discard(row + c)
    backtrack(0)
    return count

print([total_n_queens(n) for n in range(1, 9)])

[1, 0, 0, 2, 10, 4, 40, 92]

Backtracking is exponential by nature. It is the right tool when the output itself is exponential (all subsets, all permutations) or when n is small (n <= 20 is the usual tell in the constraints). If n is in the thousands, the intended solution is something else, most often DP.

Common mistakes: out.append(path) instead of out.append(path[:]): every recorded solution is then the same list object and ends up empty after the final pop. Forgetting the un-choose step, so later branches inherit choices from earlier ones. Generating duplicates by restarting the loop at 0 instead of start.

Practice: Subsets, N-Queens Count

Greedy

A greedy algorithm makes the locally best choice at each step and never revisits it. When it works it is the simplest and fastest option; when it does not, it is simply wrong, and the failure is often silent because the answer looks reasonable. Coin change is the standard warning: "take the largest coin that fits" gives an optimal answer for [1, 5, 10, 25] and a wrong one for [1, 3, 4].

Greedy is safe when you can argue an exchange property: any optimal solution that disagrees with the greedy choice can be modified to agree with it without becoming worse. Prim and Kruskal are greedy algorithms with exactly such a proof (the cut property). Dijkstra is greedy too: settling the closest node is safe because no later path through a farther node can be shorter when weights are non-negative, and the argument breaks precisely when they are negative.

Jump Game is a good first greedy problem because the invariant is so simple: track the furthest index reachable so far. Every index at or before it is reachable; if the current index is beyond it, nothing past this point can ever be reached.

def can_jump(nums):
    furthest = 0
    for i, step in enumerate(nums):
        if i > furthest:
            return False
        furthest = max(furthest, i + step)
    return True

print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]))

True False

The DP version of the same problem asks, for every index, whether some earlier reachable index can jump to it, and is O(n^2). The greedy version is O(n) because the single number furthest already summarises everything the DP table would hold. That is the usual relationship: when a greedy algorithm exists it is a DP whose table has collapsed to one or two values.

A practical test before trusting a greedy idea: try to build a small counterexample for two minutes. If you cannot, and you can say in one sentence why the local choice never hurts, go ahead. If you find one, you need DP or search.

Common mistakes: assuming greedy works because it passes the examples. Sorting by the wrong key (in interval scheduling, sorting by start time instead of end time). Stopping early in Jump Game without checking that the last index is actually within reach.

Practice: Jump Game

Bit manipulation

Bit tricks are not a paradigm but they solve a few classic problems in O(1) space. Integers are sequences of bits; &, |, ^, ~, << and >> operate on them directly. The most useful identities: x ^ x == 0, x ^ 0 == x, and XOR is commutative, so XOR-ing a whole list cancels out every value that appears an even number of times.

nums = [4, 1, 2, 1, 2]
acc = 0
for x in nums:
    acc ^= x
print(acc)

4

Other handy one-liners: x & (x - 1) clears the lowest set bit (so x & (x - 1) == 0 tests for a power of two), x & 1 tests parity, and bin(x).count("1") counts set bits.

Practice: Single Number

Checklist

Before moving on, make sure you can do each of these without looking anything up:

• Convert an edge list to an adjacency list (directed, undirected, weighted) without the [[]] * n aliasing bug.
• Write BFS and DFS from memory with a seen set, and explain why nodes are marked when enqueued.
• Count BFS levels to get a shortest path length, and seed the queue with several sources.
• Treat a grid (or a set of words) as an implicit graph and generate neighbours on the fly with bounds checks.
• Count connected components and flood-fill regions.
• Run Kahn's algorithm to produce a topological order and detect a cycle by comparing the output length with n.
• Implement union-find with path compression and union by size, and use it to detect a cycle in an undirected graph.
• Write Dijkstra with heapq, (distance, node) tuples and the stale-entry skip; say why negative edges break it.
• State the cut property and implement either Kruskal or Prim.
• Given a DP problem, write down the state in one sentence, the recurrence, the base cases and the fill order before coding.
• Convert a memoized recursion into a bottom-up table and, when possible, shrink the table to O(1) space.
• Set up a padded 2D DP table for two strings and explain the match / skip / edit transitions.
• Write the choose / explore / un-choose template, copy path when recording, and add pruning.
• Explain when a greedy choice is safe and give a counterexample where it is not.
• Use XOR to find the element that appears an odd number of times.