Unit 5: More on Dynamic Programming

I. Dynamic Programming Foundations

Dynamic programming is an algorithm-design technique for problems whose solutions can be built from solutions to smaller, overlapping subproblems. Introduced systematically by Richard Bellman in the 1950s, it replaces repeated computation with stored results and is especially effective when an optimization problem has a recursive structure.

• Optimal substructure: An optimal solution contains optimal solutions to relevant subproblems. A shortest path from vertex (i) to vertex (j) through (k), for example, combines shortest paths (i\to k) and (k\to j).
• Overlapping subproblems: The same smaller instances recur. Dynamic programming computes each state once rather than expanding an exponential recursion tree.
• State definition: A state records the minimum information needed to describe a subproblem, such as permitted intermediate vertices in a path or an interval of keys in a search tree.
• Recurrence relation: Each state is expressed using previously solved states. Correctness depends on considering every valid final choice, such as including a vertex or selecting a root.
• Base cases: Smallest subproblems are assigned direct values. Examples include a zero-length path from a vertex to itself and an empty interval in a binary search tree.
• Evaluation order: States must be computed only after their dependencies:
  • Bottom-up tabulation: Fills a table in dependency order.
  • Top-down memoization: Uses recursion and stores states when first evaluated.
• Reconstruction information: An auxiliary table can retain decisions—not merely objective values—so that an actual shortest path or optimal tree can be recovered.
• Complexity principle: Running time is approximately the number of states multiplied by the work per state. Memory use is determined by the number and size of stored states.

II. All-Pairs Shortest Paths — Minimum Distances Between Every Vertex Pair

A. All-pairs shortest paths

The all-pairs shortest-path problem computes the minimum path cost between every ordered pair of vertices in a weighted graph.

• Input model: Let (G=(V,E)) be a directed or undirected graph with (n=|V|) vertices. Each edge ((i,j)\in E) has weight (w(i,j)), representing quantities such as distance, time, or cost.
• Required output: An (n\times n) matrix (D), where (D[i][j]) is the weight of a shortest path from (i) to (j). If (j) is unreachable from (i), the entry is (\infty).
• Floyd–Warshall principle: The algorithm gradually enlarges the set of vertices permitted as internal vertices of a path. At stage (k), it decides whether a shortest (i\to j) path should avoid vertex (k) or pass through it.
• State definition: Let (D^{(k)}[i][j]) denote the shortest-path weight from (i) to (j) whose internal vertices belong only to ({1,\ldots,k}).
• Base case: Before any internal vertex is permitted,

D^(0)[i][j] = 0         if i = j
D^(0)[i][j] = w(i,j)    if (i,j) is an edge
D^(0)[i][j] = ∞         otherwise

Here, (i) and (j) are endpoint vertices, (w(i,j)) is the direct-edge weight, and (\infty) denotes that no allowed path exists.

• Recurrence: Every permitted path either excludes (k) internally or uses (k), in which case it decomposes into (i\to k) and (k\to j):

D^(k)[i][j] =
    min(D^(k-1)[i][j],
        D^(k-1)[i][k] + D^(k-1)[k][j])

The first term represents avoiding (k); the second represents passing through (k).

• Bottom-up algorithm: A single matrix can be updated in place because stage (k) requires no value from a later stage.

FLOYD-WARSHALL(W, n)
    D ← W
    for k ← 1 to n
        for i ← 1 to n
            for j ← 1 to n
                D[i][j] ← min(D[i][j], D[i][k] + D[k][j])
    return D

(W) is the initialized weight matrix, (n) is the number of vertices, and (D) is the resulting distance matrix.

• Correctness invariant: After iteration (k), every entry (D[i][j]) is the shortest path whose internal vertices are drawn from ({1,\ldots,k}). After (k=n), all vertices are permitted, so every entry is globally optimal.
• Worked example: Consider edges (1\to2=4), (1\to3=11), (2\to3=2), and (3\to1=3). Initially, the direct distance (D[1][3]) is (11). When vertex (2) becomes available, the recurrence finds

D[1][3] = min(11, D[1][2] + D[2][3])
        = min(11, 4 + 2)
        = 6

The resulting distance matrix is

      to 1  2  3
from 1   0  4  6
from 2   5  0  2
from 3   3  7  0

For example, the shortest path (2\to1) is (2\to3\to1), with cost (2+3=5).

• Path reconstruction: Maintain a matrix next, where next[i][j] stores the first vertex visited after (i) on the current shortest (i\to j) path. Whenever routing through (k) improves (D[i][j]), assign next[i][j] ← next[i][k]; repeatedly following these entries reconstructs the path.
• Negative edges: Floyd–Warshall permits negative edge weights because it does not assume that extending a path increases its cost.
• Negative cycles: A reachable negative-weight cycle makes shortest-path values undefined because traversing the cycle repeatedly decreases the cost without bound. After completion, (D[v][v]<0) identifies that vertex (v) lies on, or can return through, such a cycle.
• Complexity: The three nested loops perform (\Theta(n^3)) updates, while the distance matrix requires (\Theta(n^2)) space. A reconstruction matrix adds another (\Theta(n^2)).

B. Applications and limitations

All-pairs shortest paths are most useful when distances among many different source–destination pairs are required.

