3. Greedy Algorithms#

These problems require greedy strategies with proofs of optimality via exchange arguments or greedy-stays-ahead.

3.1. The input is an array $A$ of $n$ distinct, positive integers. Each integer is the processing time of a job. For any ordering of the jobs, the waiting time of job $j$ is the sum of processing times of jobs before $j$ in the ordering. Our goal is return an ordering of the jobs such that the sum of waiting times is minimized. Describe an $O(n\log n)$-time algorithm for this problem, explain why it’s correct, and analyze its running time.

Example: If $A = [5, 1, 2]$, then one ordering is $[5, 1, 2]$, and the sum of waiting times is $0+5+6 = 11$. But the algorithm should return $[1, 2, 5]$ because the sum of waiting times in this order is $0+1+3 = 4$.

Solution
The algorithm returns $A$ sorted in non-decreasing order. Intuitively, longer jobs should appear at the end, because that way, they contribute to the waiting time of fewer jobs. More formally, suppose that the optimal solution is not sorted in non-decreasing order, i.e., it processes some job $i$ immediately before another job $j$ but $A[i] > A[j]$. Then swapping $i$ and $j$ (and leaving all other jobs untouched) causes $i$ to wait $A[j]$ more time and $j$ to wait $A[i]$ less time. This exchange does not change the waiting time of any other job, so its net effect on the waiting time is a decrease by $A[i] - A[j] > 0$. Sorting an array takes $O(n\log n)$ time.

3.2. The input is $(G, T, e)$ where $G$ is a connected, undirected graph with distinct edge weights, $T$ is the MST of $G$, and $e$ is an edge in $T$. Suppose $w(e)$, the weight of $e$, increases. (Assume that all edge weights are still distinct.) Describe an $O(m+n)$-time algorithm that returns the MST of this new graph (i.e., $G$ after increasing $w(e)$), explain why it’s correct, and analyze its running time.

Solution

Remove $e$ from $T$ to create a cut in the graph, and add the lightest edge crossing the cut to $T$. More specifically:

ALG(G, T, e):
  u, v = endpoints of e
  remove e from T
  S = vertices reachable from u  # run BFS(T, u)
  e = lightest edge crossing S
  return T + e

Correctness: First, we show that every edge $f \in T$ other than $e$ is still in the MST. If we remove $f$ from $T$, we obtain a cut $S$, and $f$ is the only edge in $T$ crossing $S$. By the cut property, $f$ is the lightest edge crossing $S$, and this holds even if we increase $w(e)$ (or the weight of any other edge in $T$).

Thus, the $n-2$ edges of $T$ excluding $e$ are still in the MST of the new graph. The algorithm removes $e$ from $T$ to create a cut, and no edge of $T$ crosses the cut. By the cut property, the lightest edge crossing this cut must be in the new MST, so the algorithm correctly adds it to $T$.

Running Time: Removing $e$ from $T$ takes $O(n)$ time, and running BFS from $u$ takes $O(n)$ time (because $T$ has $n$ vertices and $n-2$ edges at this point). Then we scan the $m$ edges of $G$, keeping track of the lightest one crossing $S$, and we can do this in $O(m)$ time. Thus, the total running time is $O(m+n) = O(m)$ (since $G$ is connected, $n-1 \leq m$).

3.3. Suppose there are an unlimited number of dimes (10 cents each), nickels (5 cents), and pennies (1 cent). We are given a positive integer $t$, and we want to select the fewest number of coins such that their total value is exactly $t$ cents. Describe an $O(1)$-time greedy algorithm for this problem and explain why it’s correct. The algorithm should return a list $[a, b, c]$, where $a$ is the number of dimes, $b$ is the number of nickels, and $c$ is the number of pennies chosen by the algorithm.

Example: If $t = 17$, the algorithm should return $[1, 1, 2]$.

Solution

The algorithm is greedy: take as many dimes as possible, then nickels, then pennies. In the pseudocode below, we follow the notation from Python: a//b denotes $a/b$ rounded down to the nearest integer.

ALG(t):
  a = t // 10; t -= 10*a
  b = t // 5; t -= 5*b
  c = t
  return [a, b, c]

Correctness: Let $\mathsf{OPT} = [a^\ast, b^\ast, c^\ast]$ denote an optimal solution; we want to show $a+b+c = a^\ast + b^\ast + c^\ast$. First, we claim $a = a^\ast$. Notice that if $a^\ast > a$, then $\mathsf{ALG}$ could have picked at least one more dime, because it starts by picking as many dimes as possible. If $a > a^\ast$, then $\mathsf{OPT}$ must have at least 10 cents’ worth of nickels and pennies. But this implies some of these nickels and pennies can be replaced by a dime. To see this, consider the following cases:

  1. If $\mathsf{OPT}$ has at least 2 nickels, then these 2 coins can be replaced with a dime.
  2. If $\mathsf{OPT}$ has exactly 1 nickel, then it must have at least 5 pennies, and these 6 coins can be replaced with a dime.
  3. If $\mathsf{OPT}$ has no nickels, then it must have at least 10 pennies, and these 10 coins can be replaced with a dime.

In every case, we can make a replacement in $\mathsf{OPT}$ that would decrease the total number of coins in $\mathsf{OPT}$, which is impossible since $\mathsf{OPT}$, being optimal, already uses the fewest possible number of coins. Since $a^\ast > a$ and $a > a^\ast$ are both impossible, we must have $a = a^\ast$. By the same reasoning as above, we can show $b = b^\ast$ (since 5 pennies can replace 1 nickel). Finally, since $\mathsf{ALG}$ and $\mathsf{OPT}$ have the same value in coins, we must have $c = c^\ast$.

Running Time: The algorithm comprises a constant number of primitive operations, so the running time is $O(1)$.