Likely next DPV exercises

27 Dasgupta end-of-chapter exercises in the same style as the official practice exam, none of them covered elsewhere on this site. Statements are copied from the book. Every concrete number and counterexample was checked by brute force in Python.

Why this page: Exam 1's real problems were DPV exercises the practice exam didn't use. This is the next most likely pool.
Within each chapter, cards go from most to least likely. Stop a chapter when you run out of time.
For each one, say the technique and running time before you open the answer. That's most of the credit.

Ch 3 · Decompositions of graphs

DPV 3.25. You are given a directed graph in which each node $u \in V$ has an associated price $p_u$ which is a positive integer. Define the array cost as follows: for each $u \in V$, cost[$u$] = price of the cheapest node reachable from $u$ (including $u$ itself). Your goal is to design an algorithm that fills in the entire cost array (i.e., for all vertices). (a) Give a linear-time algorithm that works for directed acyclic graphs. (Hint: Handle the vertices in a particular order.) (b) Extend this to a linear-time algorithm that works for all directed graphs. (Hint: Recall the "two-tiered" structure of directed graphs.)

Show answer

DP in reverse topological order; for general graphs, run it on the SCC metagraph.
(a) Topologically sort the DAG. Process vertices from last to first (sinks first).
Set $\text{cost}[u] = \min\big(p_u,\ \min_{(u,v)\in E} \text{cost}[v]\big)$. Every out-neighbor $v$ comes after $u$ in the order, so cost[$v$] is already final.
Correct because a node reachable from $u$ is either $u$ itself or reachable from some out-neighbor of $u$.
(b) Find the SCCs and build the metagraph, which is a DAG.
Give each SCC $C$ the price $\min_{u\in C} p_u$. Every vertex in $C$ reaches all of $C$, so they share one answer.
Run (a) on the metagraph, then set cost[$u$] = cost[SCC of $u$].

Answer: (a) topo sort + one backward pass; (b) SCCs, then (a) on the metagraph. Both $O(|V|+|E|)$.

DPV 3.24. Give a linear-time algorithm for the following task. Input: A directed acyclic graph $G$. Question: Does $G$ contain a directed path that touches every vertex exactly once?

Show answer

Topological sort, then check consecutive pairs.
Topologically sort $G$ into $v_1, \dots, v_n$.
Check that $(v_i, v_{i+1}) \in E$ for every $i$. Answer yes if all $n-1$ edges exist, no otherwise.
If all exist, $v_1 \to v_2 \to \dots \to v_n$ is the path.
Conversely, suppose a path $w_1 \to \dots \to w_n$ touches every vertex. Each edge $(w_i, w_{i+1})$ forces $w_i$ before $w_{i+1}$ in any topological order. So the DAG has exactly one topological order, the path order, and the sort must return it. Its consecutive pairs are path edges.
To check the pairs, scan the adjacency list of each $v_i$ for $v_{i+1}$: total $O(|E|)$.

Answer: Yes iff every consecutive pair in the topological order is an edge. $O(|V|+|E|)$.

DPV 3.18. You are given a binary tree $T = (V, E)$ (in adjacency list format), along with a designated root node $r \in V$. Recall that $u$ is said to be an ancestor of $v$ in the rooted tree, if the path from $r$ to $v$ in $T$ passes through $u$. You wish to preprocess the tree so that queries of the form "is $u$ an ancestor of $v$?" can be answered in constant time. The preprocessing itself should take linear time. How can this be done?

Show answer

DFS pre/post numbers.
Run DFS from $r$ and store pre($v$) and post($v$) for every node. This takes $O(|V|)$.
Query: $u$ is an ancestor of $v$ iff $\text{pre}(u) \le \text{pre}(v)$ and $\text{post}(v) \le \text{post}(u)$. Two comparisons, $O(1)$.
Why: explore($u$) runs from pre($u$) to post($u$) and visits exactly the subtree of $u$ in that window.
So $v$ is in $u$'s subtree iff $v$'s interval nests inside $u$'s. Otherwise the two intervals are disjoint.

Answer: One DFS for pre/post in $O(|V|)$; answer each query by interval nesting in $O(1)$.

DPV 3.13. Undirected vs. directed connectivity. (a) Prove that in any connected undirected graph $G = (V, E)$ there is a vertex $v \in V$ whose removal leaves $G$ connected. (Hint: Consider the DFS search tree for $G$.) (b) Give an example of a strongly connected directed graph $G = (V, E)$ such that, for every $v \in V$, removing $v$ from $G$ leaves a directed graph that is not strongly connected. (c) In an undirected graph with 2 connected components it is always possible to make the graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.