• Applications: Network routing, transportation analysis, dependency-cost evaluation, and transitive-closure computation all naturally require pairwise information. For Boolean reachability, replacing min and addition with logical OR and AND yields Warshall’s transitive-closure algorithm.
• Dense graphs: The (\Theta(n^3)) bound is often acceptable when the graph has (\Theta(n^2)) edges because many pairwise relationships must already be examined.
• Sparse graphs: Repeated Dijkstra computations can be preferable when weights are nonnegative; Johnson’s algorithm supports sparse graphs with negative edges but no negative cycles.
• Memory limitation: Storing all pairwise distances necessarily consumes (\Theta(n^2)) output space, which can be prohibitive for very large (n).
• Model limitation: Static Floyd–Warshall recomputes the table when edge weights change; it is not inherently an efficient dynamic-update algorithm.

III. Optimal Binary Search Trees — Minimizing Expected Search Cost

A. Optimal binary search trees

An optimal binary search tree arranges ordered keys to minimize expected search cost when different successful and unsuccessful searches have different probabilities.

• Input model: Let ordered keys satisfy (k_1<k_2<\cdots<k_n). Successful search probability (p_i) belongs to key (k_i), while (q_i) is the probability of an unsuccessful search in dummy interval (d_i).
  • (d_0) represents values below (k_1).
  • (d_i), for (1\le i<n), represents values between (ki) and (k{i+1}).
  • (d_n) represents values above (k_n).
• Probability condition: The complete search distribution satisfies

Σ(i=1 to n) p_i + Σ(i=0 to n) q_i = 1

Here, (p_i\ge0) and (q_i\ge0).

• Objective: If the root is examined at level (1), the expected number of comparisons is the probability-weighted sum of the levels of successful and unsuccessful search terminals. Frequently accessed keys should generally occur nearer the root, but ordering constraints prevent simply sorting keys by probability.
• State definition: Let (e[i][j]) be the minimum expected cost of a subtree containing keys (k_i,\ldots,k_j). Let (w[i][j]) be the total probability associated with that interval:

w[i][j] = Σ(l=i to j) p_l + Σ(l=i-1 to j) q_l

The symbol (l) is a summation index; (w[i][j]) includes successful searches for interval keys and unsuccessful searches surrounding them.

• Base case: An empty subtree between (k_{i-1}) and (ki) contains only dummy key (d{i-1}):

e[i][i-1] = q_(i-1)
w[i][i-1] = q_(i-1)

• Recurrence: If (k_r) is selected as root of interval ([i,j]), keys before it form the left subtree and keys after it form the right subtree:

e[i][j] =
    min over i ≤ r ≤ j of
    (e[i][r-1] + e[r+1][j] + w[i][j])

The term (w[i][j]) is added because attaching both subtrees below a new root increases the depth, and therefore expected comparison cost, of every search outcome in the interval by one.

• Evaluation order: Intervals are processed by increasing length. Thus, when computing ([i,j]), both ([i,r-1]) and ([r+1,j]) have already been solved.

for i ← 1 to n + 1
    e[i][i-1] ← q[i-1]
    w[i][i-1] ← q[i-1]

for length ← 1 to n
    for i ← 1 to n - length + 1
        j ← i + length - 1
        e[i][j] ← ∞
        w[i][j] ← w[i][j-1] + p[j] + q[j]
        for r ← i to j
            cost ← e[i][r-1] + e[r+1][j] + w[i][j]
            if cost < e[i][j]
                e[i][j] ← cost
                root[i][j] ← r

root[i][j] records the index (r) chosen as the root of the optimal interval tree.

• Worked example: For two keys, let (p_1=0.30), (p_2=0.20), (q_0=0.10), (q_1=0.10), and (q_2=0.30). The total probability is (1), and (w[1][2]=1).

  1. Choose (k_1) as root: The recurrence gives (e[1][0]+e[2][2]+1=0.10+0.90+1=2.00).
  2. Choose (k_2) as root: It gives (e[1][1]+e[3][2]+1=0.80+0.30+1=2.10).

  Therefore, (k_1) is the optimal root and the minimum expected search cost is (2.00) comparisons.

• Reconstruction: Begin with root[1][n]; recursively construct its left interval ([i,r-1]) and right interval ([r+1,j]). Empty intervals become dummy leaves.

• Complexity: There are (\Theta(n^2)) intervals and up to (\Theta(n)) candidate roots per interval, producing (\Theta(n^3)) time and (\Theta(n^2)) space.

B. Applications and limitations

Optimal binary search trees turn known access frequencies into a static search structure with minimum expected comparison cost.

• Applications: They suit static dictionaries, compiler symbol tables, command lookup, and read-heavy indexes when key probabilities can be estimated reliably.
• Greedy limitation: Selecting the highest-probability key as root is not generally optimal because the decision also constrains the left and right ordered subtrees.
• Statistical limitation: If access probabilities change substantially, the computed tree may cease to be optimal and must be rebuilt.
• Operational limitation: The classical model optimizes comparisons, not cache behavior, rotations, update cost, or storage-page access.
• Improved bound: Under the standard recurrence’s monotonic-root property, Knuth’s optimization restricts candidate roots and reduces construction time from (\Theta(n^3)) to (\Theta(n^2)), while retaining (\Theta(n^2)) storage.