15. Greedy Algorithms

Exercises

15.1-1

Available in the latest revision of the IM.

15.1-2

Available in the latest revision of the IM.

Another, perhaps even clearer, approach is to tweak Theorem 15.1 to read as: "Consider any nonempty subproblem $S_k$, and let $a_m$ be an activity in $S_k$ with the latest start time. Then $a_m$ is included in some maximum-size subset of mutually compatible activities of $S_k$."

The proof is virtually the same as for the original version from the book. This theorem ensures that making a greedy choice is a safe move.

15.1-3

Available in the latest revision of the IM.

15.1-4

Available in the latest revision of the IM.

15.1-5

Available in the latest revision of the IM.

15.2-1

Available in the latest revision of the IM.

15.2-2

Available in the latest revision of the IM.

15.2-3

In this variant, the items can be sorted such that as weight increases, value decreases.This means item 1 is the lightest item in the entire set, and it is the most valuable. Item 2 is the second lightest, and the second most valuable. There is zero trade-off to evaluate. If we have to choose between item $i$ and item $j$ (where $i < j$), item $i$ is strictly superior—it has less (or equal) weight and gives more (or equal) value.

Greedy-Discrete-Knapsack(v, w, n, W)
1  Sort the items so that w[1] ≤ w[2] ≤ ... ≤ w[n] 
   (This guarantees v[1] ≥ v[2] ≥ ... ≥ v[n])
2  total_value = 0
3  remaining_W = W
4  let S be an empty list of selected items
5  for i = 1 to n
6      if w[i] ≤ remaining_W
7          add item i to S
8          total_value = total_value + v[i]
9          remaining_W = remaining_W - w[i]
10     else break  // If this item doesn't fit, no subsequent item will fit
11 return S, total_value

The running time of the core part (without sorting in line 1) is $\Theta(n)$. The extra space complexity is $\Theta(1)$ (not counting the set $S$ returned by the program).

15.2-4

Available in the latest revision of the IM.

15.2-5

Available in the latest revision of the IM.

★ 15.2-6

Available in the latest revision of the IM.

15.2-7

Available in the latest revision of the IM.

15.3-1

Available in the latest revision of the IM.

15.3-2

Available in the latest revision of the IM.

15.3-3

Available in the latest revision of the IM.

15.3-4

Available in the latest revision of the IM.

15.3-5 🌟

Shows how to represent any optimal prefix-free code on C using only $2n − 1 + n ⌈lg n⌉$ bits.

Available in the latest revision of the IM.

15.3-6

Available in the latest revision of the IM.

15.3-7

Available in the latest revision of the IM.

15.3-8

Available in the latest revision of the IM.

The solution in the IM is needlessly overcomplicated. Especially, the derivation of the summation formula $\sum_{k=0}^{n-1} k2^k = n2^n - 2^{n+1} + 2$ is a spectacular mess.

Lossless compression is fundamentally about maintaining a one-to-one correspondence between distinct input files and distinct output files. Consider all possible input files of exactly $n$ bits. Because each bit can be a 0 or 1, there are exactly $2^n$ distinct input files. Suppose a compression scheme guarantees every file is strictly shortened. The total number of possible output files across all these shorter lengths is

$$\sum_{k=0}^{n-1} 2^k = 2^0 + 2^1 + \dots + 2^{n-1} = 2^n - 1.$$

By the pigeonhole principle, the scheme cannot be perfectly invertible (lossless).

15.4-1

Cache-Manager(C, k, S, i)
 1  n = |S|
 2  b = S[i]
 3  if b ∈ C
 4      print "Cache hit"
 5  else print "Cache miss"
 6      if |C| < k
 7          C = C ∪ {b}
 8          print "No block evicted"
 9      else evict-block = NIL
10          max-future = -1
11          for each c ∈ C
12              future-index = ∞
13              for j = i + 1 to n
14                  if S[j] == c
15                      future-index = j
16                      break
17              if future-index > max-future
18                  max-future = future-index
19                  evict-block = c
20          C = C - {evict-block}
21          C = C ∪ {b}
22          print "Evicted block:" evict-block
23  return C

Lines 9-19 find the block for eviction using the furthest-in-future strategy. The running time of this block is $O(k(n - i))$, but the per-eviction cost can be significantly reduced by globally preprocessing the sequence in $\Theta(n)$ time to store future indices for each block type. This can be saved inside a hash table. Furthermore, the cache configuration may be extended with a max-heap to efficiently find the next block to evict.

15.4-2

Available in the latest revision of the IM.

15.4-3

Available in the latest revision of the IM.

15.4-4

Shows that for every solution that allows multiple blocks to enter the cache upon each request, there is another solution that brings in only one block upon each request and is at least as good.

Available in the latest revision of the IM.

Problems

15-1 Coin changing

Available in the latest revision of the IM.

15-2 Scheduling to minimize average completion time

Available in the latest revision of the IM.