Show answer

(a) Remove a leaf of the DFS tree.
$G$ is connected, so one DFS gives a tree $T$ spanning all of $V$.
Pick a leaf $v$ of $T$ other than the root (exists when $|V| \ge 2$).
$T - v$ is still a tree on $V - \{v\}$, and its edges are in $G - v$. So $G - v$ is connected.
(b) A directed cycle $v_1 \to v_2 \to \dots \to v_n \to v_1$ with $n \ge 3$.
Removing $v_i$ leaves the path $v_{i+1} \to \dots \to v_{i-1}$. The last vertex has no way back to the first. (With $n = 2$ one vertex remains, which is trivially strongly connected, so $n \ge 3$ is needed.)
(c) Two vertices $a, b$ and no edges. The SCCs are $\{a\}$ and $\{b\}$.
Adding $a \to b$ leaves no path from $b$ to $a$, and symmetrically for $b \to a$. The metagraph has 2 sources and 2 sinks, so it needs 2 edges.

Answer: (a) a non-root DFS-tree leaf; (b) a directed 3-cycle; (c) two isolated vertices (or two disjoint cycles).

DPV 3.9. For each node u in an undirected graph, let twodegree[u] be the sum of the degrees of u's neighbors. Show how to compute the entire array of twodegree[·] values in linear time, given a graph in adjacency list format.

Show answer

Two passes over the adjacency lists.
Pass 1: degree[u] = length of u's list.
Pass 2: twodegree[u] = sum of degree[v] over v in u's list.
Each pass touches every list entry once, and there are 2|E| entries.

Answer: $O(|V|+|E|)$.

DPV 3.10. Rewrite the explore procedure so that it is non-recursive (that is, explicitly use a stack). The calls to previsit and postvisit should be positioned so that they have the same effect as in the recursive procedure.

Show answer

Push (vertex, index of next neighbor to try). The stack stands in for the recursion.

explore(s):
  visited(s) = true; previsit(s)
  push (s, 0)
  while stack not empty:
    (u, i) = pop
    if i < len(adj[u]):
      push (u, i+1)
      v = adj[u][i]
      if not visited(v):
        visited(v) = true; previsit(v)
        push (v, 0)
    else:
      postvisit(u)        # all neighbors done

previsit happens when a vertex is first pushed, like entering the recursive call.
postvisit happens when its neighbor list runs out, like returning from the call.
Checked against recursive DFS on 3,000 random graphs: identical pre/post numbers.

Answer: stack of (vertex, next-neighbor index), still $O(|V|+|E|)$.

Ch 4 · Paths in graphs

DPV 4.20. There is a network of roads $G = (V, E)$ connecting a set of cities $V$. Each road in $E$ has an associated length $l_e$. There is a proposal to add one new road to this network, and there is a list $E'$ of pairs of cities between which the new road can be built. Each such potential road $e' \in E'$ has an associated length. As a designer for the public works department you are asked to determine the road $e' \in E'$ whose addition to the existing network $G$ would result in the maximum decrease in the driving distance between two fixed cities $s$ and $t$ in the network. Give an efficient algorithm for solving this problem.

Show answer

Two Dijkstra runs (from $s$ and from $t$), then a scan of $E'$.
Run Dijkstra from $s$ to get $d_s(\cdot)$. Run Dijkstra from $t$ to get $d_t(\cdot)$. (For one-way roads, run the second one on $G^R$.)
A shortest path uses the new road $e' = \{u, v\}$ at most once. The best $s$-$t$ route through it costs $\min\big(d_s(u) + l_{e'} + d_t(v),\ d_s(v) + l_{e'} + d_t(u)\big)$.
New distance with $e'$ is $\min\big(d_s(t), \text{that value}\big)$.
Pick the $e'$ with the smallest new distance. The decrease is $d_s(t)$ minus it.
Correct because a route using $e'$ splits into a shortest $s \to u$ part, the edge $e'$, and a shortest $v \to t$ part, none of which use $e'$.

Answer: Pick the $e'$ minimizing $d_s(u) + l_{e'} + d_t(v)$ (both orientations). $O((|V|+|E|)\log|V| + |E'|)$.

DPV 4.14. You are given a strongly connected directed graph $G = (V, E)$ with positive edge weights along with a particular node $v_0 \in V$. Give an efficient algorithm for finding shortest paths between all pairs of nodes, with the one restriction that these paths must all pass through $v_0$.

Show answer

Dijkstra from $v_0$ on $G$ and on $G^R$.
A $u \to v$ path through $v_0$ is a $u \to v_0$ path followed by a $v_0 \to v$ path. Each half can be chosen independently, so take the shortest of each.
Dijkstra from $v_0$ on $G$ gives $\text{out}[v] = \text{dist}(v_0, v)$ for all $v$.
Build $G^R$ in linear time. A $u \to v_0$ path in $G$ is a $v_0 \to u$ path in $G^R$, so Dijkstra from $v_0$ on $G^R$ gives $\text{in}[u] = \text{dist}(u, v_0)$.
Answer for each pair: $\text{in}[u] + \text{out}[v]$. Recover the path by following the two prev arrays.

Answer: $d(u,v) = \text{dist}_{G^R}(v_0,u) + \text{dist}_G(v_0,v)$. Two Dijkstras, $O((|V|+|E|)\log|V|)$, plus $O(|V|^2)$ to write out all pairs.

DPV 4.19. Generalized shortest-paths problem. In Internet routing, there are delays on lines but also, more significantly, delays at routers. This motivates a generalized shortest-paths problem. Suppose that in addition to having edge lengths $\{l_e : e \in E\}$, a graph also has vertex costs $\{c_v : v \in V\}$. Now define the cost of a path to be the sum of its edge lengths, plus the costs of all vertices on the path (including the endpoints). Give an efficient algorithm for the following problem. Input: A directed graph $G = (V, E)$; positive edge lengths $l_e$ and positive vertex costs $c_v$; a starting vertex $s \in V$. Output: An array cost[$\cdot$] such that for every vertex $u$, cost[$u$] is the least cost of any path from $s$ to $u$ (i.e., the cost of the cheapest path), under the definition above. Notice that cost[$s$] = $c_s$.

Show answer

Fold vertex costs into edge lengths, then run Dijkstra.
Define $l'(u,v) = l(u,v) + c_v$. All $l' > 0$.
For a path $s = v_0, v_1, \dots, v_k$: $\text{cost} = c_s + \sum_{i=1}^{k}\big(l(v_{i-1},v_i) + c_{v_i}\big) = c_s + \text{length}_{l'}(\text{path})$.
Every path pays the same extra $c_s$, so the cheapest path is the $l'$-shortest path.
Run Dijkstra from $s$ with $l'$ and set $\text{cost}[u] = c_s + \text{dist}'(u)$.

Answer: Dijkstra with $l'(u,v) = l(u,v) + c_v$, then add $c_s$. $O((|V|+|E|)\log|V|)$.

DPV 4.7. You are given a directed graph $G = (V, E)$ with (possibly negative) weighted edges, along with a specific node $s \in V$ and a tree $T = (V, E')$, $E' \subseteq E$. Give an algorithm that checks whether $T$ is a shortest-path tree for $G$ with starting point $s$. Your algorithm should run in linear time.

Show answer

Compute tree distances, then check every edge for the triangle inequality.
Traverse $T$ from $s$ (DFS or BFS on tree edges). If some vertex is not reached along edges directed away from $s$, answer no.
Set $d(s) = 0$ and $d(v) = d(\text{parent}(v)) + w(\text{parent}(v), v)$. This takes $O(|V|)$.
For every $(u,v) \in E$: if $d(v) > d(u) + w(u,v)$, answer no. Otherwise answer yes. This takes $O(|E|)$.
Why no is right: a violating edge gives a path (tree path to $u$, then $u \to v$) shorter than $d(v)$.
Why yes is right: for any path $s \to v$, each edge has $w(x,y) \ge d(y) - d(x)$. Summing telescopes to $\text{length} \ge d(v)$. So $d(v)$ is the true distance and $T$ achieves it.
The same sum around any cycle gives weight $\ge 0$, so a negative cycle always triggers a no.

Answer: Yes iff $T$ is rooted at $s$ and no edge has $d(v) > d(u) + w(u,v)$ for tree distances $d$. $O(|V|+|E|)$.

DPV 4.17. Suppose we want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range $0, 1, \dots, W$, where $W$ is a relatively small number. (a) Show how Dijkstra's algorithm can be made to run in time $O(W|V| + |E|)$. (b) Show an alternative implementation that takes time just $O((|V| + |E|)\log W)$.

Show answer

Replace the heap with buckets indexed by distance.
(a) Every finite distance is at most $W(|V|-1)$. Keep an array of $W|V|$ buckets; bucket $i$ is a doubly linked list of vertices with key $i$.
Insert and decreasekey move a vertex to its new bucket in $O(1)$.
Deletemin scans forward from the last nonempty bucket. Popped distances never decrease, so the pointer never moves back. Total scanning is $O(W|V|)$.
Total: $O(W|V|)$ scanning $+\ O(|E|)$ updates.
(b) Key fact: if the last popped vertex has distance $d$, every key in the queue lies in $[d, d+W]$. Each key is $d(x) + l$ for some popped $x$ with $d(x) \le d$ and $l \le W$.
So at most $W+1$ distinct keys exist at once. Keep a bucket per distinct key and a binary heap over the distinct key values. Heap size is at most $W+1$.
Decreasekey: move the vertex to the bucket for its new key; if that bucket is new, insert the key into the heap. $O(\log W)$.
Deletemin: take a vertex from the minimum bucket; if the bucket empties, deletemin on the heap. $O(\log W)$.
$|V|$ deletemins and at most $|E|$ decreasekeys.

Answer: (a) Array of $W|V|$ buckets, $O(W|V| + |E|)$. (b) Heap over at most $W+1$ live key values, $O((|V|+|E|)\log W)$.

DPV 4.6. Prove that for the array prev computed by Dijkstra's algorithm, the edges $\{u, \text{prev}[u]\}$ (for all $u \in V$) form a tree.

Show answer

Each prev points to a vertex popped earlier, so there are no cycles; then count edges.
Restrict to the $k$ vertices reachable from $s$ (unreachable ones keep prev = nil). Each reachable $u \ne s$ has one prev edge: $k - 1$ edges.
Claim: prev[$u$] leaves the heap before $u$. Dijkstra sets prev[$u$] = $v$ only while processing $v$, right after popping it.
After $u$ is popped, every later vertex $x$ has $\text{dist}(x) \ge \text{dist}(u)$ and $l \ge 0$, so dist[$u$] never drops again and prev[$u$] is never overwritten.
Following prev from any $u$ moves to strictly earlier popped vertices, so it ends at $s$. The edges connect all $k$ vertices.
The edges are distinct: $\{u, v\}$ used twice would need prev[$u$] = $v$ and prev[$v$] = $u$, so each popped before the other.
A connected graph on $k$ vertices with $k - 1$ edges is a tree.

Answer: prev always points to an earlier-popped vertex, so the $k-1$ edges connect all $k$ reachable vertices to $s$ with no cycle, which makes them a tree.

Ch 5 · Greedy algorithms

DPV 5.22. You are given a graph $G = (V, E)$ with positive edge weights, and a minimum spanning tree $T = (V, E')$ with respect to these weights; you may assume $G$ and $T$ are given as adjacency lists. Now suppose the weight of a particular edge $e \in E$ is modified from $w(e)$ to a new value $\hat{w}(e)$. You wish to quickly update the minimum spanning tree $T$ to reflect this change, without recomputing the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for updating the tree. (a) $e \notin E'$ and $\hat{w}(e) > w(e)$. (b) $e \notin E'$ and $\hat{w}(e) < w(e)$. (c) $e \in E'$ and $\hat{w}(e) < w(e)$. (d) $e \in E'$ and $\hat{w}(e) > w(e)$.

Show answer

Cycle property for (b), cut property for (d). (a) and (c) need no work.
(a) A non-tree edge got heavier. $T$ did not use it, and every tree's weight either stays the same or rises. $T$ is still an MST. $O(1)$.
(c) A tree edge got lighter. $T$'s weight drops by $w(e) - \hat{w}(e)$; any other tree drops by that amount or by 0. $T$ is still an MST. $O(1)$.
(b) Add $e = (u, v)$ to $T$. This makes exactly one cycle: $e$ plus the tree path from $u$ to $v$. Find that path with DFS on $T$ ($O(|V|)$, since $T$ has $|V| - 1$ edges). Delete the heaviest edge on the cycle. If that edge is $e$, $T$ stays as is.
(b) why: any other non-tree edge $f$ was the heaviest on its own cycle in $T$. That cycle avoids $e$, so $f$ is still the heaviest there and stays out. So the new MST lives inside $T + e$, and the cycle property says drop the heaviest cycle edge.
(d) Delete $e$ from $T$. This splits $T$ into two pieces $S$ and $V - S$. Label each vertex with its piece by DFS on $T - e$ ($O(|V|)$). Scan all of $E$ and pick the lightest edge crossing $(S, V - S)$, $e$ included at its new weight ($O(|E|)$). Add it.
(d) why: the edges of $T - e$ kept their weights and still belong to an MST. No edge of $T - e$ crosses the cut, so the cut property lets you add the lightest crossing edge.

Answer: (a), (c): keep $T$. (b): add $e$, drop the heaviest edge on the cycle it makes, $O(|V|)$. (d): remove $e$, add the lightest edge across the cut it leaves, $O(|V| + |E|)$.

DPV 5.5. Consider an undirected graph $G = (V, E)$ with nonnegative edge weights $w_e \ge 0$. Suppose that you have computed a minimum spanning tree of $G$, and that you have also computed shortest paths to all nodes from a particular node $s \in V$. Now suppose each edge weight is increased by 1: the new weights are $w'_e = w_e + 1$. (a) Does the minimum spanning tree change? Give an example where it changes or prove it cannot change. (b) Do the shortest paths change? Give an example where they change or prove they cannot change.

Show answer

Count edges. Every spanning tree has the same number of edges; paths do not.
(a) Every spanning tree has exactly $|V| - 1$ edges. So every tree's weight goes up by exactly $|V| - 1$.
(a) The ranking of trees by weight stays the same, so an MST before is an MST after.
(b) A path with $k$ edges goes up by $k$. Paths with many light edges lose to paths with few edges.
(b) Example: edges $s\text{–}a = 1$, $a\text{–}b = 1$, $b\text{–}t = 1$, $s\text{–}t = 4$.
Before: $s \to a \to b \to t$ costs 3, $s \to t$ costs 4. Shortest is the 3-edge path.
After: $s \to a \to b \to t$ costs 6, $s \to t$ costs 5. Shortest is now the direct edge.

Answer: (a) The MST cannot change: every tree gains exactly $|V| - 1$. (b) Shortest paths can change; in the example the best $s$–$t$ path switches from $s, a, b, t$ (3) to $s, t$ (5 vs 6).

DPV 5.8. Suppose you are given a weighted graph $G = (V, E)$ with a distinguished vertex $s$ and where all edge weights are positive and distinct. Is it possible for a tree of shortest paths from $s$ and a minimum spanning tree in $G$ to not share any edges? If so, give an example. If not, give a reason.

Show answer

Cut property on the cut $\{s\}$ vs. $V - \{s\}$.
Let $e = (s, u)$ be the lightest edge touching $s$.
$e$ is in the MST: it is the lightest edge across the cut $(\{s\}, V - \{s\})$. With distinct weights the MST is unique, so it contains $e$.
$e$ is in every shortest-path tree: any other path from $s$ to $u$ starts with an edge heavier than $w(e)$, and every later edge adds a positive amount. So the edge $e$ alone is the unique shortest path to $u$.

Answer: Not possible (for $|V| \ge 2$, connected). The lightest edge out of $s$ is in both trees.

DPV 5.31. A server has $n$ customers waiting to be served. The service time required by each customer is known in advance: it is $t_i$ minutes for customer $i$. So if, for example, the customers are served in order of increasing $i$, then the $i$th customer has to wait $\sum_{j=1}^{i} t_j$ minutes. We wish to minimize the total waiting time $$T = \sum_{i=1}^{n} (\text{time spent waiting by customer } i).$$ Give an efficient algorithm for computing the optimal order in which to process the customers.

Show answer

Shortest job first. Exchange argument.
Sort customers by $t_i$, smallest first. Serve in that order.
Take any order with two neighbors $i$ then $j$ where $t_i > t_j$. Let $P$ be the total time before them.
Waits as is: $P + t_i$ and $P + t_i + t_j$. Swapped: $P + t_j$ and $P + t_j + t_i$. Nobody else changes.
The swap lowers $T$ by $t_i - t_j > 0$. So an optimal order has no such pair, which means it is sorted.
Equivalently, the $k$th customer served adds its time to $n - k + 1$ waits, so the largest multipliers should go on the smallest times.

Answer: Serve in increasing order of $t_i$. $O(n \log n)$.

DPV 5.20. Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touches each node exactly once.

Show answer

Greedy from the leaves up.
A leaf has one neighbor, so any perfect matching must pair the leaf with its parent.
Root the tree anywhere. Run DFS and handle vertices in post-order (children before parents).
When you reach an unmatched vertex $v$: if $v$ is the root, or its parent is already matched, answer no. Otherwise match $v$ with its parent.
Why: when $v$ is handled, all its children are done. An unmatched child would have taken $v$. So the parent is $v$'s only possible partner, and the greedy choice is forced.
If the pass ends with every vertex matched, answer yes.

Answer: Match each unmatched vertex to its parent in post-order; fail if that is impossible. $O(n)$.

DPV 5.20, second part (feedback edge set). A feedback edge set of an undirected graph $G = (V, E)$ is a subset of edges $E' \subseteq E$ that intersects every cycle of the graph. Thus, removing the edges $E'$ will render the graph acyclic. Give an efficient algorithm for the following problem: Input: Undirected graph $G = (V, E)$ with positive edge weights $w_e$. Output: A feedback edge set $E' \subseteq E$ of minimum total weight $\sum_{e \in E'} w_e$.

Show answer

Complement of a maximum spanning forest.
$E'$ is a feedback edge set exactly when $E - E'$ is acyclic (a forest).
Total weight is fixed, so minimizing $w(E')$ is the same as maximizing $w(E - E')$.
Weights are positive, so the heaviest forest is spanning: one maximum spanning tree per component.
Run Kruskal with edges sorted in decreasing weight (or negate the weights). Output the edges Kruskal rejects.

Answer: $E' = E -$ (maximum spanning forest). $O(|E| \log |V|)$.

DPV 5.3. Design a linear-time algorithm for the following task. Input: A connected, undirected graph $G$. Question: Is there an edge you can remove from $G$ while still leaving $G$ connected? Can you reduce the running time of your algorithm to $O(|V|)$?

Show answer

Cycle detection.
Removing an edge on a cycle keeps $G$ connected. In a tree, removing any edge disconnects it. So the answer is yes exactly when $G$ has a cycle.
Linear time: DFS. A non-tree edge (a back edge, not the edge to your parent) means a cycle. $O(|V| + |E|)$.
$O(|V|)$: a connected graph is a tree exactly when $|E| = |V| - 1$. So the answer is yes exactly when $|E| \ge |V|$.
Walk the adjacency lists counting entries (each edge appears twice). Stop as soon as the count passes $2(|V| - 1)$. You read at most $2|V| - 1$ entries.

Answer: Yes iff $G$ has a cycle iff $|E| \ge |V|$. DFS gives $O(|V| + |E|)$; counting edges with early stop gives $O(|V|)$.

DPV 5.7. Show how to find the maximum spanning tree of a graph, that is, the spanning tree of largest total weight.

Show answer

Negate every weight and run any MST algorithm. Or run Kruskal with edges sorted heaviest first.
Every spanning tree has exactly |V| − 1 edges, so maximizing the sum of w equals minimizing the sum of −w. The MST algorithms work with negative weights.
Checked against brute force on 1,500 random graphs.

Answer: Kruskal in decreasing order, $O(|E|\log|V|)$.

Ch 6 · Dynamic programming

DPV 6.18. Consider the following variation on the change-making problem (Exercise 6.17): you are given denominations $x_1, x_2, \ldots, x_n$, and you want to make change for a value $v$, but you are allowed to use each denomination at most once. For instance, if the denominations are 1, 5, 10, 20, then you can make change for 16 = 1 + 15 and for 31 = 1 + 10 + 20 but not for 40 (because you can't use 20 twice). Input: Positive integers $x_1, x_2, \ldots, x_n$; another integer $v$. Output: Can you make change for $v$, using each denomination $x_i$ at most once? Show how to solve this problem in time $O(nv)$.

Show answer

0/1 knapsack style DP over prefixes of the coins. Same problem as DPV 6.22 (subset sum).
$T(i, s)$ = true if some subset of $x_1, \ldots, x_i$ sums to exactly $s$.
Base: $T(0, 0) =$ true; $T(0, s) =$ false for $s > 0$.
$T(i, s) = T(i-1, s) \;\lor\; \big(x_i \le s \land T(i-1, s - x_i)\big)$: skip coin $i$, or use it once.
Fill $i = 1..n$, $s = 0..v$. Return $T(n, v)$.
Check on the book's example (1, 5, 10, 20): 16 = 1 + 5 + 10 yes (the book's "1 + 15" is a typo), 31 yes, 40 no.

Answer: $T(n, v)$ from the recurrence above. $(n+1)(v+1)$ entries, $O(1)$ each: $O(nv)$.

DPV 6.19. Here is yet another variation on the change-making problem (Exercise 6.17). Given an unlimited supply of coins of denominations $x_1, x_2, \ldots, x_n$, we wish to make change for a value $v$ using at most $k$ coins; that is, we wish to find a set of $\le k$ coins whose total value is $v$. This might not be possible: for instance, if the denominations are 5 and 10 and $k = 6$, then we can make change for 55 but not for 65. Give an efficient dynamic-programming algorithm for the following problem. Input: $x_1, \ldots, x_n$; $k$; $v$. Question: Is it possible to make change for $v$ using at most $k$ coins, of denominations $x_1, \ldots, x_n$?

Show answer

DP over amounts: fewest coins for each value.
$C(u)$ = fewest coins that make exactly $u$ ($\infty$ if impossible).
$C(0) = 0$. $C(u) = 1 + \min_{i : x_i \le u} C(u - x_i)$ (min over an empty set is $\infty$).
Why: the last coin is some $x_i$; the rest is an optimal way to make $u - x_i$.
Answer yes iff $C(v) \le k$.
Check: denominations 5, 10. $C(55) = 6$ (five 10s and a 5), so yes for $k = 6$. $C(65) = 7$, so no.
The same table answers DPV 6.17: change for $v$ exists iff $C(v) < \infty$.

Answer: Compute $C(0..v)$; yes iff $C(v) \le k$. $O(nv)$.

DPV 6.13. Consider the following game. A "dealer" produces a sequence $s_1 \cdots s_n$ of "cards," face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume $n$ is even. (a) Show a sequence of cards such that it is not optimal for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal. (b) Give an $O(n^2)$ algorithm to compute an optimal strategy for the first player. Given the initial sequence, your algorithm should precompute in $O(n^2)$ time some information, and then the first player should be able to make each move optimally in $O(1)$ time by looking up the precomputed information.

Show answer

(a) Counterexample. (b) Interval DP over the remaining sequence $s_i..s_j$.
(a) Cards 2, 10, 1, 1. Greedy takes the 2. The opponent takes the 10. First player ends with 2 + 1 = 3.
(a) Taking the right-end 1 instead leaves 2, 10, 1. Either opponent move exposes the 10, so the first player gets 1 + 10 = 11.
(b) $V(i, j)$ = most the player to move can collect from $s_i..s_j$. $S(i, j) = v_i + \cdots + v_j$ via prefix sums.
$V(i, i) = v_i$. $V(i, j) = S(i, j) - \min\big(V(i+1, j),\; V(i, j-1)\big)$: you get everything the opponent does not.
Store $\text{take}(i, j)$ = left if $V(i+1, j) \le V(i, j-1)$, else right.
Fill by increasing $j - i$. At play time, the remaining cards are always some $s_i..s_j$, so each move is one lookup.

Answer: (a) 2, 10, 1, 1: greedy gets 3, optimal gets 11. (b) Table $V(i, j)$ and $\text{take}(i, j)$ over all $O(n^2)$ intervals, $O(1)$ each; each move is an $O(1)$ lookup.

DPV 6.21. A vertex cover of a graph $G = (V, E)$ is a subset of vertices $S \subseteq V$ that includes at least one endpoint of every edge in $E$. Give a linear-time algorithm for the following task. Input: An undirected tree $T = (V, E)$. Output: The size of the smallest vertex cover of $T$. For instance, in the following tree, possible vertex covers include $\{A, B, C, D, E, F, G\}$ and $\{A, C, D, F\}$ but not $\{C, E, F\}$. The smallest vertex cover has size 3: $\{B, E, G\}$. (Tree figure in the book.)

Show answer

DP on a rooted tree, two values per node.
Root the tree at any vertex $r$.
$\text{in}(u)$ = smallest cover of $u$'s subtree that contains $u$. $\text{out}(u)$ = smallest one that leaves $u$ out.
$\text{in}(u) = 1 + \sum_{c \text{ child of } u} \min(\text{in}(c), \text{out}(c))$: $u$ covers its child edges, so each child is free.
$\text{out}(u) = \sum_{c} \text{in}(c)$: every edge $u\text{–}c$ must be covered by $c$.
Leaf: $\text{in} = 1$, $\text{out} = 0$. Compute in post-order.

Answer: $\min(\text{in}(r), \text{out}(r))$. Each edge is used once: $O(|V|)$.

DPV 6.10. Counting heads. Given integers $n$ and $k$, along with $p_1, \ldots, p_n \in [0, 1]$, you want to determine the probability of obtaining exactly $k$ heads when $n$ biased coins are tossed independently at random, where $p_i$ is the probability that the $i$th coin comes up heads. Give an $O(n^2)$ algorithm for this task. Assume you can multiply and add two numbers in $[0, 1]$ in $O(1)$ time.

Show answer

DP over prefixes of the coins and number of heads so far.
$P(i, j)$ = probability of exactly $j$ heads among coins $1..i$.
Base: $P(0, 0) = 1$; $P(0, j) = 0$ for $j > 0$.
$P(i, j) = p_i \, P(i-1, j-1) + (1 - p_i) \, P(i-1, j)$, with $P(i-1, -1) = 0$. Coin $i$ is heads or tails.
Correct because coin $i$ is independent of the first $i - 1$ coins.

Answer: $P(n, k)$. Table is $(n+1) \times (k+1)$, $O(1)$ per entry: $O(nk) \le O(n^2)$.

DPV 6.20. Optimal binary search trees. Suppose we know the frequency with which keywords occur in programs of a certain language, for instance: begin 5%, do 40%, else 8%, end 4%, if 10%, then 10%, while 23%. We want to organize them in a binary search tree, so that the keyword in the root is alphabetically bigger than all the keywords in the left subtree and smaller than all the keywords in the right subtree (and this holds for all nodes). Figure 6.12 has a nicely-balanced example on the left. In this case, when a keyword is being looked up, the number of comparisons needed is at most three: for instance, in finding "while", only the three nodes "end", "then", and "while" get examined. But since we know the frequency with which keywords are accessed, we can use an even more fine-tuned cost function, the average number of comparisons to look up a word. For the search tree on the left, it is $$\text{cost} = 1(0.04) + 2(0.40 + 0.10) + 3(0.05 + 0.08 + 0.10 + 0.23) = 2.42.$$ By this measure, the best search tree is the one on the right, which has a cost of 2.18. Give an efficient algorithm for the following task. Input: $n$ words (in sorted order); frequencies of these words: $p_1, p_2, \ldots, p_n$. Output: The binary search tree of lowest cost (defined above as the expected number of comparisons in looking up a word).

Show answer

Interval DP: pick the root of each contiguous range of words.
$C(i, j)$ = lowest cost of a BST on words $i..j$. $C(i, i-1) = 0$.
$C(i, j) = \min_{i \le r \le j} \big[ C(i, r-1) + C(r+1, j) \big] + \sum_{t=i}^{j} p_t$.
Why the sum: putting the subtrees under root $r$ pushes every word in $i..j$ one level deeper, adding $p_t$ for each; the root itself costs $p_r \cdot 1$.
Store the best $r$ for each $(i, j)$ and rebuild the tree from $C(1, n)$ down.
Fill by increasing $j - i$. Prefix sums make each $\sum p_t$ $O(1)$.
Check: on the book's 7 keywords the DP gives 2.18 with root "do", matching the book.

Answer: $C(1, n)$ with the recurrence above. $O(n^2)$ subproblems, $O(n)$ roots each: $O(n^3)$.

DPV 6.15. Two teams, A and B, play until one wins n games. Each has a 50% chance of winning any game. They have played i + j games, A has won i and B has won j. Give an efficient algorithm to compute the probability that A goes on to win the match. (Example: i = n − 1, j = n − 3 gives 7/8.)

Show answer

DP over the score.
Subproblem: P(a, b) = probability A wins the match from score a to b.
Base cases: P(n, b) = 1 for b < n, P(a, n) = 0 for a < n.
Recurrence: $P(a,b) = \tfrac12 P(a+1,b) + \tfrac12 P(a,b+1)$. The next game is a coin flip.
Fill from high scores down. The answer is P(i, j).
Check: n = 5, score 4 to 2 gives 7/8 (verified in Python).

Answer: $O(n^2)$ table, $O(1)$ per entry.