[SOLVED] Fundamental-Algorithms Homework 6

3 “You know that I write slowly. This is chiefly because I am never satisfied until I 4 have said as much as possible in a few words, and writing briefly takes far more 5 time than writing at length.”
6 — Karl Friedrich Gauss
7 (1777-1855)
10 ¶1. An algorithmic approach is called “greedy” when it makes decisions for each step based 11 on what seems best at the current step. Moreover, once a decision is made, it is never revoked.
greedy with no regrets
To make this concept of “greedy decisions” concrete, suppose we have some “gain” function
) which quantifies the gain we expect with each possible decision x. View the algorithm as 17 making a sequence x1,x2,…,xn of decisions, where each xi ∈ Xi for some set Xi of feasible 18 choices at the ith step. Greediness amounts to choosing the xi ∈ Xi which maximizes the value
19G(x). Add
24 The greedy method is supposed to exemplify the idea of “local search”. But a closer exam25 ination of many greedy algorithms will reveal some global information being used. The global 26 information is usually minimal or easily obtained, such as doing a global sort. Indeed, the 27 preferred data structure for delivering this sorting information is the priority queue. The ith 28 step in the above decision sequence follows this sorting order.
29 We begin with three classes of greedy problems: the bin packing problems, the coin changing 30 problems and interval selection problems. Next we discuss the Huffman coding problem and 31 minimum spanning trees. An abstract setting for the minimum spanning tree problem is based 32 on matroid theory and the associated maximum independent set problem. This abstract 33 framework captures the essence of a large class of problems with greedy solutions.
34 §1. Joy Rides and Bin Packing
35 We start with an extremely simple problem called linear bin packing. But it will open the 36 door to a major topic in combinatorial algorithms called bin packing. In fact, the general bin 37 packing problem is an example of the NP-complete problems which are not known to have 38 polynomial-time solutions.
45 (1) Online policy: this means we must make a decision for each rider at the moment that he
49 (2) First come, first ride policy (FCFR). In other words, there is no “jumping the queue” 50 in getting into a car.
51 Therefore, whenever we make the decision “take the next car”, we must immediately dispatch
52 the current car, and call for the next empty car in order to satisfy the FCRC policy. That is
53 because our joy ride model assumes that there is only one car for loading riders. In Exercises, 54 we explore policies where if you have a “two loading cars” model or are allowed to peek ahead 55 into the queue.
56These two policies are independent. (1) Suppose we have the online policy without the
57 FCRC policy: after we ask a rider to “take the next car”, we need not call for the new car! We
58 can continue loading riders into the current car. In the meantime, we have a secondary queue
59 of riders waiting to take the next car. Of course, this secondary queue must never exceed M 61 becomes necessary with negative weights. See Exercise below.
60 in total weight. (2) We can also have the FCRC policyAdd without the online policy. This setting
62 Example. Let the weight limit be M = 400 (in pounds) and the weights of the riders in the
63 queue be
w = (30,190,80,210,100,80,50) (1) where 30 represents the front of the queue. We can load the riders into 3 cars as follows:
Solution1 : (30,190,80; 210,100,80; 50)
64 where the semi-colons separate successive car loads. For easy read, we henceforth drop the last 65 digit of 0 from these weights, and simply write
Solution1 : (3,19,8; 21,10,8; 5). (2)
Solution2 : (3,19; 8,21; 10,8,5).
Solution3 : (3,19; 8,21; 10,8; 5).
66 They do not improve upon the greedy solution in terms of the number of cars. In fact, Solution3 67 is worse because it uses 4 cars. Nevertheless we are prompted to ask if there exists instances 68 where a non-greedy solution is better than the greedy one?
69 Leaving this question aside for now, let us illustrate our introductory remark about global 70 information in greedy algorithms. Suppose we place riders into the cars in two phases. In phase 71 one, we sort the weights w in (1), giving us a new queue:
Sort(w) = (3,5,8,8,10,19,21). (3)
In phase two, we apply the greedy algorithm to Sort(w), giving us the solution
Solution4 : (3,5,8,8,10; 19,21).
72 This uses only two cars, improving our greedy algorithm. Decisions exploiting sorting is using 73 global information about the queue w. Thus Solution4 has violated both our policies.
74 ¶3. Linear Bin Packing. The solutions compliant with the FCFR Policy can be formalized 75 as “linear solutions”. Given an integer M and a sequence w = (w1,…,wn) of weights satisfying
76 0 < wi ≤ M (i = 1,…,n), a linear solution of (M,w) is given by a sequence
0 < t(1) < t(2) < ··· < t(k) = n. (4)
77 of k breakpoints (for somek ≥ 1). These k breakpoints define k bins, B1,…,Bk where
78 Bi :=(wt(i−1)+1,…,wt(i)). If i = 1, let t(0) = 0 by definition. We say the linear solution is 79 feasible if each Bi contains a total weight at most M. E.g., the greedy solution (2) is a feasible 80 linear solution with three breakpoints: t(1) = 3,t(2) = 6,t(3) = 7. A feasible linear solution is
81 optimal if k is minimum over all feasible solutions. The linear bin packing problem is to 82 compute an optimal linear solution for any inputAdd M,w.
83 ¶4. Greedy Algorithm. It is instructive to write out the Greedy Algorithm for linear bin 84 packing problem (a.k.a. joy ride problem) in pseudo-code. An important criterion for pseudo85 code that it exposes the control-loop structures of the algorithm. Critical variables used in these 86 control-loops should also be exposed. We are happy with English descriptions of variables, etc.
87 Let w = (w1,w2,…,wn) be the input sequence of weights and C denote a container (or bin 88 or car) that is being filled with elements of w. Let the variable W keep track of the sum of the 89 weights in C.
90
Greedy Algorithm for Linear Bin Packing:
Input: (M,w) where w = (w1,…,wn), each wi ≤ M.
Output: Container sequence (C1;C2;··· ;Cm) representing a linear solution. .
Initialization
C ← ∅, W ← 0
. Loop for i = 1 to n
. INVARIANT: M ≥ W = Pw∈C x if (i = n or
M < W + wi)
Append C as Ci to the output sequence C ← ∅, W ← 0
W ← W + wi; C ← C ∪ {wi}.
91
92 Pseudo-code is for human
understanding. It is deliberately short of any actual programming 93 language because programming languages are meant for computers (to be compiled). Our 94 pseudo-code exploits the power of mathematical notations and the linguistic structures of En95 glish which humans understand best. Of course, English can be replaced by any other natural 96 language. Also there are many possible levels of detail, depending on the goals of the pseudo97 code. The above pseudo-code achieves two informal goals:
98 (P1) It can be “directly” transcribed into common programming languages, assuming you know 99 how to use common data types like arrays or linked lists.
100 (P2) It exposes enough details for its complexity to be analyzed up to Θ-order. The Θ-order 101 complexity of common data types are assumed known.
106 We need an important assumption in (G2) which is often taken for granted: we assume
107 the real RAM computational model of Chapter 1. In this model, we can compare and perform 108 arithmetic operations on any two real numbers in constant time.
111 Theorem 1 The greedy solution is optimal for linear bin packing.Add
Proof. Suppose the greedy algorithm outputs k bins as defined by the sequence of breakpoints
0 = t(0) < t(1) < t(2) < ··· < t(k) = n.
Let us compare the greedy solution with some optimal solution with these breakpoints
0 = s(0) < s(1) < s(2) < ··· < s(`) = n.
112 By way of contradiction, assume the greedy algorithm is not optimal, i.e.,
` < k. (5)
113 Now we compare s(i) with t(i) for i = 1,…,`. Note that
114 (a) We have s(1) ≤ t(1) because t(1) is obtained by the greedy method.
(b) We have s(`) > t(`) because t(`) < t(k) = n = s(`).
115 It follows that ` > 1. So there is a smallest index i∗ (2 ≤ i∗ ≤ `) such that s(i∗) > t(i∗). Then
s(i∗ − 1) ≤ t(i∗ − 1) < t(i∗) < s(i∗). (6)
116 The weights in the i∗-th bin of the optimal solution is given by the subsequence w(s(i∗ − 117 1) .. s(i∗)]. But according to (6), this subsequence contains
w(t(i∗ − 1) .. t(i∗) + 1]. (7)
118 This expression is well-defined since t(i∗) + 1 ≤ s(i∗) ≤ n. By definition of the greedy 119 algorithm, the total weight in (7) exceeds M (otherwise the greedy algorithm would have 120 added wt(i∗)+1 to its i∗th car). This is our desired contradiction. Q.E.D.
121
122 ¶6. Global Bin Packing. The joy ride problem is a restricted version of the following 123 (Global) Bin Packing Problem:
124 Given a multiset S = {w1,…,wn} of weights where each wi ∈ (0,1], find a partition
S = S1 ] S2 ] ··· ] Sm (8)
125 of S into the minimum number m ≥ 1 of multisets where each Si has a total weight at most 1.
Call (8) an optimal solution to the Bin Packing instance S and also denote the minimum m by Opt(S). Note that we have departed from the Linear Bin Packing problem in two ways:
(1) The bin capacity is now M = 1. This is not an significant departure since we can divide the original input weights by the capacityM to obtain wi ∈ (0,1]. This process is called normalization, and wi are the normalized weights. In fact, we will often write
S = M1 {w1,…,wn}
126 where wi are the original weights.Add
127 (2) The input weights are not ordered. This is a more profound change because we are no longer 128 dealing with a “linear” problem. Alternatively, if the input is given as a list (w1,…,wn), we 129 are free to reorder them

anyway we like.

1 2 3 4
Figure 1: Bin packing solution.
then one global solution (before normalization) is 131 {3,2},{2,3},{1,1,1,1,1}, illustrated in Figure 1. This solution uses 3 bins, and it is clearly 132 optimal since each bin is filled to capacity.
137 The converse is less clear.
As far as we know, one cannot do much better than the brute force method for computing
). What do we mean by “brute force”? It is to try all possibilities. But what are these 140 possibilities? First, we must give concrete representations of S and its solutions. First, we 141 represent the set S by any listing of its elements in an arbitrary order:
w = (w1,…,wn). (9)
142 If Sn denote the set of all permutations of [1..n], and σ ∈ Sn, then σ(w):=(wσ(1),…,wσ(n)). 143 Likewise, we represent any solution B1,…,Bm (8) to S by any permutation π ∈ Sn in which
π(w) = (wπ(1),…,wπ(n)) (10)
144 lists the weights in B1 first (in any order), followed by the weights in B2, etc. It is clear that 145 there are many representation of any solution; that is OK since Sn is a very large set!
Grd(π(w)) = Opt(w)
146 OBSERVATION: if (10) represents a global solution to the bin packing instance (9), then 147
148 where Grd(w0) is the number of bins used by greedy algorithm on any input w0. It follows that
Grd(σ(w)).
The “brute force”
algorithm for Opt(w) will use the greedy algorithm of linear bin
packing solution as a subroutine: it
cycles through each of the n! permutations
of Sn, and for each σ,
computes Grd(σ(w)) in OAdd (n) time. The minimum of these values is
Opt(w). We conclude that the brute

force method has a complexity of
Θ(n · n!) = Θ((n/e)n+(3/2)).
149 Here, we assume that we can generate all n-permutations in O(n!) time. This is a nontrivial 150 assumption; see §8 for details on how to do this.
154 Lemma 2 (Karp-Held) The global bin packing problem can be optimally solved in O(n!) = 155 O((n/e)n+(1/2)) time in the real RAM model.
156 See Exercise where we further exploit this idea to improve the brute force algorithm by any 157 polynomial factor. The relation between global bin packing and linear bin packing is worth 158 noting: by imposing restrictions on the space of possible solutions, we have turned a difficult 159 problem like global bin packing into a feasible one like linear bin packing. The latter problem 160 is in turn useful as a subroutine for the original problem.
Use the Θ-form of
Stirling’s approximation 161 ¶7. How good is the Greedy Solution? How good is the greedy algorithm Grd when 162 viewed as an algorithm for global bin packing? We are not interested in goodness in terms of 163 computational complexity. Instead we are interested in the quality of the output of Grd, namely 164 the number of bins, Grd(w). We shall compare Grd(w) to Opt(w), the optimal solution. Since 165 Grd(x)/Opt(w) ≥ 1, we want to upper bound the ratio Grd(w)/Opt(w).
166 Theorem 3 For any unit weight sequence w,
Opt(w) ≥ 1 + bGrd(w)/2c (11)
167 Moreover, for each n, there are weight sequences with Opt(w) = n for which (11) is an equality.
168
169 Proof. Suppose Grd(w) = k. Let the weight of ith output bin be Wi for i =
1,…,k. The
170 following inequality holds:
Wi + Wi+1 > 1. (12)
To see this, note that the first weight v to be put into the i + 1st bin by the greedy algorithm must satisfy Wi + v > 1. This implies (12) since Wi+1 ≥ v. Summing up (12) for i =
1,3,5,…,2bk/2 c−1, we obtain. The last inequality implies that the optimal
solution
needs more thanbk/2c bins, i.e., Opt(w) ≥ 1 + bk/2c. This proves (11). To see that the inequality (11) is sharp, consider the following unit
weight sequence of length n:
171

reedy solution uses n bins, but clearly Opt(w) = 1 + bn/2c.
172 Add Q.E.D.
173
174 ¶8. Absolute and Asymptotic Approximation Ratios. We said the global bin packing
175 is an important problem for which there are no polynomial-time algorithms. So it is essential
176 to seek good approximations to global bin packing. Let A be any bin packing algorithm. To 177 evaluate the performance of A, consider the simplest definition that comes to mind: define the 178 absolute approximation ratio of A as
) (13)
179 where w range over all non-empty weight sequences. By definition α0(A) ≥ 1. Our goal is to 180 design algorithms A with small α0(A).
A1(w) = 2 · Opt(w) + 1 (14)
for all w. For each n ∈ N, there is some weight sequences wn such Opt(wn) = n. We would conclude
that α1(A1) = 3 since
1 2 · Opt(w) + 1 1
= 1. The worst case is controlled by the “trivial” input w1. This conclusion seems artificial. Intuitively, we think that a correct definition of approximation ratio ought to yield the conclusion that “α(A1) = 2”. Here is the definition to achieve this: Define the (asymptotic) approximation ratio of algorithm A as

o where: Opt(w) = n . Recall from mathematical analysis that the limit superior of
an infinite sequence of numbers (x1,x2,…) is given by
. source Wikipedia
184 For the algorithm A1, we define : Opt . Then
185 α(A1) = limsupn→∞ an = 2. The behavior of our hypothetical A1 is rather like Grd, as seen 186 in Theorem 3.
187 Lemma 4 The greedy algorithm Grd for Linear Bin Packing has (asymptotic) approximation
188 ratio α(Grd) = 2. (15)
189
190 Proof. Note that Theoremhttps://.3 implies that Opt com . This implies 191
Grd(w) 1
≤ 2 − . (16)
Opt(w) Opt(w)
192 This implies α(Grd) ≤Add 2 (Careful: we are not entitled to say “α(Grd) < 2”). Moreover,
193 Theorem 3 also shows that for each odd integer n ≥ 2, there are inputs with Opt(w) = n for 194 which (16) is an equality. This implies α(Grd) ≥ 2 − ε for any ε > 0. By definition of limsup,
195 α(Grd) ≥ 2. This proves (15). Q.E.D.
196
197 ¶9. First Fit Algorithm. In order to beat the approximation factor of 2 in (15), we must 198 give up the “linearity constraint” of linear bin packing. We consider the following “non-linear” 199 bin packing algorithm:
200
201
First Fit Algorithm
Given w = (w1,…,wn):
Initialize n empty bins: B1,B2,…,Bn.
For i = 1,…,n, place wi into the first bin Bj that it fits into.
Return the sequence of non-empty bins (B1,…,Bm).
202
203 Let FF(w) denote the number of bins used by the First Fit Algorithm. We leave it as an 204 Exercise to give a more detailed pseudo-code for this algorithm, keeping in mind our goals for 205 pseudo-code ¶4.
206 Example: Let M = 7 and w = (3,5,4,1,3,2,3). It is easy to check that Opt(M,w) = 3 207 with the bins (5,2),(4,3),(3,3,1). The greedy achieves Grd(M,w) = 5 with (3;5;4,1;3,2;3).
208 The following simulation of the First Fit Algorithm shows that FF(M,w) = 4:
i wi B1 B2 B3 B4
209
210 FF was one of the earliest bin packing algorithms to be studied.
Johnson, Ullman, Garey 211 and others began its analysis in the
1970s.
212 Theorem 5 α(FF) = 17/10.
In fact, it is now known that even the absolute approximation ratio of FF is 1.7:
Add α0(FF) = 17/10.
214 Let us first prove a lower bound on α(FF), somewhat less than the optimal bound of 1.7:

α(FF) ≥ 5/3 = 1.66. (17)
Let w be a sequence of 18n weights given in 3 groups:

215 Clearly, Opt(w) = 6n since the total weight is (0.15 + 0.34 + 0.51)6n = 6n and so 6n bins are 216 necessary. It is also clearly sufficient. We next claim that FF(w) = 10n: FF puts the first 217 group into n bins (each bin having weight 0.15 × 6 = 0.9), second group in 3n bins (each bin 218 having weight 0.34 × 2 = 0.68), and the last group in 6n bins (each bin of weight 0.51). So 219 FF(w)/Opt(w) = (n + 3n + 6n)/6n = 5/3. as claimed in (17).
220 The upper bound in Theorem 5 is from Ullman (1971) who showed FF(w) ≤ 1.7Opt(w)+3. 221 We give a compact proof from Gy. D´osa and J. Sgall (see [4]). The structure of this highly 222 stylized proof should be first understood:
The value of each item) where b(x) is the bonus defined by
0 if,
) if ,
1 if 4 if.
223 The bonus function b(x) is continuous except at x = 1/2. We extend these definitions to any
224 set B of items: let v(B):= Px∈B v(x) and b(B):= Px∈B b(x). Also, let the size of the bin 225 be given by s(B):= Px∈B x. Thus v(B) = b(B) + s(B). If B are the items in a bin from bin 226 packing, then clearly s(B) ≤ 1. GRAPH of b(x):
227 For any set B of items, if s(B) ≤ 1 then v(B) ≤ 1.7: because 2 and it is sufficient 228 to show that v(B)
≤ 0.5. (see paper)
Heuristics for Bin Packing. The First Fit algorithm, also known as Greedy First Fit, is based on the First Fit Heuristic (FF) in which each weight wi is placed into the first (smallest j) bin Bj in which it fits. This heuristic assumes a sequence of bins B1,…,Bn that remain open for packing additional weights, if they are not full. What we have called the Greedy algorithm for Linear Bin Packing, Grd(w), is based on what is known as the Next Fit Heuristic (NF). Hence another name for Grd is Greedy Next Fit. Finally, the Best Fit Heuristic (BF) is one that packs wi into the bin whose residual capacity exceeds wi by the least amount. You can easily guess how the Greedy Best Fit Algorithm should behave.
229
230 ¶10. Bin Packing on Weight Decreasing
Sequences. The next idea is to introduce
231 sorting. Heuristically, it seems a good idea to pack the larger weights before the smaller ones.
232 Let Sort(w) return the sequence w in decreasing sorting order (breaking ties arbitrarily) E.g., 233 Sort(2,3,1,2) = (3,2,2,1). Adding this heuristic to Grd and to FF, we obtain two new bin 234 packing algorithms: Add
235 • Next Fit Decreasing: NFD(w):=Grd(Sort(w))
236 • First Fit Decreasing: FFD(w):=FF(Sort(w))
237 Our previous bound that α(Grd) = 2 is no longer valid for α(NFD), but we have this lower 238 bound:

239 Lemma 6 (Next Fit Decreasing) α(NFD) ≥ 5/3 = 1.66.
Proof. Consider this sorted sequence of 3n weights in three equal size groups:
.
240 where = 1. So e = 1/126. Thus Opt(w) = n. The greedy algorithm uses n bins
241 for the first group. The first weight of fits into the previous bin. The next n − 1 weights 242 fit into (n − 1)/2 bins (assume n is odd). The first weight of fits into the previous bin.
243 The remaining n − 1 weights fit into (n − 1)/6 bits (assume n − 1 is divisible by 6). Thus 244 NFD(w)
= n + (n − 1)/2 + (n − 1)/6 = (5n − 2)/3, or NFD(w)/Opt(w) = 5/3 − (2/3n). We
245 conclude that α(NFD) ≥ 5/3. Q.E.D.
246
Theorem 7 (First Fit Decreasing)

1.22 = 11/9 ≤ α(FFD) ≤ 1.5.
Remark: the tight upper bound of

α(FFD) ≤ 11/9 = 1.22
is known; but we state a weaker result here because its proof is relatively simple.
Proof. The lower bound on α(FFD) comes from the following weight sequence w = (w1,…,w30n) where
,
247 The optimal packing uses 9n bins: we can pack 6n bins with weights (), and 248 3n bins with weights (). However, we see that FFD uses 11n bins: 249 it fills the first 6n bins with (), the next 2n bins with (), and the 250 last 3n bins with (
251 To prove the upper bound on α(FFD), it suffices to prove that for any unit weight sequence
252 w,
FFD(w) ≤ 1.5 · Opt(w) + 1. (18)
253 Suppose FFD(w) = k. Consider the firstm = b2k/3c bins, say B1,…,Bm. We claim that
254 Opt(w) ≥ m. There two cases. (1) Suppose bin Bm contains a weight > 1/2 (for i = 1,…,m). 255 Thus Opt(w) ≥ m as claimed. (2) Suppose bin Bm contains only weights that are ≤ 1/2.
256 Therefore, the remaining k − m bins contains only weights that are ≤ 1/2. This implies each
257 of these k −m bins contains at least two weights. So there are 2(Add k −m) = 2dk/3e ≥ 2k/3 ≥ m
258 weights in these bins. Take any m of these weights v1,v2,…,vm. None of these weights fits 259 into the first m bins. Therefore vi + |Bi| > 1 for i = 1,…,m (where |Bi| is the total weight 260 contained in Bi), i.e., Opt(w) ≥ m. So we have proved that Opt(w) ≥ m. It follows that 261 Opt(w) ≥ m = b2k/3c ≥ (2k − 2)/3, or k = FFD(w) ≤ 1.5 · Opt(w) + 1. This concludes our
262 demonstration of (18) Q.E.D.
263
264 The efficient implementation of Step 4 in the First Fit algorithm is interesting: we could use
Insert(wi):
1. Initialize u to the root of T.
2. While (u is not a leaf)
3. If (u.left.key ≥ wi) u ←
u.left
4. else u ← u.right
5. u.key ← u.key − wi / u is a leaf
6. While (u is not the root)
7. u ← u.p / move to the parent
8. u.key ← max{u.left.key,u.right.key}
265 a while loop, checking B1,B2,B3,… in this order until we find a bin that can accept wi. Each 266 iteration of the while-loop is O(n) time, with overall complexity O(n2). But let us improve this 267 to O(logn), giving an overall complexity of O(nlogn). We represent the bins as leaves of a 268 (static) binary tree T of height O(lgn). The ith leaf stores the set of weights in bin Bi. Define 269 the residual capacity of Bi to be Ri :=M − Wi where Wi is the sum of the weights in Bi. 270 Each node u of T stores a key u.key which is the maximum residual capacity of the bins in the 271 subtree at u. Initially, each Wi is zero, and so u.key = M for each node u. For each wi, we 272 can find the first bin Bj whose residual Rj is at least as large as wi as follows:
273
274
275 The first while-loop (Line 2) finds the leftmost bin Bj where wi can be inserted; the second 276 while-loop (Line 6) updates the keys along the path from Bj to the root.
277 ¶11. Two-Car Loading. Consider the extension of linear bin packing where we simulta-
278 neously load two cars. Call these two cars thefront and rear cars. This is a realistic joy
282 one car). If neither car can accommodate the new rider, we mustdispatch the front car, so
287 What is a good design Grd2 for 2-car loading? The goal, as usual, is to minimize the 288 number of cars used for any given input sequence w. we want to ensure Grd2 is at least as 289 good as Grd, the loading policy of the original greedy algorithm (¶4). More precisely, for all
290 w = (w1,…,wn), we require
Grd2(w) ≤ Grd(w). (19)
291 A trivial way to ensure (19) is to just just imitate Grd! This means (19) is actually an equality, 292 but it is not very interesting. We want a policy Grd2 where, in addition to (19), there are many 293 inputs w where Grd2(w) < Grd(w), with quantifiable advantages.
294 Consider the following definition of Grd2: Load each rider into the front car if it fits, 295 otherwise load into the rear car if it fits. If neither fits, dispatch the front car. We leave 296 as an exercise to show (19). But Grd2 can be strictly better than Grd: For instance, if 297 w = (30,190,80,210,90,80,50) and M = 400 in our example in (1), then the first fit pol298 icy gives an improvement: Grd2(w) = 2 < 3 =
Grd(w).
299 We can extend the 2-car loading framework: these extensions):
300 • Allow decisions to be revoked. This means that, upon seeing the next rider in the queue, 301 we are allowed to move one or more riders between the front and rear cars. An even 302 stronger notion of revoking is to exchange a rider in one of the two loading cars with the 303 rider at the head of the queue.

Note that this stronger notion can be applied even in 304 1-car loading.
305 • Assume that two loading cars are in “parallel tracks” (left or right tracks). That means
310 ¶12. Extensions. There are many ways to extend the bin packing problem. Let us consider 311 the higher dimensional version of this problem. In particular, the packing of rectangles into 312 rectangular bins. One interesting simplified 2-dimension problem is to consider one bin of unit 313 width but infinite height: we want to pack the rectangles so as to minimize the height of the 314 packing. A popular computer game is based on this problem.
315 Let us consider another simplified 2-dimensional problem: the bins are unit squares, and the 316 input is a sequence of squares. Let w = (w1,w2,…,wn) where 0 < wi ≤ 1 represents an input 317 square of width wi. Things are complicated enough in 2D that we will begin with assuming 318 that the wi are already sorted by non-increasing weights.
319 We start with the simplest greedy
packing heuristic that we can analyze. Consider the 333
320 following cell packingidea: Suppose we subdivide each bin into cells using the usual quadtree 321 method: a bin is a cell, and given any cell, we can recursively split it into 4 congruent subcells. 322 We want to put the wi’s into cells, at most one per cell! Moreover, each cell is guaranteed
to
323 be at least 1/4 full. The latter condition is easy to fulfill: if a cell is not 1/4 full, we can split 324 it first, and use one of its child. It is not hard to prove that this gives an approximation ratio 325 α(A) = 1/4.
326 Add
327 Exercises
328 Exercise
1.1: We
consider linear bin packing problem in which the weights wi’s can be nega-
329 tive.
330 (a) Show that Grd(w) is no longer optimal for linear bin packing.
331 (b) How
bad can
Grd(w)
compared
to the optimal linear bin packing solution?
Please
332 quantify
“badness”
in some
reasonable way. ♦

roof for the greedy algorithm breaks
334 down when
there are
negative weights.
What are they?
♦
Exercise 1.3: Consider the linear bin packing problem when the weight wi’s can be negative. A solution is determined by its the sequence of breakpoints, 0 = n0 < n1 < n2 < ··· < nk = n where the ith car holds the weights
[wni−1+1,wni+2,…,wni].
335 Here is a greedy way to define
these
indices: for i
≥ 1,
assuming
ni−1 is defined, let ni
336 to be the largest index (but at most n) such that. Either prove that
337 this
solution is optimal (in the sense of linear bin packing), or give a counter example.
338 NOTE: this algorithm is no longer
line problem?

339 Exercise
1.4: Give an O(n2) algorithm for linear bin packing when there are negative weights. 340 HINT: When
solving the problem for (M,w), assume that you already know the
solution
341 for
each (M,w0) where w0 is a suffix of w.
342 ♦ 343 E
x e r
ci
s
e 1.
5
:
I
m
p r o v
e
t h
344 H
I
N
T
:
R
e p e a t
t h
e tr ic
k w
h
ic h s a v e
d
u s a
f a
c t o r
o f
n i
n
t h
e fi r
st p
la
w off the 1, car w with 2 the
b smaller
el residua
o l
n capacit g y (and t put wi o into its t replace h ment e car).
s 357
a Call this m the best e fit dualb track 2-
i car
n strateg
o y, and r let Grd) t be the h number
e of
y 358 cars
d used by o this n strateg
o y on t. input w
♦ (say
capacit y is 1). 346 Exercise 1.6: Above we extended the Karp-Held idea of improving brute-force by another This is
347 factor of n. Can this be further extended? ♦ open
ended:
compar
348 Exercise 1.7: We have the 2-car loading problem, but now imagine the 2 cars move along e
two 349 independent tracks, say the left track and right track. Either car could be sent off
359 Grd) to before 350 the other. We still make decision for each rider in an online manner, but our ith
Grd and
decision 351 xi now comes from the set {L,R,L+,R+}. The choice xi = L or xi = R means we
Grd2.
load

352 the ith rider into the left or right car (resp.), but xi = L+ means that we send off the left ♦
353 car, and put thei-th rider into a new car in its place. Similarly for xi = R+. Consider
354 the following heuristic: let C0 > 0 and C1 > 0 be the residual capacities of the two open 355 cars. Try to put wi into the car with the smaller residual capacity. If neither fits, we 356 send
360 Exercise 1.8: Let Grd2Add (w) and) denote (respectively) the number of cars used when 377 smalles
361 loading according to the First Fit and Best Fit Policies. t
362 (a) Show an example where Grd possibl
363 (b) Show an example where Grd ♦ e
number
of
364 Exercise 1.9: In the text, we compare our 2-car loading policy against an optimal bin packing rectang
correct
369 Exercise 1.10: (Open ended) Explore the revoking of decisions in 1- or 2-car loading. ness.
♦
♦
370 Exercise 1.11: (Open ended) Quantify the improvements possible when loading 2 cars in
371 parallel tracks instead of loading 2 cars in a single track. ♦
372 Exercise 1.12: Weights with structure: suppose that the input weights are of the form wi,j = 373 ui +vj and (u1,…,um) and (v1,…,vn) are two given sequences. So w has mn numbers. 374 Moreover, each group must have the form w(i,i0,j,j0) comprising all wk,` such that i ≤ 375 k ≤ i0 and j ≤ ` ≤ j0. Call this a “rectangular group”. We want the sum of the weights 376 in each group to be at most M, the bin capacity. Give a greedy algorithm to form the
378 Exercise 1.13: For 0 < r < 1, let Opt(r) denote the maximal number of identical disks of 379 radius r that can be packed into a unit disk.
380 (a) Device a greedy online algorithm for this problem, and analyze its performance relative
381 to Opt(r),
382 (b) How good is your algorithm when r = 1/2? ♦
383 Exercise 1.14: A vertex cover for a bigraph G = (V,E) is a subset C ⊆ V such that for 384 each edge e ∈ E, at least one of its two vertices is contained in C. A minimum vertex 385 cover is one of minimum size. Here is a greedy algorithm to finds a vertex cover C:
386
Greedy Vertex Cover(G(V,E)):
1. Initialize C to the empty set.
2. Choose a vertex v ∈ V with the largest degree. Add
387 vertex v to the set C, and remove vertex v and all edges
that are incident on it from graph G.
3. Repeat step 2 until the edge set is empty.
4. The final set C is a vertex cover of the original G.
388
389 (a)Show a graph G for which this greedy algorithm fails to give a minimum vertex 390 cover. HINT: There is an example with 7 vertices.

Page
391 (b) Let x = (x1,…,xn) where each variable xi is associated with vertex i ∈ V = 392 {1,…,n}.
Consider the following set of inequalities:
• For each i ∈ V, introduce the inequality 0 ≤ xi ≤ 1.
• For each edgeAdd i − j ∈ E, introduce the inequality xi + xj ≥ 1.
393 Let a = (a1,…,an) ∈ Rn. If the assignment x ← a satisfies these inequalities, we call 394 a a feasible solution. If each ai is either 0 or 1, we call a a 0 − 1 feasible solution. 395 Clearly, there is a bijective correspondence between the set of vertex covers and the set 396 of 0−1 feasible solutions. denote the corresponding 0−1 feasible solution. We also write
397 |a| for the sum a1 + ··· + an. Suppose x is a feasible solution that
398 minimizes the |x|, i.e., for all feasible x,
|x∗| ≤ |x|. (20)
399 Call x∗ an optimum vector. Construct a graph G = (V,E) where the optimum vector 400 x∗ is not a 0 − 1 feasible solution.
401 (c) There exists an optimal x∗ that is half-integer valued, i.e., each component is
402 or 1.
403 (d) Given a vector x, define the rounded vector bxe where each component xi is 404 rounded to bxie ∈ {0,1}. Note that rounding is usually defined up to some tie-breaking 405 rule, viz., how to round 0.5. Show that, with a suitable tie-breaking rule, if x is feasible 406 solution then bxe is feasible 0 − 1 solution. 407 (e) Suppose C∗ is a minimum vertex cover. Show that |bx∗e| ≤ 2|C∗|. ♦
408 Exercise 1.15: Consider the following trivial vertex cover algorithm:
409
Trivial Vertex Cover(G(V,E)):
1. Initialize C ⊆ V,M ⊆ E to be empty sets
2. While E 6= ∅
3. Pick any edge u − v ∈ E
4. M ← M ∪ {u − v}
5. C ← C ∪ {u,v}
6. Remove from E any edge that is incident on either u or v 7. Return C
410
411
412 (a) Show that the
output C is at most twice the
size of the minimum vertex cover. 413 HINT: the set M ⊆ E is useful for this proof. For two sets A and B, you can show that 414 |A| ≤ |B| by showing that there exists an injective function f : A → B.
415 (b) Given that the trivial algorithm is also a 2-approximation algorithm for Vertex 416 Cover, are there reasons to use the rounding algorithm bx∗e of the previous algorithm?
417 ♦ 418 E
x e r
ci
s
e 1.
1
6
:
S u p p o s
e
y o
u
h a v
e a
n al g o
ri t h m t o s o lv e t h e
# B i n
P a c k i n g
P r o b le m
.
C a n y o u
4
1
9 u s e t h is al g o ri t h m a s a s u b r o u ti n e t o fi n d a n o p ti m al b i n p a c k i n g
?
H o w o ft e n d o y o
u
420 need to call the subroutine?♦
421 Exercise 1.17: For k ≥ 1, a k-coloring of a bigraph G = (V,E) is a function C : V →
422 {1,…,k}. The coloring isproper if u − v ∈ E implies C(u) 6= C(v). The chromatic
423 number of G is the smallest k such that there exists a proper k-coloring of G; this 424 number is denoted χ(G). Computing the chromatic number of bigraphs is one of the
425 pure graph problems for which we do not know any polynomial time solution. But like
434 (b) Suppose we first sort the vertices in order of increasing degrees. How bad can the 435 greedy coloring be in this case?
436 (c) Show that
there exists an
enumeration whose greedy coloring is optimal.
437 (d) Using (d), establish an upper bound on the complexity of computing chromatic num-
438 bers. ♦
439 End Exercises
440 §2. Coin Changing Problem
441 In the US, if you paid your grocer bill of $5.75 with a ten dollar bill, you are very likely to get 442 back four singles ($1.00 bills) and a quarter (25 cents) as change. You would be surprised if you 443 get, say, three singles and 5 quarters even though this is the right amount. Your expectation 444 suggests that there is a deterministic algorithm that cashiers use under normal circumstances.
greed and money,
445 In fact, it is a greedy algorithm. What problem does this greedy algorithm solve? It is popularly yes, they go
446 known as the coin changing problem although paper bills also count as coins here. together

D = [1,5,10,25,$1,$5,$10,$20,$50,$100]. (21)
453 In (21), we have omitted the rare two-dollar bill which has been a US denomination since
454 1976. For x ∈ N, a D-solution for x is any vector s ∈ Nm such that the dot product equals x. Call x the value of s. We say D is complete if every positive 456 integer has a D-solution. It is easy to see that D is complete iff d1 = 1. In other words, the 457 humble penny is what makes our currency system complete.
Two D-solutions s,s0 are equivalent denoted s ≡ s0, if they have the same value. For example, if s = (0,0,0,1,4,0,0,0,0,0) is a solution in the US currency system (21), then its value is hs,Di = $4.25 (the change we expected in the initial example). An equivalent solution
would be s0 = (0,0,0,5,3,0,0,0,0,0), i.e.,
(0,0,0,1,4,0,0,0,0,0) ≡ (0,0,0,5,3,0,0,0,0,0),
458 Henceforth, we omit reference toD if it is understood (so we speak of “solution” instead of 459 “D-
solution”, etc).
460 Call s a greedy solution for x if s is lexicographically the largest among solutions for x:
462 s − s0 is positive. For example,Add s0 = (0,0,0,5,3,0,0,0,0,0) then s is lexicographically larger 461 that means that if s0 is another solution, then the last non-zero entry in the vector difference 463 than s0. Note that we look at last (not first) non-zero entry entry because we order the vector 464 D from smallest to largest denomination.
465 ¶13. The Canonicity Problem. The size of a solution s = (s1,…,sm) is given by
. Thus “size” is the “number of coins” we get in change during a transaction. An 467 optimal solution for x is any solution s for x of minimum size. Let OptD(x) (resp., GrdD(x)) 468 denote any optimal (resp., the greedy) solution, assuming x is a multiple of d1. Clearly, we have 469 |OptD(x)| ≤ |GrdD(x)|. We say D is canonical if |GrdD(x)| = |OptD(x)| for all x ∈ N that is 470 a multiple of d1. For instance, D = [1,2,4,5] is not canonical. To see this, notice that greedy 471 solution for x = 8 is (1,1,0,1) of size 3. The optimal solution is (0,0,2,0) with size 2. On 472 the other hand D = [1,2,4,8] is canonical because for any x, the greedy solution (s1,s2,s3,s4) 473 has s4 = bx/8c which is necessary for optimality, and the remainder x mod 8 has a unique 474 optimal solution in the system [1,2,4]. This argument shows that any binary currency system 475 [1,2,4,…,2m−1,2m] is canonical. The key open problem in coin changing is to characterize 476 all canonical systems. Surprisingly, this problem remain unsolved.
477 Besides canonicity, another desirable property is uniqueness: D has uniqueness if OptD(x) 478 is unique for every x that is a multiple of d1. For example, the system [1,2,3] is a canonical 479 system, but it is non-unique since x = 4 has two solutions, (1,0,1) ≡ (0,2,0).
480 If s = (s1,…,sm) and) then we write s ≤ s0 to mean that si ≤ s0i for all i.
481 Call s a subsolutio n of s0. The following is easy to see: Optimal solutions are closed under the
The 2 dollar bill was
introduced in 1862, discontinu ed in 1966, and reintroduc ed in 1976 for the US Bicentennial. the main problem!

482 subsolutions. In other words, subsolutions of an optimal solution are optimal. This is a form 483 of the Dynamic Programming Principle which we will address in Chapter 7.
Chee
484 To show non-canonicity, we need counter examples. If |GrdD(x)| > |OptD(x)|, we call x a 485 counter example for (the canonicity of) D. Suppose x is a minimum counter example for 486 D =
[d1,d2,…,dm], i.e., any value less than x is no counter example. Tien and Hu noted that
487 if Opt) is an optimum solution for such an x then
si · s∗i = 0 (for all i = 1,…,m) (22)
488 where GrdD(x) = (s1,…,sm). Suppose not. Say si · s∗i > 0. Then we can replace x by 489 x0 = x − di to get a strictly smaller counter example. Why? Clearly, Grd(x0) is obtained from 490 Grd(x) by subtracting 1 from the i-th component. Also, |Opt(x0)| ≤ |Opt(x)| − 1. We know 491 that |Opt(x)| < |Grd(x)|. Thus |Opt(x0)| ≤ |Opt(x)| − 1 < |Grd(x)| − 1 = |Grd(x0)|. Thus x0 is 492 also a counter example, contradicting the minimality of x.
493 Let q(D) = (q1,q2,…,qm) where qi = ddi+1/die for each i = 1,…,m−1. Also let qm = ∞. 494 Thus q(D) is roughly the multiple by which successive denominations increase. Then for any 495 x, we claim Grd(x) ≤ q(D) (23)
496 in a componentwise manner: if Grd(x) = (s1,…,sm) then si ≤ qi for all i. If (23) is violated 497 at some i, say si > qi, then we can construct a solution s0 that is lexicographically larger than
498 s (in particular, we can make s0i+1 > si). This contradicts the definition of s as the greedy
499 solution.
500 ¶14. Is the US Currency System canonical? Not all currency system is canonical – the have you ever met 501 pre-1971 British currency system is non-canonical (Exercise). Experience suggests that the USAdd a counter example? 502 Currency system is canonical. But how do we prove this?
Towards this end, let us say one currency systems D0 is an extension of another D when D is a prefix of D0. Consider the following sequence of extensions:
D1 = [1,2,4], D2 = [1,2,4,5], D3 = [1,2,4,5,8].
503 We already noted that D1 is canonical and D2 is not. Thus, there are non-canonical extensions 504 of canonical ones. Moreover, it can be shown that D3 is canonical (Cai-Zheng). Thus, there 505 are also canonical extensions of noncanonical ones. These examples hint at the difficulty of 506 canonicity.
507 Consider two kinds of extensions of D = [d1,…,dm]:
508 • Type A extension is D0 = [d1,…,dm,dm+1] where dm+1 = dm ·q for some q ≥ 2. E.g., 509 [1,5,10] is a type A extension of [1,5].
510 • Type B extension is D0 = [d1,…,dm,dm+1,dm+2] where
dm+1 = dm · q (for some
dm+2 = dm+1 · q0 + dm · r (for some q0 ≥ 1,r ≥ 1. (24)
511 Call (q,q0,r) a set of parameters of the Type B extension. E.g., [1,5,10,20,50] is a type 512 B extension of [1,5,10] with parameters (q,q0,r) = (2,2,1).
513 If r > q, then (q,q0 + 1,r − q) is also a set of parameters for the extension. By repeating this 514 process, we conclude that there is a set of parameters in which r < q. Call it a reduced set 515 of parameters for the Type B extension.
516 Examples: Trivially, D = [d1] and D = [1,d2] is canonical for any d1 ≥ 1 and d2 > 1. 517 The system D = [1,2,3] is a Type B extension with parameters (q,q0,r) = (2,1,1). and 518 D00 = [1,5,10,25] is a Type B extension of [1,5] with parameters (q,q0,r) = (2,2,1). In fact,
519 the US currency system (21) is a sequence of Type A and Type B extensions of [1]. Indeed, 520 this remains true even if we add the two dollar bill to the system. We now characterize how 521 canonicity is preserved under these extensions:
522 Theorem 8 Let D be a canonical system, D0 be a Type A extension of D, and D00 be a Type 523 B extension of D with reduced parameters (q,q0,r).
524 (i) If D is canonical, then D0 is canonical.
525 (ii) If D is canonical, then D00 is canonical iff r < q ≤ r + q0.
526 (iii) If D is uniquely canonical, then D00 is uniquely canonical iff r < q < r + q0.
Proof. Let us initially assumeD = [q1] (we will see that this is without loss of generality). Then D0 = [d1,qd1] (q ≥ 2) and D00 = [d1,qd1,(qq0 + r)d1] (r < q).
(i) Suppose x is the minimum counter example for D0 where q ≥ 2. If the greedy D0-solution
for x is Grd) then 1. If Opt) then by property (
Thus, we can view OptD0(x) as a D-solution for x. Since D is canonical, this proves that
|OptD0(x)| ≥ |GrdD(x)|. Thus,
|GrdD0(x)| > |OptD0(x)| x is a counter example Add ≥ |GrdD(x)| just noted
= s01 + qs02 since GrdD
= |GrdD0(x)| + (q − 1)s02
> |GrdD0(x)| q ≥ 2 and
which is a contradiction.
(ii) Note that D0 is canonical (by part(i)), and r < q holds by definition of reduced parameters. We must show that q ≤ r + q0 holds iff D00 is canonical. There are two cases: CASE 1, q > r + q0: In this case, we must provide a counter example. This is readily provided by the x such that GrdD00(x) = (q − r,0,1).
527 Then (q−r,0,1) ≡ (0,q0+1,0) and we see that |(q−r,0,1)| = q−r+1 > q0+1 = |(0,q0+1,0)|.
CASE 2, q ≤ r + q0: by way of contradiction, assume there is a counter example. KozenZaks
(Exercise) shows that the minimum counter example x has the form GrdD00(x) = (a,0,1) for some
a ≥ 0. But we know (a,0,1) ≡ (a + r,q0,0). The optimal solution satisfies )). Since () is equal to GrdD0(x) (by canonicity of D0), we deduce
0) if a + r < q else.
528 If a + r < q, |s∗| = a + r + q0 ≥ a + 1 = |GrdD00(x)|. If a + r ≤ q, |s∗| = a + (r − q) + 1 + q0 ≥
529 a + 1 = |GrdD00(x)|. In either case, we have shown that |s∗| ≥ |GrdD00(x)|, i.e., the D00-greedy 530 solution for x is optimal. This contradicts the assumption that x is a counter example.
531 (iii) This is similar to part(ii). We must show that q < r+q0 iff D00 is uniquely canonical. Again, 532 consider two cases. CASE 1, q ≥ r + q0. We see that (q − r,0,1) ≡ (0,q0 + 1,0) implies that 533 the greedy solution (q−r,0,1) has size that is either greater than or equal to (0,q0 +1,0). This 534 shows it is either suboptimal or non-unique. This proves that D00 is not uniquely canonical. 535 CASE 2, q < r+q0: We want to show that D00 is uniquely canonical. By way of contradiction, 536 assume an x where |OptD00(x)| ≤ |GrdD00(x)|. The same argument as before will lead to the 537 contradiction that |OptD00(x)| > |GrdD00(x)|.
538 The arguments for parts(i)-(iii) assume D = [d1]. But it is easy to see that if D is an 539 arbitrary canonical system, there is no change in any argument, except for slightly more 540 tedious notations such as s = (0,…,0,q − r,0,q) instead of s = (q − r,0,q). Q.E.D.
541
542 As a result of this theorem, we conclude that the US currency system (21) is uniquely 543 canonical.
544 ¶15. Historical Notes. Chang and Gill [3] seems to be the first to study the coin change 545 problem algorithmically. Kozen and Zaks characterized canonical system of up to order m = 3
546 [6], and our Type A and Type B extensions have roots there. Cai and Zheng [2] characterized 547 canonical systems of order up tom = 5.
548
549 Exercises
550 Exercise 2.1: In a certain country, its currency system was originally D =
551 [1,5,10,25,50,100Add ,200]. A new king came along. As a mathematician, he wanted
552 to honor π = 3.1415··· and so he decreed a new denomination 314. Is the new currency
553 system canonical? ♦
554 Exercise 2.2: A certain sovereign state had a complete and canonical currency system D = 555 (d1,…,dm). After a period of hyper-inflation, the state decreed that its pennies (d1 = 1) 556 are no longer legal currency. Is the new currency still canonical? What if the next
557 denomination d2 is also no longer legal? ♦
Exercise 2.3: In 1971, the British denomination converted to a decimal system. The old system has these denominations:
12(=shilling),24(=florin),30(=half-crown),60(=crown),240(=pound).
558
559 (a) Show that the old system in non-canonical.
560 (b) Determine the largest possible value of Grd(x) − Opt(x) in the old system. ♦
Yogi Berra was referring to this in
561 Exercise 2.4: Show by a direct argument that the binary system D = (1,2,4,…,2m) is a the introductory 562 canonical system that is also unique. Direct argument means to avoid quoting our theorem quote!
563 on extensions. ♦

564 Exercise 2.5: (Kozen-Zaks)
565 (a) Let D = [1,d2,d3] where d3 = qd2 + r and 0 ≤ r < d2. Show that (q + 1)d2 is the 566 minimum counter example.
567 (b) If D = [1,d2,…,dm] is non-canonical, the minimum counter example s = (s1,…,sm)
568 satisfies s3 < x < sm−1 + sm. ♦
Exercise 2.6: (Panagiotis Karras) The following problem arises in “compressing databases”. We are given a sequence w = (w1,…,wn) of numbers and some > 0. We say a sequence x = (x1,…,xm) is an -approximation of w of order m if there is a sequence of m breakpoints (as in (4))
0 = t(0) < t(1) < t(2) < ··· < t(m) = n
such that for each original number wi, the unique xj (j = 1,…,m) such that t(j − 1) < i ≤ t(j)
provides an -approximation to wi in the sense that

569 Intuitively, this says that we can approximate the sequence w by a histogram with m
570 steps. Let) denote the minimum order of an -approximation of w. Design and
571 prove an O(n) greedy algorithm to compute the♦
572 Exercise 2.7: Suppose that our supermarket checkout suddenly ran out of quarters. All the
573other denominations remain available.
574 (a) Is the greedy algorithm still optimal?
575 (b) More generally, we say a canonical currency system D = [d1,…,dm] is robust if 576 it remains
canonical under the loss of any single denomination di. Is the US currency
577 system robust? Add ♦
578 End Exercises
579 §3. Interval Problems
580 An important class of greedy algorithms involves intervals. Typically, we think of an interval 581 I ⊆ R as a time interval, representing the duration of some activity.
582 ¶16. Intervals as Activities. We will use half-open intervals of the form I = [s,f) where 583 s < f to represent an activity that starts at time s and finishes before time f. Recall that [s,f) 584 is the set {t ∈ R : s ≤ t < f}, (we might say our activity intervals are “open ended”). Two 585 activities conflict if their time intervals are not disjoint. We use half-open intervals instead of 586 closed intervals so that the finish time of an activity can coincide with the start time of another 587 activity without causing conflict. A set S = {I1,…,In} of intervals is said to be compatible 588 if the intervals in S are pairwise disjoint (i.e., the activities in S are mutually conflict-free).
589 We begin with the activities selection problem, originally studied by Gavril. Imagine 590 you have the choice to do any number of the following fun activities in one afternoon:
591
beach 12 : 00 − 4 : 00, swim 1 : 15 − 2 : 45, tennis 1 : 30 − 3 : 20,
movie 3 : 00 − 4 : 30, movie 4 : 30 − 6 : 00.
You are not allowed to do two activities simultaneously. Assuming that your goal is to maximize your number of fun activities, which activities should you choose? Formally, the activities selection problem is this: given a set
S = {I1,I2,…,In}
592 of intervals, compute a compatible subset of S that is optimal. Here optimal means “of maximum
593 cardinality”. E.g., in the above fun activities example, an optimal solution would be to swim
594 and to see two movies. It would be suboptimal to go to the beach. What would a greedy 595 algorithm for this problem look like? Here is a generic version:
596
597
Generic Greedy Activities Selection:
Output: A ⊆ S, a set of compatible intervals .
Initialization
Sort S according to some numerical criterion.
Let (I1,…,In) be the sorted sequence. Let A = ∅.
. Main Loop
For i = 1 to n
If A ∪ {Ii} is compatible, add Ii to A Return(S)
598
599 Thus, A is a partial solution that we are building up. At stage i, we consider interval Ii, to 600 either accept or reject it. Accepting means to make it part of current solution A.
601 But what greedy criteria should we use for sorting? As usual, ties are broken arbitrarily. 602 Here are four possibilities. Notice that we say “sort in increasing order”, instead of the more 603 accurate “sort in non-decreasing’ order’. I prefer this direct formulation, always assuming that 604 ties are broken arbitrarily.
605 (a) Sort Ii’s in order of increasing finish times: 606 swim, tennis, beach, movie 1, movie 2
607 (b) Sort Ii’s in order of increasing start times:
608 beach, swim, tennis, movie 1, movie 2
609 (c) Sort Ii’s in order of duration where the duration of activity Ii is fi − si. Note that movie
610 1, movie 2 and swim are tied, but breaking ties arbitrarily: My class (Fall 2011)
611 movie 1, movie 2, swim, tennis, beach voted on which
criteria yield an
612 (d) Sort Ii’s in order of increasing conflict degree. optimal solution.
613 The conflict degree of Ii is the number of Ij’s which conflict with Ii. If the conflict degree
Tally: (a) 11, (b) 0, 614 of Ii is zero, clearly we can always add Ii into our set. Thus the ordering is: (c) 16, (d) 20.
615 movie 2, movie 1 or swim, beach or tennis Wisdom of the crowd?
616 We can combine these criteria: e.g., if one criterion leads to a tie, we can use use another 617 criterion to break ties. We now show that the first criterion (sorting by increasing finish 618 times) leads to an optimal solution. In the Exercises, you will provide counter examples to 619 the optimality of the other three criteria. Because of the possibility of ties, we distinguish two 620 kinds of counter examples: “strong” counter examples do not depend on how ties are broken 621 and “weak” ones that depend on how ties are broken.
f1 < f2 < ··· < fk.
Suppose ) is an optimal solution where Ii∗ = [s∗i ,fi∗) and again ··· < f`∗. By optimality ofA∗, we have k ≤ `. CLAIM: We have the inequality fi ≤ fi∗
for all i = 1,…,k. We leave the proof of this CLAIM to the reader. Let us now derive a contradiction
if the greedy solution is not optimal: non-optimality of the greedy solution means k < `. Therefore the interval Ik∗+1 is defined. Then
fk ≤ Add fk (by CLAIM)
≤ s∗k+1 (Ik∗+1 is defined and have no conflict)
622 and so is compatible with {I1,…,Ik}. This is a contradiction since the greedy algorithm 623 halted after choosing Ik – it could have continued with Ik∗+1.
624 What is the running time of this algorithm? In deciding if interval Ii is compatible with the 625 current set A, it is enough to only look at the finish time f of the last accepted interval. This 626 can be done in O(1) time since this comparison takes O(1) and f can be maintained in O(1) 627 time. Hence the algorithm takes linear time after the initial sorting.
628 ¶17. Extensions, variations. There are many possible variations and generalizations of 629 the activities selection problem. Some of these problems are explored in the Exercises.
630 • Suppose your objective is not to maximize the number of activities, but to maximize 631 the total amount of time spent in doing activities. In that case, for our fun afternoon 632 example, you should go to the beach and see the second movie.
633 • Suppose we generalize the objective function by adding a weight (“pleasure index”) to 634 each activity. Your goal now is to maximize the total weight of the activities in the 635 compatible set.
636 • We can think of the activities to be selected as a uni-processor scheduling problem. (You 637 happen to be the processor.) We can ask: what if you want to process as many activities 638 as possible using two processors? Does our original greedy approach extend in the obvious 639 way? (Find the greedy solution for processor 1, then find greedy solution for processor
640 2).
641 • Alternatively, suppose we ask: what is the minimum number of processors that suffices 642 to do all the activities in the input set?
649
650 Exercises
651 Exercise 3.1: The text gave four
different greedy criteria (a)-(d) for the activities selection
652 problem.
653 (i) Show that (b), (c), (d) are suboptimal using “strong” counter examples (we prefer
Draw your counter 654 visualized intervals). Extra credit if (b), (c), (d) are shown with the same set of activities. examples! 655 How small can this set of activities be?
656 (i) Each of the criteria (a’)-(d’) have an inverted version in which we sort in decreasing
657 order. Again, one of these inverted criteria is optimal, and the other three suboptimal. 658 Prove the optimality of one, and provide counter examples for the other three. ♦ Add
659 Exercise 3.2: Suppose the input S = (I1,…,In) for the activities selection problem is already 660 sorted, by increasing order of their start times, i.e., s1 ≤ s2 ≤ ··· ≤ sn. Give an algorithm
661 to compute a optimal solution in O(n) time.
Show that your algorithm is correct.
♦
Exercise 3.3: Consider the activities selection problem. Let S = {I1,…,In} be a set of activities where each activity Ii = [si,fi) is a half-open interval. We want to find a compatible set A ⊆ S which maximizes the length |A| where
|A|:= X |I|
I∈A
662 and |Ii|:=fi − si. Denote
by Opt(S) the maximum length of A ⊆ S.
663 Let Si,j = {Ii,Ii+1,…,Ij} for
i ≤ j and Opti,j
:=Opt(Si,j).
664 (a) Show by a counter example that the following algorithm does not work:
Opti,j = max{Opti,k + Optk+1,j : i ≤ k ≤ j − 1} (25)
666 (b) Give an O(nlogn)
algorithm for computing Opt1,n.
667 HINT: order the activities in the set S according to their finish times.
668 ♦

669 E
x e r
ci
s
e 3.
4
:
G iv e a d
iv
i
d
e
– a n d
– c o n q u
e
r
al g o
ri
t h
m f
o r
t h
e
p
r o b a 676 of play si time. b 677 (b) le Suppose
s there is a o n player l game that u lasts t ti minutes. o Again, any
n number
f of players o 678 can
r be
a swapped
s at any e time.
t There are S m friends
o who
f wants to a play this c game.
ti Prove 679 v that there it is always
ie a
T friend h have the is same a amount of p playtime.
p 680 (c) Design
r an
671 harder and less efficient!) ♦ every one
has the same
672 Exercise 3.5: Interval problems often arises from scheduling. 681 amount of
673 (a) There is a 5 player game that lasts 48 minutes. In this game, any number of players 674 play time.
can be swapped at any time. Suppose there are 8 friends what wants to play this game. 675 ♦

682 End Exercises 683 §4.
Huffman Code
684 The problem of compressing information is central to computing and information processing. 685 We shall study one problem whose solution is based on the greedy paradigm.
686 ¶18. An Encoding Problem.Add It is best to begin with an informally stated problem:
687 (P) Given a string s of characters (or letters or symbols) taken from an alphabet 688 Σ, choose a variable length code C for Σ so as to minimize the space to encode the 689 string s.
Casc : Σ → {0,1}8 . (26)
701 Problem (P) suggests the use of variable length code to take exploit the relative frequency 702 of characters in Σ. For instance, in typical English texts, the letters ‘e’ and ‘t’ are most frequent 703 and it is a good idea to use shorter codes for them. On the other hand, infrequent letters like 704 ‘q’ or ‘z’ could have longer codes. According to some statistics (see §5, Exercises), the relative 705 frequencies of ‘e’, ‘t’, ‘q’, ‘z’ are 12.02,9.10,0.11,0.07, respectively. An example of a variable 706 length code is Morse code (see Notes at the end of this section). To see what additional 707 properties are needed in variable-length codes, let us give some definitions:
A (binary) code for Σ is an injective function
C : Σ → {0,1}∗.
698 This code is a fixed-length binary code:
|Casc(x)| = 8 for all x ∈ Σ. So the ASCII encode of a
699 file of m characters is a binary string of length 8m. Can we do better, i.e., can we choose a 700 different code that uses less than 8m bits?
Basically, this is the problem of data compression.
Gauss appears to be referring to a kind of data compression or removing redundancy in the epigraph of this Chapter

708 A string of the form C(x) (x ∈ Σ) is called a code word. The string s = x1x2 ···xm ∈ Σ∗ is 709 then encoded as
C(s):=C(x1)C(x2)···C(xm) ∈ {0,1}∗. (27)
710 This raises the problem of decoding C(s), i.e., recovering s from C(s). For a general code C
711 and s, we cannot expect unique decoding. A basic requirement for decodability is the ability to 712 detect the boundary between code words in C(s). One solution is to introduce a new symbol 713 ‘$’ and insert it between successive C(xi)’s. If we insist on the binary alphabet for the code,

715 bits, probably wasteful.
716 ¶19. Prefix-free codes.Our preferred solution for unique decoding is that C be prefix-
717 free. This means that if a,b ∈ Σ are distinct letters then C(a) is not a prefix of C(b). Clearly, 718 this ensures unique decoding. With suitable preprocessing (basically to construct the “code 719 tree” for C, defined next) decoding can be done quite simply, in an on-line fashion.
720 We represent a prefix-free codeAdd C by an external binary tree TC with |Σ| leaves. Each leaf
721 in TC is labeled by a character b ∈ Σ such that the path from the root to b is encoded by C(b) 722 in the natural way: the path length has length |C(b)|, with the 0-bit (resp., 1-bit) representing 723 a left (resp., right) branch. We call TC a code tree for C.
724 Figure 2 shows two such trees representing prefix codes for the alphabet Σ = {a,b,c,d}. 725 The first code, for instance, corresponds to C(a) = 00, C(b) = 010, C(c) = 011 and C(d) = 1.
c b
COST=11+9+3=23 COST=11+5+3=19
Figure 2: Code trees for two prefix-free codes: assume f(a) = 6, f(b) = 2, f(c) = 1 and f(d) = 2.
730 (P), we can now interpret this problem as the construction of the best prefix-free code C for s, 731 i.e., the code that minimizes the length |C(s)| of C(s). Clearly, the only statistics important 732 about s is the frequency fs(x) of each letter x in s, i.e., the number of occurrences of x in s. 733 In general, call a function9 of the form
f : Σ → N (28)
734 a frequency function. So we now regard the input data to our problem to be a frequency 735 function f = fs rather than the string s. Relative to f, the cost of C is defined to be
COST(f,C):= X |C(a)| · f(a). (29)
a∈Σ
Clearly COST(fs,C) is the length of C(s). Finally, the cost of f is defined by minimization over all choices of C:
COST(f):= minCOST(f,C)
C
736 over all prefix-free codes C on the alphabet Σ. A code C is optimal for f if COST(f,C) 737 attains this minimum. It is easy to see that an optimal code tree must be a full binary tree 738 (i.e., non-leaves must have two children).
739 Consider a simple example10 where s is “abadacadaba” So Σ = {a,b,c,d} with frequencies
740 of the characters a,b,c,d equal to 6,2,1,2 (respectively). For the codes in Figure 2, the cost of 741 the first code is 6 · 2 + 2 · 3 + 1 · 3 + 2 · 1 = 23. The second code is better, with cost 19.
742 ¶20. Huffman Code Algorithm. We can now restate the informal problem (P) as the 743 precise
Huffman coding problem: Add
744
(H) Given a frequency function f : Σ → N, find an optimal prefix-free code
C for f.
745 Relative to a frequency function f on Σ, we associate a weight W(u) with each node u of 746 the code tree TC: the weight of a leaf is just the frequency f(x) of the character x at that leaf, 747 and the weight of an internal node is the sum of the weights of its children. Let Tf,C denote 748 such a weighted code tree. In general, a weighted code tree is just a code tree together with 749 weights on each node satisfying the property that the weight of an internal node is the sum of 750 the weights of its children. For example, see Figure 2 where the weight of each node is written 751 next to it. The weight of Tf,C is the weight of its root, and its cost COST(Tf,C) defined as 752 the sum of the weights of all its internal nodes. In Figure 2(a), the internal nodes have weights 753 3,9,11 and so the COST(Tf,C) = 3 + 9 + 11 =
COST(f,C) = COST(Tf,C). (30)
9Sometimes, frequency is regarded as a fraction between zero and one. But we view it as an counting value: perhaps “census function” is a better term here.
10Regard it as toddler’s version of the incantation “abracadabra” or its more palindromic form “abradacadabra” The palindromic nature on this incantation is supposed to be part of the magic.
759 We now present a greedy algorithm for the Huffman coding problem:
760
761
762
Huffman Code Algorithm:
Input: Frequency function f : Σ → N.
Output: Optimal code tree T∗ for f.
1. Let Q be a set of weighted code trees. Initially, Q has n = |Σ| trivial trees, each with only one node representing a single character in Σ.
2. While Q has more than one tree,
2.1. Extract T,T0 ∈ Q of minimum and next-to-minimum weights.
2.2. Merge T,T0 and insert the result T + T0 into Q.
3. Now Q has only one tree T∗. Output T∗.
763
764 A Huffman tree is defined as a weighted code tree that could be output by this algorithm. 765 We say “could” because the
Huffman code algorithm is nondeterministic – when two trees have
767 is non-Huffman because its node of weight 9 cannot be a result of the Huffman algorithm; 768 however, the second tree in Figure 2(b) is Huffman.
letter h e l o t w r d !
frequency 1 1 3 2
wc W e1
o 1 1 1
arrays:
770
771
772 Note that the exclamation mark (!) and blank space (t) are counted as letters in the alphabet
773 Σ. The final Huffman tree is shown in Figure 3. The number shown inside a node u of the tree 774 is the weight of the node. This is just sum of the frequencies of the leaves in the subtree at u.
775 Each leaf of the Huffman tree is labeled with a letter from Σ.

Figure 3: Huffman Tree for “hello world!”: weights are inside each node, but ranks (0,1,…,16) are beside the nodes.
776 Figure 3 shows the Huffman tree produced by our algorithm on our famous string. In 777 addition, we display, next to each node, its “rank” (0,1,2,…,16). The rank of a node specifies 778 the order in which nodes were extracted from the priority queue. For instance, the leaves h 779 (rank 0) and e (rank 1) were the first two to be extracted in the queue. Their merge produced 780 a node of rank 8. Note that the root is the last (rank 16) to be extracted from the queue. 781 With this rank information, we can retrace the step-by-step execution of the Huffman code
782 algorithm. In the next section, we will exploit rank information in a more significant way. For 783 the time being, we draw Huffman trees without paying much attention to its “orientation” i.e.,
784 the ordering of the 2 children of an internal node. When we treat dynamic Huffman tree in the 785 next section, we will start paying attention to this issue. E.g., in Figure 3, the left child of the 786 root has rank 15. Thus the Huffman code for the letter ` is 00. But we could also let the node 787 of rank 14 be the left child of the root (this will be required in dynamic Huffman trees). The 788 Huffman code of ` is then 10.
795 item with smallest key.The frequency of the code tree serves as its key. Any balanced binary
798 Now that we have constructed the code tree, let us see how to use it for coding and decoding.
799 Decoding is easy: just start from the root of T, we follow a path to a leaf by turning left or 800 right according to the scanned bits. Once we read a leaf, we can output the character stored 801 at the leaf, and start again at the root. What about using T for encoding a string s ∈ Σ∗? 802 For each a ∈ Σ, we need to determine the code word C(a) ∈ {0,1}∗. How could we do it? We
803 must assume a separate “character map”Add Cm that takes each a ∈ Σ to the corresponding leaf
804 in T. Then by following parent pointers from Cm(a) to the root, we obtain the code word (in 805 reverse).
806 But the code tree T will be used for determining the code word C(a) for each a ∈ Σ. 807 The weights are no longer relevant. Instead T is viewed as an external BST in the sense 808 of ¶III.33. Why? Recall that we want to convert our input string s = x1 ···xm into the 809 binary string C(s) = C(x1)···C(xm) as in (27). For each xi, we use T to compute C(xi) 810 as follows: do a binary search for xi in T, and output a 0 (resp., 1 for each comparison that 811 makes us turn left (resp., right). Hence we must modify the above Huffman tree algorithm to 812 construct such an external BST. Recall (§III.5) that if v is an external node of such a BST, 813 then v.left.key = v.key and v.left is a pointer to the predecessor of v (if it exists). Suppose 814 TL and TR are two external BST’s to be merged. We take these steps to create the desired 815 merger:
816 • Create a new node u.
817 • Make TL and TR the left and right subtrees of u.
818 • If v is the minimum external node of TR, then v.left ← u, and u.key ← v.key.
819 ¶22. Correctness. We show that the produced code C has minimum cost. This depends 820 on the following simple lemma. Let us say that a pair of nodes in TC is a deepest pair if they 821 are siblings and their depth is equal to the depth of TC. In a full binary tree, there is always a 822 deepest pair.
823 Lemma 9 (Deepest Pair Property) For any frequency function f, there exists a code tree 824 T that is optimal for f, with the further property that T has a deepest pair b,c where b is some 825 least frequent character, and c is some next-to-least frequent character.
826
827 Proof. The proof follows from a simple observation: suppose a and b are two leaves in T
828 such that the depth of a is at most the depth of b: D(a) ≤ D(b). If their frequencies satisfy 829 f(a) ≤ f(b), then we can exchange a ↔ b in the tree without increasing its cost, COST(f,T). 830 If T is optimal for f, the exchange will preserve optimality. By making two such exchanges in 831 an initially optimal T, we produce an optimal tree with the desired “deepest pair” property.
832 Q.E.D.
833
834 Note that this lemma does not claim that every optimal code tree has the deepest pair
835property. See Exercise for a counter example.
836 We are ready to prove the correctness of Huffman’s algorithm. Suppose by induction hy-
837 pothesis that our algorithm produces an optimal code whenever the alphabet size |Σ| is less 838 than n. The basis case,n = 1, is trivial. Now suppose |Σ| = n > 1. After the first step of the
839 algorithm in which we merge the two least frequent characters b,b0, we can regard the algorithm 840 as constructing a code for a modified alphabet Σ0 in which b,b0 are replaced by a new character
841 [bb0] with modified frequency f0 such that f0([bb0]) = f(b) + f(b0), and f0(x) = f(x) otherwise. 842 By induction hypothesis, the algorithm produces the optimal codeAdd C0 for f0:
COST(f0) = COST(f0,C0). (31)
843 From the code C0, we can obtain a code C for Σ as follows: the code tree TC is obtained 844 from TC0 by replacing the leaf [bb0] by an internal node with two children representing b and b0, 845 respectively. Thus we have
COST(f,C) = COST(f0,C0) + f(b) + f(b0). (32)
846 By our deepest pair lemma, and using the fact that the COST is a sum over the weights of 847 internal nodes, we conclude that
COST(f) = COST(f0) + f(b) + f(b0). (33)
848 [More explicitly, this equation says that if T is the optimal weighted code tree for f and 849 T has the deepest pair property, then by removing the deepest pair with weights f(b) and 850 f(b0), we get an optimal weighted code tree for f0.] From equations (31)–(33), we conclude 851 COST(f) =
COST(f,C), i.e., C is optimal.
852 ¶23. Representation of the Code Tree for Transmission. Suppose I want to send 853 you the string s. It is not enough to send you its code C(s). I must also send you some 854 representation of the code tree TC. Let this representation be a binary string αC. We will now 855 provide one description of αC that is essentially optimal in its length. We split the binary αC 856 into two parts:
αC = βCγC (34)
857 where βC encodes the ”shape” of the code tree TC, and γC is just a list of the characters in Σ, 858 in the order they appear as leaves of TC.
862 Σ is a subset of Σ0. For the present purposes, assume Σ0 ⊆ {0,1}N for some fixed N. This 863 N is the common knowledge used by both the transmitter and receiver. As a practical matter, 864 it is important that we allow Σ to be a proper subset of Σ0. Typically, Σ is just the set of 865 characters that actually occur in the string we are transmitting.
866 E.g., Let C be Huffman code in Figure 2(b), Σ0 be the extended ASCII set (so N = 8). If Σ =
867 {a,b,c,d}, then the codes for these letters in hexadecimal are a=0x61,b=0x62,c=0x63,d=0x64
868 (see Figure 8 in the next section). Therefore γC = 0x61626364. In full glory, γC = 869 0110’0001’0110’0010’0110’0011’0110’0100.
870 It remains to explain the string βC in (34). We give a progression of ideas that lead to the 871 final form. The initial idea is simple: let us prescribe a systematic way to traverse T. Starting
872 from the root, we use a depth-first traversal, always go down the left child first. Each edge is
873 traversed twice, initially downward and later upward. Then if we “spit” out a 0 for going down
874 an edge and “spit” out a 1 for going up an edge, we would have faithfully output a description
875 of the shape of T by the time we return to the root for the second time. Figure 4 illustrates 876 this traversal of the Huffman tree of Figure 2(a), and shows resulting binary sequence
0010’0101’1101. (35)
4n − 4 = 12 bits
878 scheme uses 2 bits per edge. If there are n leaves, there are n−1 internal nodes. Each internal 879 nodes are associated with 2 outgoing edges, giving 2Add n − 2 edges. Each edge gives rise to 2
880 bits, and so the representation has 4n − 4 bits. We emphasize: this representation depends on
Where have we 881 knowing that T is a full binary tree. exploited this fact?

Figure 4: Compressed bit representation for the Huffman tree Figure 2a
882 Another remark is this: this encoding is self-limiting in the sense that, if we know the 883 beginning of the encoding, then we would know when we have reached the end of the encoding. 884 This property is useful for many applications; in particular, we need this property in (34): we 885 must know when βC ends, and γC begins.
886 To improve this representation, observe that a contiguous sequence of ones can be replaced 887 by a single 1 since we know where to stop when going upward from a leaf (we stop at the first 888 node whose right child has not been visited). This also takes advantage of the fact that we 889 have a full binary tree. Previously we used 2n − 2 ones. With this improvement, we only use 890 n ones (corresponding to the leaves). The representation now has only 3n − 2 bits. Then (35) 891 is now represented by
0010’0101’01. (36)
892 Finally, we note that each 1 is immediately followed by a 0 (since the 1 always leads us to a
3n − 2 = 10 bits
893 node whose right child has not been visited, and we must immediately go down to that child). 894 The only exception to this rule is the final 1 when we return to the root; this final 1 is not
895 followed by a 0. We propose to replace all such 10 sequences by a plain 1. Since there are n
How about 01 → 1?
896 ones (corresponding to the n leaves), we would have eliminated n − 1 zeros in this way. This 897 gives us the final representation with 2n − 1 bits. The scheme (36) is now shortened to:
0010’111. (37)
898 See the final illustration in Figure 4. The final scheme (37) will be known as the compressed 899 bit representation βT of a full binary tree T. In case T is the code tree for a Huffman code 900 C, βT is the desired βC of (34).
901 If T has more than one leaf, βT will begin with a 0 and end with a 1. Since we assume |Σ| ≥ 2, 902 the shortest bit string is 011, represent a full binary tree with two leaves. For completeness, we 903 will define βT= 1 for the tree T with only one leaf. The following lemma summarizes several 904 simple properties:
905 Lemma 10 Let T be a full binary tree T with n ≥ 1 leaves, and βT is its compressed bit
906representation.
907 (i) The length of βT is 2n − 1, with n − 1 zeros and n ones. 908 (ii) In any proper prefix of βT, the number of zeros is at least the number of ones.
∗
909 (iii) The set S ⊆ {0,1} of all such compressed bit representations βT forms a prefix-free set. 910 (iv) There is a linear time algorithm that checks whether a given binary stringAdd s belongs to the
911 set S, i.e., if s has the form βT for some T.
912 We leave the proof as an Exercise. This has the following application:

913 Theorem 11 There is a protocol to transmit a binary string αC representing any Huffman
∗
914 code C : Σ → {0,1} on |Σ| = n letters such that 915 (i) The length of αC is (2n − 1) + Nn = n(N + 2) − 1.
916 (ii) A receiver can recover the code C from αC in linear time, without prior knowledge of Σ 917 except that Σ ⊆ Σ0 ⊆ {0,1}N.
918
919 Proof. Using the notation of (34), αC = βCγC where |βC| = 2n − 1 when the code tree TC
920 has n leaves, and |γC| = nN under our assumption that Σ ⊆ Σ0 ⊆ {0,1}N. This proves 921 (i). For part (ii), the receiver can use the prefix-free property of αC to detect the end 922 of αC while processing βC. In linear time, it reconstruct the shape of TC and thus knows 923 n. Since the receiver knows N, he can also parse each symbol of Σ in the rest of βC. Q.E.D.
924
925 ¶24. Canonical Huffman Trees. full binary tree is said to be canonical if in each level, 926 all the leaves appear to the left of all the internal nodes. Thus the first tree in Figure 2 is
2n − 1 = 7 bits

927 non-canonical, but the second is canonical. If a full binary tree is non-canonical, we can try to
928 make it canonical by swapping: pick any two nodes u,v at the same level. We totally order 929 the nodes in a given level using “u < v” if u is to the left of v. If u < v where u is internal and 930 v is external, we call (u,v) an inverted pair. Hence T is canonical iff there are no inverted 931 pairs. We define the Swap(u,v) operation in which the the subtrees Tu,Tv rooted at u and v
932 are swapped. This can be implemented with two pointer assignments. If u,v are in level ` ≥ 1,
933 then:
934 (i) The number of inverted pairs at levels < ` is unchanged.
935 (ii) The number of inverted pairs at level ` strictly decreases.
936 (iii) COST(T) is invariant under such swaps.
937 By repeated swaps, we can obtain a canonical tree (Exercise). For example, the tree in Fig938 ure 2(a) is noncanonical: at level 1, the leaf d appears after the internal node 9. After swapping 939 them, the tree become canonical. Likewise, the tree in Figure 2(b) can be made canonical with 940 one swap. The tree in Figure 3 is a canonical (despite the way we draw all leaves at the “same” 941 level).
942 Canonical trees has a self-limiting encoding that uses only n+2 bits where n is the number of
943 leaves (Exercise). We want to exploit this in the preceding lemma on αC. Suppose T is Huffman 944 tree. We note that swaps does not change the cost of the code tree (it is less clear whether swaps
945 preserves Huffman-ness of trees). By repeated swaps, we finally reach a “canonical Huffman
946tree”. In the exercises, we show that the encoding of canonical trees can be further improved.
947 TO BE COMPLETED:
948 Remarks: The publication of the Huffman algorithm in 1952 by D. A. Huffman was con-
949 sidered a major achievement. This algorithm is clearly useful for compressing binary files. 950 See “Conditions
for optimality of the Huffman Algorithm”, D.S. Parker (SIAM J.Comp.,
952 characterizations of the cost functions for which the Huffman algorithm remains valid. Ac-Add 951 9:3(1980)470–489, Erratum 27:1(1998)317), for a variant notion of cost of a Huffman tree and
953 cording to Adam Gashlin the encodings of canonical Huffman trees are used in Audio-Video 954 compression applications.
955 ¶25. Notes on Morse Code. In the Morse code, letters are represented by a sequence of dots 956 and dashes: a = · −, b = − · · · and z = − − · ·. The code is also meant to be sounded: dot is
957 pronounced ‘dit’ (or ‘di-’ when non-terminal), dash is pronounced ‘dah’ (or ‘da-’ when nonterminal). 958 So the famous distress signal “S.O.S” is di-di-di-da-da-da-di-di-dit. Thus ‘a’ is di − dah, ‘z’ is 959 da − da − di − dit. The code does not use capital or small letters. Here is the full alphabet:
960 Note that Morse code assigns a dot to e and a dash to t, the two most frequent English letters. 961 These two assignments dash any hope for a prefix-free code. So how can do you send or decode messages 962 in Morse code? Spaces! Since spaces are not part of the Morse alphabet, they have an informal status 963 as an explicit character (so Morse code is not strictly a binary code). There are 3 kinds of spaces: 964 space between dit’s and dah’s within a letter, space between letters, and space between words. Let us 965 assume some unit space. Then the above three types of spaces are worth 1, 3 and 7 units, respectively. 966 These units can also be interpreted as “unit time” when the code is sounded. Hence we simply say 967 unit without prejudice. Next, the system of dots and dashes can also be brought into this system. We 968 say that spaces are just “empty units”, while dit’s and dah’s are “filled units”. dit is one filled unit, 969 and dah is 3 filled units. Of course, this brings in the question: why 3 and 7 instead of 2 and 4 in the 970 above? Today, Morse code is still required of HAM radio operators and is useful in emergencies.

A · − B − · · ·
C − · − · D − · ·
E · F · · − ·
G − − · H · · · ·
I · · J · − − −
K − · − L · − · ·
M − − N − ·
O − − − P · − − ·
Q − − · − R · − ·
S · · · T −
U · · − V · · · −
W · − − X − · · −
Y − · − − Z − − · ·
0 − − − − − 1 · − − − −
2 · · − − − 3 · · · − −
4 · · · · − 5 · · · · ·
6 − · · · · 7 − − · · ·
8 − − − · · 9 − − − − ·
Fullstop (.) · − · − · − Comma (,) − − · · − −
Query (?) · · − − · · Slash (/) − · · − ·
BT (pause) − · · · − AR (end message) · − · − ·
SK (end contact) · · · − · −
Table 1: Morse Code 971 Exercises
972 Exercise 4.1: Let s be the following string: “hello!tthististmytlittletworld!”. Show 973 the Huffman codeC for s, and what is |C(s)|? ♦
974 Exercise 4.2: What is the length of the Huffman code for the string s =
975 “please compress me00. Show your hand computation. Do not forget the empty space
976character. Add ♦
977 Exercise 4.3: Consider the following letter frequencies:
a = 5,b = 1,c = 3,d = 3,e = 7,f = 0,g = 2,h = 1,i = 5,j = 0,k = 1,l = 2,m = 0, n = 5,o = 3,p = 0,q = 0,r = 6,s = 3,t = 4,u = 1,v = 0,w = 0,x = 0,y = 1,z = 1.
980 Exercise 4.4: Give an example of a prefix-free code C : Σ → {0,1}∗ and a frequency function 981 f : Σ → N with the property that (i) COST(C,f) is optimal, but (ii) C could not have
982 arisen from the Huffman algorithm. Try to minimize |Σ|. ♦
983 Exercise 4.5: True or False? If T and T0 are two optimal prefix-free code for the frequency
984 function f : Σ → N, then T and T0 are isomorphic as unordered trees. Prove or show 985 counter example. NOTE: a binary tree is an ordered tree because the two children of a
986 node are ordered. ♦
987 Exercise 4.6: The text proved that for any frequency function f, there is an optimal code 988 tree in which there is a deepest pair of leaves whose frequencies are the least frequent and 989 the next-toleast frequent. Consider this stronger statement: if T is any optimal code tree 990 for f, there must be a deepest pair whose frequencies are least frequent and next-to-least
991 frequent. Prove it or show a counter example. ♦ 992 Exercise 4.7: Let C : Σ → {0,1}∗ be any prefix-free code whose code tree TC is a full-binary 993 tree. Prove that there exists a frequency function f : Σ → N such that C is optimal. ♦
Exercise 4.8: (a) Draw the full binary tree corresponding to its compressed bit representa- tions: α1 = 0010011000101101 α2 = 010001001000110111
994 (b) What is βT where T is the full binary tree with 6 leaves and every right child is a
995 leaf.
996 (c) What is βT where T is the full binary tree with 6 leaves and every left child is a leaf. 997 (d) What is
βT where T is the complete binary tree with 8 leaves.
998 ♦
999 Exercise 4.9: Joe Smart suggested that we can slightly improve the compressed bit represen1000 tation of full binary trees on n leaves as follows: since the first bit is always 0 and the 1001 last bit is always 1, we can use only 2n − 3 bits instead of 2n − 1. What are some issues
1002 that might arise with this improvement? ♦
1003 Exercise 4.10: We define a ternary tree by analogy with a binary tree: it is either the empty 1004 tree with no nodes, or it has a unique node called the root. Each non-leaf has at most three
1005 children, each with a unique label, taken from the set{L,M,R} (corresponding to Left,
1006 Middle or Right child). The tree is full if each non-leaf has 3 children. In the following, 1007 let Tn denote a full ternary tree with exactly n ≥ 1 internal nodes. By definition, T0 is 1008 the tree with only one node. Be sure to justify your answers!
1009 (a) How many leaves doesAdd Tn have?
1010 (b) Describe the “compressed bit representation” of Tn by analogy with the case of full 1011 binary trees. We will write α(Tn) for this representation. (c) Please draw the full ternary tree represented by
‘0011’0111’1001’1111’
1012
1013 (d) How many bits are used in α(Tn)?
∗
1014 (e) Let A ⊆ {0,1} be the set of all compressed bit representation of full ternary trees. 1015 Characterize A. This means give a complete list of properties that determines A.
1016 ♦
1017 Exercise 4.11: Let T be a full binary tree on n leaves. Give an algorithm to
convert its
1018 compressed bit representation βT[1..2n − 1] to a 4n − 4 array B[1..4n −
4] representing
1019 the traversal of T.
♦
1020 Exercise 4.12:
Suppose we want to represent an arbitrary binary tree, not necessarily full. 1021 HINT: there is a bijection between arbitrary binary trees and full binary trees.
Exploit
1022 our compressed bit-representation of full binary trees. ♦
1023 Exercise 4.13: (a) Prove (30).
1024 (b) It is important to note that we defined COST(Tf,C) to be the sum of f(u) where u 1025 range over the internal nodes of Tf,C. That means that if |Σ| = 1 (or Tf,C has only 1026 one node which is also the root) then COST(Tf,C) = 0. Why does Huffman code 1027 theory break down at this point?
1028 (c) Suppose we (accidentally) defined COST(Tf,C) to be the sum of f(u) where u range 1029 over the all nodes of Tf,C. Where in your proof in (a) would the argument fail?
1030 ♦
1031 Exercise 4.14: (Kraft
Inequality) Let 0 ≤ d1 ≤ d2 ≤ ··· ≤ dn be the depths of the leaves in 1032 a binary tree with n leaves.
Prove that n
1 ≥ X2−di. (38)
i=1
1033 Moreover, if the binary tree is a full binary tree, then the inequality is an equality. ♦
1034 Exercise 4.15: (Elias) Let bin(n) denote the standard binary encoding of n ∈ N and 1035 len(n)be the length of this encoding. E.g., 100) and
1036 len(0,1,2,3,4) = (0,1,2,2,3). Here, is the empty string and we use the compact 1037 notation bin(n1,n2,…,nk):=(bin(n1),bin(n2),…,bin(nk)), etc.
1038 We want a binary encoding of natural numbers, rep : N → {0,1}∗, with the following prop-
1039 erty: if n1,n2,… is any sequence of natural numbers, the binary stringrep(n1)rep(n2)···
1040 is uniquely decodable. Such an encoding rep(n) is self-limiting in the sense that when-
1041 ever we know the start of rep(n), we can also determine where it ends. Alternatively, the 1042 representation is prefix-free: if n 6= n0 then rep(n) is not a prefix of rep(n0). 1043 (a) Consider the following encoding schemeAdd rep1 : N → {0,1} for natural numbers: ∗
1044 rep1(0) = 1 and for n ≥ 1, rep1(n) = 0len(n)bin(n). E.g., rep1(0,1,2,3,4) = 1045 (1,001,00010,00011,0000100). Note we use the prime mark (0) for decoration. What 1046 is rep1(99)? What is the length of rep1(n) as a function of n?
∗
1047 (b) Now consider rep2 : N → {0,1} where rep2(n) = rep1(len(n))bin(n) for n ≥ 0. E.g., 1048 rep2(0,1,2,3,4) = (1,0101,0010010,0010011,00110100). What is rep2(99)? What is 1049 the length of rep2(n) as a function of n?
(c) What is wrong with the suggestion to define rep(n) recursively as follows:
rep(n) = rep(len(n))bin(n)
1050 for all n ≥ n0 (for some n0)? How can you fix this issue? How small can n0 be, 1051 and what can you do for n < n0? What is the length of your representation as a 1052 function of n? What is your representation of 99? For what values of n will your 1053 representation be shorter than rep2(n)?
1054 ♦
1055 Exercise
4.16:
(Gashlin
2012) We
give a
further
improvem ent on the
encoding
of canonical 1056 Huffman
trees, using a radically different approach: instead of focusing on the leaves, we 1057 focus on the internal nodes. An integer
sequence of the form
n = (n0,n1,…,nd−1) (39)
1058 is called the profile of a full binary tree of depth d and at level i = 0,…,d−1, it has ni 1059 internal nodes.
1060 (a) Show that there is a bijection between canonical trees with N internal nodes and
1061 integer sequences of the form (39) that satisfies = 1 and 1 ≤ ni ≤ 2ni−1 1062 (i = 1,…,d − 1). 1063 (b) Let the leaf profile of a full binary tree of depth d be the sequence (`1,`2,…,`d) 1064 where `i is the number of leaves at level i = 1,…,d. Given the profile (39) of a full 1065 binary tree, what is the corresponding leaf profile?
1066 (c) Give a self-limiting encoding of profiles of canonical trees. HINT: use simple self1067 limiting encodings, but be sure we can detect the end of the encoding.
1068 (d) Give an upper bound on the number T(N) of canonical Huffman trees with N internal
1069 nodes.
1070 (e) Give a lower bound on T(N). ♦
1071 Exercise 4.17: Below is President Lincoln’s address at Gettysburg, Pennsylvania on Novem-
1072 ber 19, 1863.
1073 (a) Give the Huffman code for the string S comprising the first two sentences of the ad1074 dress. Also state the length of the Huffman code for S, and the percentage of compression 1075 so obtained (assume that the
1078 (b) The previous part was meant to be done by hand. Now write a program in your
1079 favorite programming language to compute the Huffman code for the entire Gettysburg 1080 address. What is the compression obtained?
1081 Four score and seven years ago our fathers brought forth on this continent
1082 a new nation, conceived in liberty and dedicated to the proposition that
1083 all men are created equal. Now we are engaged in a great civil war, testing 1084 whether that nation or
any nation so conceived and so dedicated can long 1085 endure. We are met on a great battlefield of that war. We have come to 1086 dedicate a portion of that field as a final resting-place for those who hereAdd
1087 gave their lives that that nation might live. It is altogether fitting and 1088 proper that we should do this. But in a larger sense, we cannot dedicate, 1089 we cannot consecrate, we cannot hallow this ground. The brave men, living 1090 and dead who struggled here have consecrated it far above our poor power to 1091 add or detract. The world will little note nor long remember what we say 1092 here, but it can never forget what they did here. It is for us the living 1093 rather to be dedicated here to the unfinished work which they who fought 1094 here have thus far so nobly advanced. It is rather for us to be here 1095 dedicated to the great task remaining before us — that from these honored 1096 dead we take increased devotion to that cause for which they gave the last 1097 full measure of devotion — that we here highly resolve that these dead 1098 shall not have died in vain, that this nation under God shall have a new 1099 birth of freedom, and that government of the people, by the people, for the 1100 people shall not perish from the earth.
1101 ♦
Exercise 4.18: Let (f0,f1,…,fn) be the frequencies of n+1 symbols (assuming |Σ| = n+1). Consider the Huffman code in which the symbol with frequency fi is represented by the ith code word in the following sequence
.
1102 (a) Show that a
sufficient condition for optimality of this code is f0 ≥ f1 + f2 + f3 + ··· + fn, f1 ≥ f2 + f3 + ··· + fn, f2 ≥ f3 + ··· + fn,
… fn−2 ≥ fn−1 + fn.
1103
1104 (b) Suppose the frequencies are distinct. Give a set of sufficient and
necessary conditions.
1105 ♦
1106 Exercise 4.19:
Suppose you are given the frequencies fi in sorted order. Show that you can
1107 construct the Huffman tree in linear time.
♦
1108 Exercise 4.20:
(Representation of Binary Trees) In the text, we showed that a full binary tree
1109 on n leaves can be represented using 2n − 1 bits. Suppose T is an arbitrary binary tree,
1110 not necessarily full.
With how many bits can you representT? HINT: by extending T
1111 into a full binary tree T0, then we could use the previous encoding on T0. ♦
1112 Exercise 4.21:
(Properties of Optimal Ternary Huffman Code)
1113 Huffman code is based on transmitting bits.
Suppose we transmit in ‘trits’ (a base-3 1114 digit).
Then the corresponding 3ary Huffman code C : Σ → {0,1,2}∗ is represented by a
1115 3-ary code tree T where each leaf is associated with a unique letter in Σ and each internal 1116 node has degree at most 3. IfAdd f : Σ → N is a frequency function, this assigns a weight to
1117 each node of T: the leaf associated with x ∈ Σ has weight f(x), and each internal node 1118 has a weight equal to the sum of the weights of its children. The cost of T is defined as 1119 usual, as the sum of the weights of the internal nodes of T. We are interested in optimal 1120 trees T, i.e., whose cost is minimum.
1121 (a) Show that in an optimal 3-ary code tree, there are no nodes of degree 1 and at most 1122 one node of degree 2. Furthermore, if a node has degree 2, then both its children 1123 are leaves.
1124 (b) Let T be an optimal tree whose internal nodes have degrees 2 or 3. If there are di 1125 nodes of degree i (i = 0,2,3) in T show that d0 = 1 + d2 + 2d3.
1130 ♦
1131 Exercise 4.22:
(Algorithm for Optimal Ternary Huffman Code)
1132 Ternary means that our code uses
Ternary Huffman Code Algorithm:
Input: Frequency function f : Σ → N.
Output: Optimal ternary code tree T∗ for f.
1. Let Q be a priority queue containing weighted code trees. Priority is determined by the weight of the root. Initially, Q is the set of n = |Σ| trivial trees, each tree with one node representing a single character in Σ.
2. If n is even,
T ← Q.deleteMin(), T0 ← Q.deleteMin().
Q.enqueue(Merge(T,T0))
3. While Q has more than one tree,
3.1. T ← Q.deleteMin(), T0 ← Q.deleteMin() T00 ← Q.deleteMin() 3.2. Q.enqueue(Merge(T,T0,T00).
4. Now Q has only one tree T∗. Output T∗.
1136
1137 ♦
1138 Exercise 4.23: Given the optimal ternary Huffman code C for strings s below. In each case,
1139 determine |C(s)|:
1140 (a) s =hellotworld!.
1141 (b) s
=hi!tmytlittletworl d!. ♦
1142 Exercise 4.24: We want to compare the relative efficiency of bits versus trits in Huffman
1143 coding. Let f : Σ → N be a frequency function. Suppose H2(f) is cost of f under the 1144 standard (binary) Huffman code; let H3(f) be the cost using a ternary Huffman code.
1145 We say “bits are better than trits” on f if H2(f) <
H3(f)lg(3) (and
conversely if the
1146 inequality goes the other way). Using the algorithm in the previous question to computeAdd 1147 H3(f), answer the question whether “bits are better than trits” for the following f’s: 1148 (a) Let f(a) = f(b) = f(c) = 1 (and f is zero on other characters).
1149 (b) Let f be the frequency function for compresstthistplease. ♦
1150 Exercise 4.25: We consider the 4-ary version of the previous question. Let T be an optimum 1151 4-ary code tree for some frequency function f : Σ → N.
1152 (a) Give a short inductive proof of the following fact: Suppose T is any 4-ary tree on 1153 n ≥ 1 leaves, and let Nd be the number of nodes with d children (d = 0,1,2,3,4).
1154 Thus, n = N0. Give a short inductive proof for the following formula: n = 1+N2 +
1155 2N3 + 3N4.
1156 (b) Show that if T is an optimal code tree, then N1 = 0 and 3N2 + 2N3 ≤ 4, and every 1157 non-full internal node has only leaves as children and the depth of these leaves must 1158 equal the height of of T.
1159 (c) Moreover, we can always transform T from part (b) into T0 such that the corre1160 sponding degrees satisfy = 0 and 1. Also, for any non-full internal 1161 node of T0, its children have weights no larger than any other leaves.
1162 (d) Suppose r = (n − 1)mod3. So r ∈ {0,1,2}. Show how in part (b) is 1163 determined by r. 1164 (e) Describe an algorithm to construct an optimal code tree from a frequency function
1165 f.
1166 (f) Show the optimal 4-ary Huffman tree for the input string hello world!. Please 1167 state the cost of this optimal tree.
1168 ♦
1169 Exercise 4.26:
Further generalize the 3-ary Huffman tree construction to arbitrary k-ary codes
1170 for k ≥ 4. ♦
1171 Exercise 4.27:
Suppose that the cost of a binary code word w is z + 2o where z (resp. o) is 1172 the number of zeros (resp. ones) in w. Call this the skew cost. So ones are twice as 1173 expensive as zeros (this cost model might be realistic if a code word is converted into a 1174 sequence of dots and dashes as in Morse code). We extend this definition to the skew 1175 cost of a code C or of a code tree. A code or code tree is skew
Huffman if it is optimum
1176 with respect to this skew cost. For example, see Figure 5 for a skew Huffman tree for alphabet {a,b,c} and f(a) = 3, f(b) = 1 and f(c) = 6.
c
1 6 a b
3 1
Figure 5: A skew Huffman tree with skew cost of 21.
1177
1178 (a) Argue that in some sense, there is no greedy solution that makes its greedy decisions 1179 based on a linear ordering of the frequencies.Add
1180 (b) Consider the special case where all letters of the alphabet has equal frequencies. 1181 Describe the shape of such code trees. For any n, is the skew Huffman tree unique?
1182 (c) Give an algorithm for the special case considered in (b). Be sure to argue its cor1183 rectness and analyze its complexity. HINT: use an “incremental algorithm” in which 1184 you extend the solution for n letters to one for n + 1 letters.
1185 ♦
1186 Exercise
4.28:
(Golin-
Rote) Further generalize
the
problem
in the
previous exercise. Fix 1187 0 < α < β and let the
cost of a
code word w be α · z + β · o.
Suppose α/β is a
rational 1188 number. Show a
dynamic
programm
ing
method
that takes O(nβ+2) time.
NOTE:
The 1189
best result
currently known
gets rid of the “+2” in the exponent, at the cost of two
1190 non-trivial ideas. ♦
1191 Exercise 4.29: (Open) Give a non-trivial algorithm for the problem in the previous exercise 1192 where α/β is not rational. An algorithm is “trivial” here if it essentially checks all binary
1193 trees with n leaves. ♦
1194 Exercise 4.30: The range of the frequency function f was assumed to be natural numbers. 1195 If the range is arbitrary integers, is the Huffman theory still meaningful? Is there fix?
1196 What if the range is the set of non-negative real numbers? ♦

1207 (b) Same as part (a) but using method (II).
1208 (c) Discuss the pros and cons of (I) and (II).
1209 (d) There are clearly many generalizations of shift keys, as seen in modern computer 1210 keyboards. The general problem arises when our letters or characters are no longer indi-
1211 visible units, but exhibit structure (as in Chinese characters). Give a general formulation 1212 of such extensions. ♦
1213 End Exercises
1214 §5. Dynamic Huffman Code
1215 The original Huffman coding formulation does not take into account the full context of its 1216 applications, which we now clarify.
1217 ¶26. The Larger Context of Huffman Coding.Add Here is the typical sequence of steps
1218 for compressing and transmitting a string s using the Huffman code algorithm. Imagine two 2 1219 players in this process, called the Sender and Receiver.
1220 Sender Steps:
1221 (S1) To transmit string s, first compute its frequency function fs.
1222 (S2) Using fs, construct a Huffman code tree TC corresponding to the code C.
1223 (S3) Using TC, compute the compressed string C(s).
1224 (S4) Finally, transmit the string αC;C(s) that is the concatenation of αC (representing TC as 1225 in Theorem 11), with the compressing string C(s).
1226 Receiver Steps:
1227 (R1) On receipt of αC, reconstruct TC. Since αC is self-limiting, the Receiver knows the break 1228 between αC and C(s).
1229 (R2) Using TC, the Receiver can now reconstruct s from C(s)
1230 Since the Sender must make two passes over the string s (in steps (S1) and (S3)), the 1231 original Huffman tree approach is called “2-pass Huffman encoding”. There are weaknesses in 1232 this 2-pass process: (a) Multiple passes over the string s makes the algorithm unsuitable for 1233 realtime data transmissions. If s represents a large file, this require extra buffer space. It is 1234 unsuitable for strings that are (potentially) infinite. Examples of the latter include Ticker Tape 1235 data from a Stock Exchange, or sensor data that is continuously transmitted from satellites to 1236 earth stations. (b) The Huffman code tree must be explicitly transmitted before the decoding 1237 of C(s) can begin. The sender needs an algorithm to convert TC to αC, and the receiver needs 1238 another algorithm to do the reverse conversion.
1239 An approach called Dynamic Huffman coding (or adaptive Huffman coding) can over1240 come these weaknesses: the Sender does not need to explicitly transmit the code tree, and 1241 makes only one pass over the string s. In fact, the Sender does not even have to pass over the 1242 entire string even once before starting transmission; this allows the Receiver to begin decoding 1243 some prefix of s while the transmission is ongoing. This property is vital for the transmission 1244 of (potentially) infinite strings as noted above. There are two algorithms for dynamic Huff1245 man coding: one is the FGK Algorithm (Faller 1973, Gallager 1978, Knuth 1985) and the 1246 Lambda Algorithm (Vitter 1987). See [11]. The dynamic Huffman code algorithm has been 1247 used for data compression in the Unix utility called compress/uncompress.
1248 ¶27. Sibling Property.In Dynamic Huffman Coding, the weighted code tree T must
1249 evolve as characters from the input string is read. It must evolve in two ways: not only 1250 does the frequency of letters in Σ increase over time, but Σ itself can grow as new letters are
1251 encountered. We need to update our representation of T as this happens. The key idea is the 1252 “sibling property” of Gallagher.
1253 Assume T has k ≥ 0 internal nodes. So it has k +1 leaves or 2k +1 nodes in all. We say T 1254 has the sibling property if its nodes can be ranked from 0 to 2k satisfying: Add
1255 (S1) (Weights are non-decreasing with rank) If wi is the weight of node with rank i, then 1256 wi−1 ≤ wi for i =
1,…,2k.
1257 (S2) (Siblings have consecutive ranks) The nodes with ranks 2j and 2j + 1 are siblings (for
1258 j = 0,…,k − 1). siblings and ranks
1259 For example, the weighted code tree in Figure 3 has been given the rankings 0,1,2,…,16. 1260 We check that this ranking satisfies the sibling property. Note that the node with rank 2k is 1261 necessarily the root, and it has no siblings. In general, let r(u) denote the rank of node u. If 1262 the weights of nodes are all distinct, then the rank r(u) is uniquely determined by Property 1263 (S1).
1264 Lemma 12 Let T be weighted code tree. Then T is Huffman iff it has the sibling property.
1265
1266 Proof. If T is Huffman then by definition, it is constructed by the Huffman code algorithm. 1267 We can rank the nodes in the order that nodes are extracted from the priority queue, and 1268 this ordering implies the sibling property. Conversely, the sibling property of T determines an
1269 obvious order for merging pairs of nodes to form a Huffman tree. Q.E.D.
1270
Wt[0..2k], Lc[0..2k]
1283 such that Cm[x] = i iff Lc[i] = x ∈ Σ, and Cm[x] = −1 if x /∈ Σ. Call Cm the character map 1284 array. Initially, Cm[x] = −1 for all x ∈ Σ0 (i.e., initially Σ = ∅). As new letters in Σ0 are 1285 encountered, they are added to Σ and the entry inCm updated.
1286 In summary, our Huffman tree is represented by three arrays Lc,Wt,Cm. For example, the Huffman tree in Figure 3 is illustrated by the arrays in Table 2: Two of these arrays, Lc and Add
Rank 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Lc h e t w r d ! o 0 2 4 6 ` 8 10 12 14
Wt 1 1 1 1 1 1 1 2 2 2 2 3 3 4 5 7 12
Table 2: Compact representation of Huffman tree in Figure 3
1287
1288 Wt, are explicitly shown. But the array Cm[x ∈ Σ0] is easily inferred from the leaf entries of Lc. 1289 E.g., Cm[h] = 0, Cm[e] = 1 and Cm[a] = −1. There is no “Rank” array in this representation
1290 because, trivially, Rank[v] = v for all v ∈ {0,…,2k}. ` h e t w r d ! o
Here is a simple application of the Sibling representation. Suppose we are given a letter
Σ, and we want to determine the corresponding Huffman code C(x). We need to first go 1293 to the leaf u of T corresponding to x. This is of course given by u = Cm[x]. The last bit of C(x)
1294 is therefore equal to the “parity” of u. (The parity of a natural number u is equal to 0 if u is 1295 even, and equal to 1 otherwise.) Then we replace u by parent(u), and thereby determine the 1296 next bit of C(x). Iterating this process, we stop when u eventually becomes the root. So the 1297 macro to compute the bits of C(x) (in reverse order) is given by
1298
C(x):
u ← Cm[x]
Output(parity(u))
While u < 2k u
←parent(u)
Output(parity(u))
1299
1300 The parent of u is computed by a simple for-loop:
1301
parent(u):
` ← 2bu/2c for p ← u + 1 to 2k if (Lc[p] = `), Return(p).
1302
1303 The for-loop is sure to terminate when u is non-root. Moreover, the number of times that the
1304 p variable is updated (over repeated calls to parent(u) by C(x)) is at most 2k values since the
1305 value of p is strictly increasing with each assignment. This ensures the overall complexity of 1306 C(x) is O(k). Ideally, we would like to generate C(x) in time O(|C(x)|) (Exercise).
1307 ¶29. The Restoration Problem.The key problem of dynamic Huffman tree is how to
1308 restore Huffman-ness under a particular kind of perturbation: let T be Huffman and suppose 1309 the weight of a leaf u is incremented by 1. So weight of each node along the path from u to
1311 longer be Huffman. Informally, our problem is to restore Huffman-ness in such a treeAdd T0.

Figure 6: Restoring Huffmanness after incrementing the frequency of letter `
1312 Let us first give some intuition of what has to be done, using our example of he“o 1313 wor`d!. Begin with the Huffman tree after having transmitted the prefix he`. Assume that, 1314 somehow, we managed to construct a Huffman tree for this string as shown in Figure 6(a). 1315 The letters h, e and ` are stored in nodes 4,3 and 1 (respectively). Note that there is a 1316 leaf with weight 0, but we ignore this for now. Each letter has frequency (=weight) of 1.
1317 The next transmitted letter is `, and if we simply increase the frequency of node 1 (which 1318 represents `) to 2 = 1 + 1, we would violate the ranking property (S1) of ¶27. This is 1319 because the weight of a node of rank 1 would now be greater than the weights of nodes
1320 with greater rank (3 and 4). The key idea is to first swap node 1 with node 4. This is shown
1327 Consider the following algorithm for restoring Huffman-ness in T. For each node v in T,
1328 let R(v) denote its rank in the original tree T. But our usual convention is that v is identified 1329 with its rank, i.e., R(v) = v. Let u be the current node. Initially, u is the leaf whose weight 1330 was incremented. We use the following iterative process:
1331
1332
Restore (u)
1.
2. 3. 4. 5.
6. . u is a node whose weight is to be incremented
the root) do
. Find node v of largest rank R(v) subject . to
powcoderWt[v + 1] = Wt[u])
v++
If (v 6= u)
Swap(u,v). / This swaps the subtrees rooted at u and v.
Wt[u]++. / Increment the weight of u u ← parent(u). / Reset u
Wt[u]++. / Now, u is the root
1333

1334 We need to explain one detail in the Restore routine. The swap operation in Line 3 needs 1335 to be
explained: conceptually, swapping u and v means the subtree rooted at u and the subtree
1343
Swap(u,v)
1. tmp ← Lc[u]
2. Lc[u] ← Lc[v]
3. Lc[v] ← tmp
4. If (Lc[u] ∈ Σ0) then Cm[Lc[u]] ← u
5. If (Lc[v] ∈ Σ0) then Cm[Lc[v]] ← v
1344
1345 The first 3 assignments in Swap(u,v) is the standard meaning of swapping two values: Lc[u] ↔
1346 Lc[v]. The last two assignments are to update our character map Cm for the purposes of We do 1347 not need to exchange Wt[u] and Wt[v] since they have the same weights! A swap is done only 1348 if v > u (Line 2 of Restore). Thus the rank of the current node u is strictly increased by such 1349 swaps. After swapping u and v, their siblings are automatically swapped (recall that rank 2j 1350 and rank 2j + 1 nodes are siblings).
Lc h e t w r d ! o 0 2 4 6 ` 8 10 12 14
Wt 1 1 1 1 1 1 1 2 2 2 2 3 3 4 5 7 12
Restore (u) u Pr el
p
Rank 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1358
1359 Note that u has rank 2. For clarity, let xi denote the node whose rank is i. Thus u = v2.
1360 Moreover, Wt[x2] = 1 and so we must find the largest ranked node with the same weight of 1.
1361 As seen from the table, this is the node x6. In the restore algorithm, after the while loop, the 1362 variable v is equal to x6, and we call Swap(u,v) = Swap(x2,x6). After the swap, v = x2 and 1363 u = x6, and we incrementing the weight of x6: Add
1364
Lc h e ! w r d t o 0 2 4 6 ` 8 10 12 14
Wt 1 1 1 1 1 1 1+1 2 2 2 2 3 3 4 5 7 12
After first swap v u
Rank 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1365
1366 Next, u is set to the parent of node of rank 6, namely v11. This has weight 3, and so we must 1367 swap it with the element v12 which is the highest ranked node with weight 3. After swapping 1368 v11 and v12, we increment the new v12. The following table illustrates the remaining changes:
1369
Lc h e ! w r d t o 0 2 4 ` 6 8 10 12 14
Wt 1 1 1 1 1 1 1+1 2 2 2 2 3 3+1 4 5 7+1 12
No third swap u = v
Rank 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Lc h e ! w r d t o 0 2 4 ` 6 8 10 12 14
Wt 1 1 1 1 1 1 1+1 2 2 2 2 3 3+1 4 5 7 12
After second swap v u
1370
Lc h e ! w r d t o 0 2 4 ` 6 8 10 12 14
Wt 1 1 1 1 1 1 1+1 2 2 2 2 3 3+1 4 5 7+1 12+1
No final swap u = v
1371 ¶30. How to add a new letter: the 0-Node. Our dynamic Huffman code tree T must be 1372 capable of expanding its alphabet Σ. This is illustrated in Figure 7 which shows how T evolves 1373 as we process successive letters in the string s = hello.
0 0
8
6 5
6 7
4
2 3
4 5
2 2 ` 4 ` 1213oe1 2 2 3 5

`
0 1 e 1 1
0 1 0 1 h * h 0 1
* o
Figure 7: Evolving Huffman tree on inserting the string hello
1374 Initially, Σ = {*} whereAdd * is a special letter of weight 0. The leaf of T representing * is called
1375 the 0-node (or, the *-node). It is justified by the fact that no other node has weight 0, and * 1376 does not
occur in the input string s. Although this node does not represent any input letter, 1377 yet in another sense, it represents all the yet unseen letters! We slightly revise our definition
1378 of Cm in (40) to
Cm : Σ0 → {0,1,2,…,2k} (41)
1379 such that Cm[x] = 0 iff x /∈ Σ, and otherwise Lc[Cm[x]] = x.
1. Our Huffman tree T has a special 0-node.
(42) 2. If T has other nodes, then the parent of the 0-node has rank 2.
1385 Let us now see how T evolves as we process the next letter x in the string s. There are two 1386 cases:
1387 (Case-1) The letter x is already in T: In this case, the Character Map Cm[x] returns the leaf 1388 that represents x. We can output the code C(x) of x starting from Cm[x], as described 1389 above. Moreover, we update T by increment the weight of Cm[x], and call Restore(u) 1390 where u is the parent of Cm[x].
1391 (Case-2) The letter x is new: Now, we assume that Cm[x] returns the 0-node. Again we can 1392 output C(*), and send the standard code for x (e.g., ASCII code of x). Let u be 1393 the 0-node. We now turn u into an internal node with children uL and uR. Make 1394 uL the new 0-node, and uR represent x with weight 1. That means updating the 1395 Character Map with Cm[*] ← uL and Cm[x] ← uR. We update the weights as follows: 1396 Wt[uL] ← 0,Wt[uR] ← 1. Note that Wt[u] = 0, but must be incremented: this is done 1397 by calling Restore(u), which ensures that the update is propagated all the way to 1398 the root while preserving the Sibling Property.
1399 The transformation of the arrays Lc/Wt in Case-2 seems formidable as described above. We 1400 will eventually see that the mechanics is quite simple. But to understand what needs to be 1401 done, we study an example. A Case-2 transition in Figure 7 happens when we process the letter 1402 o in the string hello. The Lc/Wt arrays before and after this transition is shown here:
Rank – – 0 1 2 3 4 5 6
Lc – – * h 0 e ` 2 4
Wt – – 0 1 1 1 2 2 4
Rank 0 1 2 3 4 5 6 7 8
Lc * o 0 h 2 e ` 4 6
Wt 0 1 0 1 1 1 2 2 4
Rank 0 1 2 3 4 5 6 7 8
Lc e 2
Wt 1 2 3 5
Before Restored Add
1403 After
1404 Conceptually, we must add two new array entries in front of the
original arrays! Under the 1405 assumption (42), the former 0node becomes the rank 2 node. Indeed, all the nodes of the 1406 original tree have their ranks increased by 2. That meant for any internal node of rank i, if 1407 Lc[i] = j before the transition, then Lc[i + 2] = j + 2 after. E.g., if Lc[6] = 4 before, then 1408 Lc[8] = 6 after. This appears to be a non-trivial transformation, but we will solve it by an 1409 encoding trick. We use a blue font to identify those entries of Lc/Wt array that have been 1410 changed. These transformations (Before → After) are easily achieved using extendible arrays, 1411 to be described.
1412 In the After arrays, there is a single entry in red font, namely Wt[2] = 0. This is the 1413 entry that needs to be incremented to Wt[2] = 1. We call Restore(2) to do this increment 1414 since it must be propagated along the root path. The final result is shown in the arrays for 1415 Restored where we only indicate entries that have changed. Note that we have effected one 1416 swap operation, Swap(4,5)=Swap(4, Cm[e]).
1417 We address the final issue of how to increase the ranks of all nodes by 2 in the array Lc 1418 (i.e., transforming Lc[i] = j to Lc[i + 2] = j + 2 above). There are two related issues:
1421 assume that the length of A can be extended by any needed amount m ≥ 1, transforming 1422 A[0..n − 1] to A[0..n + m − 1] in which A[n..n + m − 1] are new slots while A[0..n − 1]
1423 are unchanged. Such an extendible array A∗ can be simulated by a fixed length array 1424 by preallocating a sufficiently large array, provided we introduce a member variable n to 1425 remember the current length of the array. Extending the array by m slots just amounts to 1426 increasing n by m. Thus we will simulate Lc/Wt by the extendible arrays Lc∗/Wt∗.
1427 (b) The second issue is that the array A∗ is extendible at the high end (i.e., the new m slots 1428 are A[n..n + m − 1]) while our application needs to extend at the low end (i.e., new slots 1429 in A[0..m − 1]). We partially resolve this by defining this relationship between A and A∗:
A[i] = j iff A∗[Idx(i)] = j (43)
1430 where Idx(i) = n − 1 − i is the index function. But for the array Lc, the value of 1431 Lc[i] (when i is an internal node) is actually, an index into the array Lc. Therefore the 1432 relationship between Lc and Lc∗ is modified to
Lc[i] = j iff Lc∗[Idx(i)] = Idx(j). (44)
Since the size of Lc/Wt is n = 2k + 1 (k = |Σ|), it follows that Idx(i) = 2k − i in our application. E.g., if i is (the rank of) an internal node, then (the ranks of) its left and right children are
Lc[i] = Lc∗[Idx(i)], Lc[i] + 1 = Lc∗[Idx(i)] + 1. 1433 Note that the root always has rank 2k in Lc/Wt, it follows that Lc∗[Idx(2k)] = Lc∗[0] is 1434 always the left child of the root, independent of the size n = 2k +1. Similar remarks apply
1435 to the array Wt∗: e.g.,Wt[i] = Wt∗[Idx(i)], and therefore Wt∗[0] is the weight of the root.
1436 The implementation of (a) and (b) results in the following Before→After transformation of 1437 the array
Lc∗ of our running example. We also show Lc for comparison: Add
Rank i – – 0 1 2 3 4 5 6
Lc[i] – – * h 0 e ` 2 4
Idx(i) 0 1 2 3 4 5 6 – –
Lc∗[Idx(i)] 2 4 ` e 6 h * – –
Before
1438

Rank i 0 1 2 3 4 5 6 7 8
Lc[i] * o 0 h 2 e ` 4 6
Idx(i) 0 1 2 3 4 5 6 7 8
Lc∗[Idx(i)] 2 4 ` e 6 h 8 o *
After
1439 It is clear the transformation affects only the last 3 entries of Lc∗ (in red font).
1440 In summary: all operations on the arrays Lc/Wt are effected through operations on the 1441 extendible arrays Lc∗/Wt∗. In particular, subroutines such as Restore must be reinterpreted 1442 as operations on Lc∗/Wt∗. For Case-2, we extend these arrays simply by incrementing k, 1443 effectively extending Lc∗/Wt∗ by 2 slots. These new slots are at the high end of Lc∗/Wt∗ 1444 (corresponding to the low end of Lc/Wt). The transformation can be effected in O(1) time.
1445 ¶31. Interface between Huffman Code and Standard Encoding. Let Σ denote the
1446 set of characters in the current Huffman code. We view Σ as a subset of a fixed universal set 1447 U where U ⊆ {0,1}N. Call U the standard encoding. The main example of a standard
1448 encoding U is the set of ASCII characters with N = 8. A more complicated example is when U
1449 is some unicode set. We assume the transmitter and receiver both know this standard encoding 1450 (in particular the parameter N). In the encoding process, we assume that s ∈ U∗. Upon seeing 1451 a letter x in s, we must decide whether x ∈ Σ (i.e., in our current Huffman tree), and if so, 1452 transmit its current Huffman code. To be specific, suppose |Σ| = k and the current Huffman
1453 tree T is represented by the arrays Lc[0..2k],Wt[0..2k]. If x ∈ {0,1}N, let C[x] = i if node i (of 1454 rank i) is the leaf of T representing the letter x. Initially, let C[x] = −1 for all x. Hence, the 1455 array C is a representation of the alphabet Σ.
1456 Even though we know the leaf, it requires some work to obtain the corresponding Huffman 1457 code. [This is the encoding problem – but the Huffman code tree is specially designed for the 1458 inverse problem, i.e., decoding problem.] One way to solve this encoding problem is assume 1459 that our Huffman tree has parent pointer. In terms of our Lc,Wt array representation, we now 1460 add another array P[0..2k] for parent pointers.
1461 Here now is the dynamic Huffman coding method for transmitting a string s: 1462
Dynamic Huffman Transmission Algorithm:
Input: A string s of indefinite length.
The dynamically encoded sequence representing s.
. Initialization
Initialize T to the 0-node, and size k ← 0.
(T is represented by the arrays Lc∗/Wt∗/Cm)
While s is non-empty
1. Remove letter x from the front of string s.
2. Let u = Cm[x] be the leaf of T corresponding to x.
3. Using u, transmit the code word C(x).
4. If u is the 0-node / x is a new character
5. Transmit the standard code for x.
6. k++ and
perform the Before → After transformation.
7. Call Restore(2).
Signal termination, using some convention.
1463

1464
1465 On the Receiver
End, decoding is relatively straightforward. We are processing a continuous 1466 binary sequence, but we know where the implicit “breaks” are in this continuous sequence be1467 cause the transmitted information is a sequence of self-limiting codes. Call the binary sequence 1468 between these breaks a word. We know how to recognize these words by maintaining the same 1469 dynamic Huffman code tree T as the transmission algorithm. For each received word w, there 1470 is a corresponding action:
1471 (R1) If w = C(x) is the code word for some x ∈ Σ, we spit out the standard code of x. We 1472 also increment the weight of Cm[x] by calling Restore(Cm[x]).
1473 (R2) If w = C(*), this is is a signal that the next word is the standard encoding of a new letter.
1474 (R3) If w is the anticipated standard encoding of a new letter x, we spit out w. Then we 1475 update Cm[x] = 1 and perform the Before → After transformations of Lc∗/Wt∗. Finally, 1476 we call Restore(2).
1477 What is spit out by the receiver is clearly a faithful reproduction of the original string s which 1478 is in standard encoding.
1479 REMARKS: It can be shown that the FGK Algorithm transmits at most 2H2(s)+4|s| bits. 1480 The
Lambda Algorithm of Vitter ensures that the transmitted string length is ≤ H2(s)+|s|−1 1481 where
H2(s) is the number of bits transmitted by the 2-pass algorithm for s, independent of 1482 alphabet size. In Chapter VI, we will show another approach to dynamic compression of strings 1483 based on the move-to-front heuristic and splay trees [1].
1484 ¶32. Beyond Huffman Coding: Lempel-Ziv Coding. Although Huffman codding is 1485 optimal, we can go beyond its character-by-character encoding assumption. In other words, 1486 we can look for blocks of characters that occur with high frequency. For example, in English,
1487 certain digraphs like in, at, th, ng, etc, occur with high frequency. Certain trigraphs like
1488 the, ing, ion, and, etc, are also very common. But more generally, there is no need to

(a) ASCII set (b) ANSI extension
Figure 8: Extended ASCII
1491 ¶33. Notes on the ASCII Character Set. ASCII stands for The American Standard Code 1492 for Information Interchange, and refers to the 7-bit encoding of 128 characters. See Figure 8(a) for
1493 this character set. There are 95 printable characters such as 0, 1,…, 9, a, b, c,…, x, y, 1494 z, and A, B, C,…, X, Y, Z, including the space character which we denote by ‘t’. The remaining 1495 33 are nonprinting or control characters such as backspace (BS), carriage-return (CR), bell (BEL), 1496 etc. They include many obsolete ones associated with technology such as teletype from a bygone era.
1498 and last characters. For instance, the table in Figure 8(a) shows that the first and last characters of 1499 these first 128 characters are called NUL and DEL, respectively. Indeed, the first 32 characters (i.e., 1500 the first two columns in Figure 8(a)) are control characters, as is the last DEL.
1501 The hexadecimal code for any character in Figure 8 is given as 0xCR where C is the column number

1502 and R is the row number of that character. E.g., 0x20 is the space character (also denoted t), and the 1503 lower case alphabet a, b, c,…, x, y, z occupy the sequence 0x61 to 0x7A.
1504 The basic ASCII character set has been extended into a set of 256 characters; Figure 8(b) shows 1505 this so-called ANSI extension (ANSI stands for American National Standards Institute). For example, 1506 two special symbols we use throughout in this book comes from the extension: the section symbol
1507 ‘§’ and paragraph symbol ‘¶’. The 256 characters is naturally associated with an 8-bit binary string 1508 called its ASCII code. We shall write ASCII(x) to denote the ASCII code of a character x. The 1509 original 128 characters in the ASCII character set, naturally, occupy the first 128 positions; thus a 1510 character x belongs to this original set iff the most significant bit in ASCII(x) is 0. Of course, the 1511 8-bits can be broken up into two groups of 4-bits which are then interpreted as hexadecimal digits. 1512 This much more compact notation is preferred. The 16 hexadecimal digits are conventionally written as 1513 0,1,2,…,9,A,B,C,…,F. Because of the overlap between standard decimal digits and hexadecimal 1514 digits, a sequence like ‘10’ would be ambiguous. To indicate that the hexadecimal digits are meant, we
1515 typically prefix the digits by ‘0x’. Thus, the ASCII code for the character A is (01000001)2 in binary 1516 or 0x41 in hexadecimal notation. Here are some ASCII codes:
ASCII(A) = 0x41,
ASCII(Z) = 0x5A,
ASCII(a) = 0x61, ASCII(z) = 0x71,

ASCII(0) = 0x30, ASCII(9) = 0x39,
ASCII(t) = 0x20, ASCII(∗) = 0x2A.
1517 Note that t (space) is considered a printing character. These are all part of the original ASCII set
1518 since the first hexadecimal digit are all in the range 0 to 7. In contrast, the extended characters
1519 begin with a digit in the range 8 to F. E.g., ASCII(§) = 0xA7 and ASCII(¶) = 0xB6. Actually,
1522 There are many variants of the ASCII encoding, as many countries adapted ASCII to their unique
1523 requirements. Today, the ASCII encoding is re-interpreted as the first 128 characters of the UTF-8 1524 encoding. The latter is part of theAdd Unicode, a character encoding system of amazing scope and 1525 generality. This system will be briefly described next.
The original ASCII set together with the ANSI extension is often called the
1526 extended ASCII set. However, unless otherwise noted in this book, we will use
“ASCII set” to refer to the extended ASCII set..
1540 There are other international standards (ISO) and these have some compatibility with Unicode. 1541 For instance, the first 256 code points corresponds to ISO 8859-1. There are two methods for encoding 1542 in Unicode called Unicode Transformation Format (UTF) and Universal Character Set
(UCS). These 1543 leads to UTF-n, UCS-n for various values of n. Let us just focus on one of these, UTF-
8. This was
You know the joke: there are 10 kinds of people in the world — those who count in binary and those who count in decimal.

1544 created by K.Thompson and R.Pike, which is a de facto standard in many applications (e.g., electronic 1545 mail). It has a basic 8-bit format with variable length extensions that uses up to 4 bytes (32 bits). It 1546 is particularly compact for ASCII characters: only 1 byte suffices for the
127 US-ASCII characters. A 1547 major advantage of UTF-8 is that a plain ASCII string is also a valid UTF-8 string (with the same 1548 meaning of course). Here is
UTF-8 in brief:
1549 1. Any code point below U+0080 is encoded by a single byte. Of course, 080 in hex is just 128 in 1550 decimal.
Thus, U+00XY where X < 8 can be represented by the single byte XY that has a 1551
leading 0bit.
1552 2. Code points between U+0080 to U+07FF uses two bytes. The first byte begins with 110, second 1553 byte begins with 10.
1554 3. Code points between U+0800 to U+FFFF uses three bytes. The first byte begins with 1110, 1555 remaining two bytes begin with 10.
1556 4. Code points between U+100000

to U+10FFFF uses four bytes. The first byte begins with 11110, 1557 remaining three bytes begin with Exercise 5.2:
10. Simplified
dynamic
1558 Observe that each code point is self-limiting, i.e., you can tell when you have reached the end of a Huffman tree.
code 1559 point. 1560 Let T be
1561 Exercises the
external
BST in
1562 Exercise Figure 9
5.1: In this whose question, leaves we are store the asking for set Σ = three {*,e,h,l,o, numbers. r,w} of But you characte
must rs with
summarize the
1563 intermediat sorting
e results of order
your * computatio < ns. Assume e that the < alphabet Σ h is a subset <
of l
8 <
1564 {0,1} (i.e., o
ASCII code). <
1565 (a) What is r
the length < of the w
(static) .
Huffman
code of the 1572 Given x ∈ string Σ, we can “hello, compute
world!”? its code
The C(x) by
doing
1567 (b) How many bits does it take to transmit the Huffman tree used for encoding in part(a)? 1568 x) in T, Note: using static Huffman coding, you must first transmit part(b) before transmitting and C(x)
1569 part(a). is just
1570 (c) How many bits would be transmitted by the Dynamic Huffman code algorithm in 1573 the
1571 sending the string “hello, world!”? Compare this number with parts(a)+(b). ♦ correspo
nding search path. E.g., C(h) = 0100, and C(w) = 11. Thus, T represents a 1574 prefix-free code for Σ.
1575 Let s ∈ Σ∗ be a string to be transmitted. Assuming that receiver also has a copy of the 1576 tree T, the receiver would be able to decode our message. We look at two scenarios: a 1577 static and a dynamic way to use T for transmission.
1578 1. We first assume that T is static (unchanging). How many bits does it take to transmit
1579 C(s) where
s = hellloooo (45)
1580 Please show the encoded string C(s).

Figure 9: An external BST
1585 Again, show us the encoded binary string C(s).
1586
1587 ♦ 1588 E
x e r ci s
e 5.
3
:
W h a t is
t h
e m
e s s

a g
e s
?
1589 (
a
)
C o n
si
d
e
r
t h
e
f
o ll o w
i
n
g
c
o m
p
r e s s
e
d
b
it
r e
p r e s e n
t a ti
o
n
α
T o f
a
f
u
ll
b
i
n a r y tr e
e
T
:
1590
αT = 00010101100011000110011. (46)
1591 Please draw T. 1592
1593 (b) The leaves of T contain the following ASCII characters, listed in left-to-
1594right order:
t o g e d r i s n t
Add
1595
1596 Parts(a) and (b) defines a Huffman code. We used it to encode a string s into C(s):
C(s) = 01010010101011010000001100011001000011100001011110000001000010010100
(47)
1597 What is our original string s?
1598 (c) What is the total number of bits I need to transmit in order to send you this 1599 message, including the Huffman tree? Is this an improvement over just sending you the
1600 straight ASCII code for s? ♦
1601 Exercise 5.4: What binary string would you transmit in order to send the string “now is the 1602 time”, under the dynamic Huffman algorithm? Show your working. Note: you would
1603 have to transmit ascii codes for the letters n, o, w, etc. Just write ASCII(n), ASCII(o),
1604 ASCII(w), etc. ♦
1605 Exercise 5.5: Natural languages are highly redundant. Here is one way to test this. 1606 (a) Please transmit the following string using dynamic Huffman coding, and state the bit 1607 length of your transmission.
1608 Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn’t 1609 mttaer in waht oredr the ltteers in a wrod are, the olny 1610 iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit 1611 pclae. The rset can be 1612 a total mses and you can sitll raed it wouthit porbelm. Tihs is
1613 bcuseae the huamn mnid deos not raed ervey lteter by istlef, but 1614 the wrod as a wlohe.
1615 (b) Now repeat part (a) but using similar string in which the words are now properly 1616 spelled. Should we expect a drop in the number of transmitted bits? Note that this 1617 experiment could not be done using standard Huffman coding since the frequency function 1618 in (a) and (b) are identical. ♦
Exercise 5.6:
(a) Please reconstruct the Huffman code tree T from the following representation:
r(T) = 000001111000110011d0mrit0yo
Besides the 0/1 symbols, the letters d,m,i, etc, stand for 8-bit ASCII codes. The leftmost leaf in the tree is the 0-node, and its label (namely ’∗’) is implicit. NOTE that the ’∗’
letter actually has ASCII code 0x2A in hex, so it is not literally the smallest letter. The smallest letter in the ASCII code is 0x00 and is usually called the NUL character. The
remaining leaves are labeled by 8-bit ASCII codes for d,m,r,i,t,y,o, in left-to-right order. (b) Here is an ASCII string s encoded using this Huffman code:
C(s) = 00010111001001010010011101011010
Decode the string s.
(c) Assume that the leaves of the Huffman tree in (a) has the following frequencies (or weights):
f(∗) = 0, Add f(d) = f(m) = f(i) = f(t) = d(y) = 1, f(r) = f(o) = 2.
1619 Assign a rank (i.e., numbers from 0,1,…,14) to the nodes of the tree in (a) so that the 1620 sibling property is obeyed. Redraw this tree with the ranking listed next to each node. 1621 Also, write the arrays Lc[0..14] and Wt[0..14] which encodes this ranking of the Huffman 1622 tree. Recall that these arrays encode the left-child relation and weights (frequencies),
1623 respectively.
1624 (d) Suppose that we now insert a new letter t (blank space) into the weighted Huffman 1625 code tree of (c). Draw the new Huffman tree with updated ranking. Also, show the 1626 updated arrays Lc[0..16] and Wt[0..16].
1627 (e) Give the Huffman code for the string “dirty room” (this string has is a blank character 1628 t, but the quotes are not part of the string). What is the relation between this string
1629 and the one in (d)? ♦ 1630 Exercise 5.7: Give the dynamic Huffman coding for the following anagrams:
1631 (1) the morse code
1632 (2) here come dots ♦
1633 Exercise 5.8: Assume the Sibling Representation of the Huffman code C : Σ → {0,1}∗. Give 1634 the routine to compute the code word C(x) ∈ {0,1}∗ of any given x ∈ Σ. ♦
1635 Exercise 5.9: Give a careful and efficient implementation of the dynamic Huffman code. As1636 sume the compact representation of Huffman tree using the arrays Wt and Lc described
1637 in the text. ♦

1638 Exercise 5.10: Consider 3-ary Huffman tree code. State and prove the Sibling property for
1639 this code. ♦
1640 Exercise 5.11: A previous Exercise asks you to construct the standard Huffman code of Lin1641 coln’s speech at Gettysburg.
1642 (a) Construct the optimal Huffman code tree for this speech. Please give the length of 1643 Lincoln’s coded speech, and also the size of the code tree.
1644 (b) Please give the length of the dynamic Huffman code for this speech. How does it
1645 compare to part (a)? Also, compare the code tree at the end of the dynamic coding
1646 process with the one in part (a). ♦
1647 Exercise 5.12: In the text, we have represented the Huffman code tree ways: as an binary code 1648 tree and as the arrays Wt,Lc,Cm. The former gives O(|C(x)|) complexity for finding the 1649 code of x ∈ Σ, but the latter is only O(|Σ|). Show how to improve the latter complexity
1650 in the setting of dynamic Huffman coding. ♦
1651 Exercise 5.13: The correctness of the dynamic Huffman code depends on the fact that the
1652 weight at the leaves are integral and the change is +1.
1653 (a) Suppose the leave weights can be any positive real number, and the change in weight 1654 is also by an arbitrary positive number. Modify the algorithm.
1655 (b) What if the weight change can be negative? ♦
Exercise 5.14: Programming Project. Suppose we are given s1, a string of (extended) ASCII characters. Let C1 be the static Huffman code for s1. Consider the binary string
Add αC1C1(s1)
1656 where the first part αC1 is the encoding of C1 described in ¶23 above, and the second 1657 part C1(s1) is just the application of C1 to s1. Break this up into 8-bit blocks and so 1658 reinterpret it as an ASCII string denoted s2. If necessary, we pad this string with 0’s so 1659 that the last block still has
8 bits. This transformation s1 → s2 can be repeated: s2 → s3, 1660 etc. What is the limit of this process? ♦
1661 Exercise 5.15: Programming Project. Compare the use of a fixed Huffman code of a large 1662
document versus a dynamic Huffman encoding. For the fixed Huffman code, use the 1663 following statistics on the frequency English letters based on a sample of 40,000 words:
1664
Letter: E T A O I N S R H D L U C
Count: 21912 16587 14810 14003 13318 12666 11450 10977 10795 7874 7253 5246 4943
Frequency: 12.02 9.10 8.12 7.68 7.31 6.95 6.28 6.02 5.92 4.32 3.98 2.88 2.71

1665
Letter: M F Y W G P B V K X Q J Z
Frequency: 2.61 2.30 2.11 2.09 2.03 1.82 1.49 1.11 0.69 0.17 0.11 0.10 0.07

1666
1667 ♦
1668 End Exercises
1669 §6. Minimum Spanning Tree
¶35. Minimizing over Maximal Sets. In the minimum spanning forest problem we are given a costed bigraph
G = (V,E;C)
1670 where C : E → R is the cost function. An acyclic set T ⊆ E of maximum cardinality is called 1671 a spanning forest; in this case, |T| = |V |−c where G has c ≥ 1 components. The cost C(T) 1672 of any subset T ⊆ E is given by C(T) = Pe∈T C(e). An acyclic set is minimum if its cost is 1673 minimum. It is conventional to make this standard simplification:
The input bigraph G is connected.
1674
1675 With this assumption, a spanning forest is actually a tree, and the problem is known as 1676 the minimum spanning tree (MST) problem. The simplification is not too severe: if 1677 our graph is not connected, we can first compute its connected components (we saw efficient 1678 solutions to this basic graph problem in Chapter IV). Then we apply the MST algorithm to 1679 each component. Alternatively, it is not hard to modify most MST algorithms so that they 1680 apply to non-connected graphs.
1681 An important point to note is that we areminimizing over certain maximal sets (spanning
1682 trees). In general, “min-max problems” can have very high complexity. But for MST, we are 1683
saved by the fact that these maximal sets have a great deal of structure. One formalization of 1684 this structure is the concept of matroid in the next section. https://po2 wcoder.com
b a
2
Add 1 2 3 e
1
Figure 10: Bigraph G5 with edge costs.
1685 Consider the bigraph G5 in Figure 10 with vertices V = {a,b,c,d,e}. One such MST is 1686 {a − b,b − c,c − d,d − e}, with cost 6 and shown in Figure 11(a).
1687 ¶36. Some Global Properties of MSTs. Fix a connected bigraph G = (V,E;C) and let 1688
MST(G) denote the set of all MST’s of G. If all the edges of G have unit cost, then MST(G) 1689 is just the set of all spanning trees of G.
1692 Each T ∈ MST(G) has size n − 1 where n = |V |. If T,T0 ∈ MST(G), notice that their 1693 symmetric difference T ⊕ T0 = (T T) ∪ (T0 T) has an even cardinality since T and T0 have 1694 the same size implies |T T0| = |T0 T|. Thus |T ⊕ T0| = 2k for some k = 0,…,n − 1. If 1695 |T ⊕ T0| = 2, we call (T,T0) an exchange pair. Exchange pairs have these properties:
1696 • |T ∩ T0| = n − 2

1697 • There are edges e ∈ T T0 and e0 ∈ T0 T with C(e) = C(e0)
1698 • T = T0 − e0 + e and T0 = T − e + e0
1699 In Figure 11, the pair (T(a),T(b)) is an exchange pair, but (T(a),T(d)) is not an exchange pair.
1700 Define the (MST) exchange graph Exch(G) to be the bigraph (MST(G),H) whose 1702 with 8 exchange pairs in blue.
1701 nodes are MST’s and edgesAdd T − T0 ∈ H are the exchange pairs. In Figure 12 we see Exch(G5)

Figure 12: Exchange graph of G5
1703 Lemma 13 (Exchange) If T 6= T0 ∈ MST(G), then there exists e ∈ T T0 and e0 ∈ T0 T 1704 such that T + e0 − e ∈ MST(G).
1705
1706 Proof. Pick e0 = argmine∈T0T C(e). Then T + e0 has a unique cycle Z. In this cycle, there 1707 exists some e ∈ T T0 (otherwise Z ⊆ T0, contradiction). Now T − e + e0 is a tree. Also 1708 C(e) ≤ C(e0) since T is MST. If C(e) = C(e0) then T − e + e0 is our desired MST, proving our 1709 claim.
1710 Otherwise, C(e) < C(e0) and we obtain a contradiction: by the same argument, T0 + e has 1711 a unique cycle Z0 and there exists in this cycle some e00 ∈ T0 T. Also C(e00) ≤ C(e) since 1712 T0 is a MST. This implies C(e00) ≤ C(e) < C(e0), contradicting our initial choice of e0 as an
1713 argmin over T0 T. Q.E.D.
1714
1715 We leave this as an exercise:
1716 Theorem 14
1717 (a) For T,T0∈ MST(G), if |T ⊕ T0| = 2k, then the link-distance between T,T0 in Exch(G) is
1718 equal k.
1719 (b) Exch(G) is a connected graph of diameter at most n − 1 where n = |V |.
1720 If T is a set of edges, let C∗(T) = {C(e) : e ∈ T} viewed as a multiset. For instance, if T is 1721 an MST of G5 (Figure 11) then C∗(T) = {1,1,2,2}.
1722 Theorem 15 For all T,TAdd 0 ∈ MST(G), C∗(T) = C∗(T0).
1723 ¶37. Prim’s Algorithm. Let us see how one algorithm for computing the MST operates. 1724 The input is the costed bigraph G = (V,E;C), and the final output is a set T ⊆ E that 1725 forms a MST of G. The goal of this section is to understand the basic mechanics of Prim’s 1726 algorithm, not to implement it on a computer. After this understanding you should be able to 1727 do hand-simulation.
1728 Imagine that Prim’s algorithm is trying to grow two sets:
1729 • S ⊆ V corresponding to the “settled nodes”
1730 • T ⊆ E corresponding to a minimum spanning tree for G|S.
1731 We maintain an array m[v ∈ V ] with this property: for all u ∈ V S,

m[u]:= min{C(v − u) : v ∈ S} (48)
with the usual convention that minimizing over an empty set of numbers is infinity: min∅ = ∞. We
proceed in stages: In Stage 0, we initialize S ← ∅ and
0 if v = s0 [ ] =
∞ else
for some arbitrary s0 ∈ V . At subsequent Stage i (i = 1,…,n) we choose any
ui = argmin{m[u] : u ∈ V S}
1732 and add ui to S. Thus ui is henceforth a “known” node. Since S is updated, we also need to 1733 update m following the definition (48). Here is a simulation of Prim’s algorithm on our graph 1734 Figure 10:
Stage a b c d e u : S ← S + u e : T ← T + e Cost
0 0/– ∞ ∞ ∞ ∞ S ← ∅ T ← ∅ 0
1 0/– 2/a 2/a 3/a 2/a u ← a − 0
2 2/a 1/b u ← b a − b 2
3 1/b 2/c u ← c b − c 3
4 2/c 1/d u ← d c − d 5
5 1/d u ← e d − e 6
1735
Graph G5
1736 Here is how to read the tabular simulation:
1737 1. Each nodev ∈ V has a
column in this table which we denote by Column(v).
1738 2. Each stage i has a row in this table which we denote by Row(i).
1739 3. Every entry in Row(i) and Column(v) has the form x/u where x is a number and u is a
1740 node. This tells us that “current value of m[v] is x where x = C(u − v)”.
1741 4. A red entry x/u in Row(i) and Column(v) tells us “node v is added to S in the ith stage, 1742 and the edge u − v to the minimum spanning tree T ”.
1743 5. An entry is blank if it is unchanged from the previous stage.Add
1744 ¶38. Generic MST Algorithm. Prim’s algorithm is one of many known algorithms for 1745 computing the MST. We now want to describe a “Generic MST Algorithm” that captures many
1746 of these algorithms. Our generic algorithm is trying to grow a set T of edges. Initially, T is 1747 empty, and the algorithm stops when |T| = |V | − 1: this T is output as an MST. Any subset 1748 T ⊆ E that is a subset of some MST is said to be feasible. It follows that our set T must be 1749 feasible at every step.
1750 Let S = V (T) be the vertices that appear in T. As T grows, so that S. Sometimes (e.g., in
1751 Prim’s algorithm), we can also formulate the algorithm as trying grow the set S. The algorithm 1752 stops when S = V .
1753
1754
Generic Greedy MST Algorithm
Input: G = (V,E;C) a connected bigraph with edge costs. Output: T ⊆ E, a MST for G.
T ← ∅.
for i = 1 to |V | − 1 do
1. Greedy Step: find an e ∈ E T that is “good for T”.
2. T ← T + e.
Output T as the minimum spanning tree.
1755
1756 NOTATION: as illustrated in Line 2, we shall write “T +e” for
“T ∪{e}”. Likewise, “T
−e” 1757 shall denote the set
“T {e}”.
1758 What does it mean for “e to be good for T”? This will be made specific next.
1759 ¶39. Some Greedy MST Criteria. Let us say that e is a candidate for T if T + e is 1760 acyclic. Consider the graph G|T = (V,T), the restriction of G to T. The connected components 1761 of G|T are called Tcomponents. For instance if T is the empty set, then each vertex forms 1762 its own T-component (such components are trivial). For any candidate e = u − v, let the
1763 T-component that contains u and v (resp.) be denoted Cu and Cv. Clearly Cu ∩ Cv is empty 1764 (otherwise we get a cycle). Moreover, Cu ∪Cv is a (T +e)-component. We say that e extends 1765 the component Cu (and also Cv by symmetry). Among the candidates for T, only some are 1766 “good”. Here are 4 notions of what “good” means:
1767 • (Minimal) T + e is feasible. This is clearly the minimal condition expected of e.
1768 • (Kruskal) Edge e has the least cost among all the candidates.
1769 • (Boruvka) Ife = (u − v) then either (i) e has the least cost among all the candidates
1770 that extend the component Cu, or (ii) e has the least cost among all the candidates that 1771 extend the component Cv. In case (i), we call Cu a Boruvka witness for e; similarly for 1772 Cv in case (ii). It is possible that both Cu and Cv are witnesses for e.
1773 • (Prim) This can be viewed adding an extra requirement to Boruvka’s condition: assume
1774 we are given a vertex s ∈ V called the source. The edge e must have least cost among 1775 candidates that extends the unique component Us ⊆ V containing s.
1777 be X-good where X ∈ {minimal, Boruvka, Kruskal, Prim} depending on the criteria used. By 1778 assumption, the empty set T is X-good for any X. The correctness of these algorithms amounts 1779 to showing that “X-good implies minimally-good” where X = Kruskal, Boruvka or Prim. Of 1780 course, minimally-good is synonymous with feasibility. We now prove this:
1781 Lemma 16 (Correctness of Algorithm X)
1782 Let T ⊆ E.
1783 (a) If T is Prim-good then T is Boruvka-good.
1784 (b) If T is Kruskal-good then T is Boruvka-good.
1785 (c) If T is Boruvka-good then T is minimally-good.
1786
1787 Proof. In each case, we want to show that if T is X-good, then it is Y-good, for appropriate X 1788 and Y. We use induction on |T|. When |T| = 0 and the lemma holds trivially. Suppose T and 1789 T + e are X-good. By induction, T is Y-good. It remains to show that T + e is Y-good.
1790 (a) X=Prim, Y=Boruvka: We must show that T +e is Boruvka-good. Since T +e is assumed 1791 to be Prim-good, we know e has least cost among the edges that extend the T-component 1792 Cs containing the source s. So Cs is a Boruvka-witness for e. Thus T +e is Boruvka-good.
1793 (b) X=Kruskal, Y=Boruvka: We must show that T + e is Boruvka-good. Since T + e is
1794 assumed to be Kruskal-good, we know e has least cost among the edges that extend any 1795 T-component. The T-component for which e has least cost serves as a Boruvka-witness for 1796 e. Thus T + e is Boruvkagood.
1797 (c) X=Boruvka, Y=minimally: We need to prove that T + e is minimally-good. By the 1798 Boruvkagoodness of T, there is a T-component U which is the Boruvka-witness for e. 1799 By induction hypothesis, T is minimally-good. Hence there is a MST T0 that contains T. 1800 If e ∈ T0, then we are done (as T0 is witness that T + e is minimally-good). So assume 1801 e 6∈ T0. This means that contains a closed path Z.

Figure 13: Extending a component U by e = (u,v).
Let e = u− v where u ∈ U and v 6∈ U. The closed path Z has the form Z :=(u − v − v1 − v2 − ··· − vk − u).
Clearly, there exists somei = 0,…,k such that vi ∈6 U and vi+1 ∈ U where v = v0 and u = vk+1 in
this notation. Rewriting,
Z = (u − v − v1 − ··· − vi − vi+1 − ··· − u).
1802 Let e0 :=(vi − vi+1)Add . Note that T00 :=(T0 − e0) + e is acyclic (since we broke the unique
1803 cycle Z by omitting e0). It is also a spanning tree. Looking at costs, we have C(e) ≤ C(e0), 1804 by our choice of e as least cost edge out of U. Hence C(T00) ≤ C(T0). Since T0 is MST, 1805 this means T00 is also an MST. Thus T + e is minimally-good as it is contained in T00.
1806 Q.E.D.
1807
1808 This minimally-good criterion is computational ineffective. The remaining three criteria 1809 are effective and are named after the inventors of three well-known MST algorithms. We next 1810 discuss the algorithmic techniques needed to make these criteria effective:
1811 • (Kruskal) Kruskal tells us to sort the edges first, and then consider each edge e in order 1812 of increasing cost. How can we quickly tell if T +e is acyclic? If e is u − v, this amounts 1813 to checking if u,v are in the same connected component of the graph G|T = (V,T). A 1814 simple method is to do this is have a linked list for each connected component of G|T, 1815 with the nodes of the linked list representing vertices of the component. Given a vertex 1816 u, assume we have a pointer from u to the representative for u in such a linked list. To 1817 decide if two vertices u,v are in the same connected component, we go to the linked lists 1818 nodes that represent u and v, and follow the links till the end of their respective linked 1819 lists. The ends of these two linked list are equal iff T + e has a cycle.
1820 The elaborations of this linked list idea will ultimately lead us to the union-find data 1821 structure which is studied in Chapter XIII. An Exercise below will explore some of these 1822 ideas.
1823 • (Boruvka) Suppose T is a Boruvka-good set. If T is not a spanning tree of G, the number 1824 of T-components is at least 2. Let these T-components be U1,…,Uk (k ≥ 2). For each 1825 Ui, there is at least one ei that extends Ui with least cost. These ei’s need not be distinct 1826 (it is possible that ei = ej with i 6= j). Nevertheless, there are at least dk/2e distinct edges
1827 in the set {e1,…,ek}. Algorithmically, we want maintain the least cost edge that extends 1828 each Scomponent. We can exploit the union-find data structure (see Chapter 13), but at
1829 present, a simple direct solution can be found. The key feature of Boruvka’s algorithm 1830 is that we can select the good edges in “phases” where each phase calls for a pass through 1831 the set of remaining edges. This feature can be exploited in parallel algorithms.
1832 • (Prim) Because of its focus on one component, Prim’s algorithm is somewhat easier to 1833 implement than Boruvka’s. The ultimate version of Prim’s algorithm can only be taken 1834 up in Chapter VI (amortization techniques).
1835 ¶40. Good sets of vertices. Let us extend the notion of “goodness” to sets of vertices. For 1836 any set T ⊆ E of edges, let V (T) denote the set of vertices that are incident on some edge of 1837 T. We say a set S ⊆ V is X-good if there exists an X-good set T ⊆ E such that S = V (T). 1838 Here, X is equal to
‘minimally’, ‘Prim’, ‘Kruskal’ or ‘Boruvka’. We also declare any singleton
1839 set with only one vertex to be X-good.
1840 ¶41. Boruvka’s MST Algorithm. Let T ⊆ E be Boruvka-good, and G|T = (V,T). If C
1841 is a connected component of G|T, an edge e = (u − v) where u ∈ C and v /∈ C is called an
1842 outgoing edge of C. Recall that ife has minimum cost among all outgoing edges of C, then
1843 the extension T + e is Boruvka-good. If G|T has k connected components, we pick one such
1844 minimum outgoing edge for each component. Let ei be the edge picked edge for component Ci 1845 (i = 1,…,k). Our goal want to extend T to
Add T0 ← T {e1,…,ek}.(49)
Next, we need to be sure that T0 in (49) is acyclic. How might a cycle arise? Consider a cycle of m ≥ 2 distinct components of the form
[C1,C2,…,Cm]
1846 such that Cj picks ej = (uj − vj) where uj ∈ Cj and vj ∈ Cj+1 (assume Cm+1 = C1 in this 1847 notation). Let wj be the cost of ej. Since Cj+1 picks ej+1 but not ej. it implies wj+1 ≤ wj for all 1848 j = 1,…,m. Since these m inequalities creates a cycle, we conclude that w1 = w2 = ··· = wm.
1849 Note that if m = 2, this does not constitute a cycle since e1 = e2. However, if m ≥ 3, 1850 then we have a cycle. To prevent cycles, we now assume some tie-breaking rule among edges 1851 with the same cost so that they are totally ordered. We now claim that no cycle can arise for 1852 m ≥ 3. By way of contradiction, suppose we have a cycle. Then the set {ej : j = 1,…,m} has
1853 m distinct edges. Wlog, assume e1 is the minimum edge of {ej : j = 1,…,m}. Since e1 and e2 1854 are incident on C2, our tie breaking rule implies that C2 must pick e1 and not e2, contradiction.
1855 Thus our tie breaking rule implies T0 is acyclic. It follows that each of the edges e1,…,ek0
1856 reduces the number of components in T by 1. Thus T0 has k −k0 components. Since T0 has at 1857 least one component, k − k0 ≥ 1 or k > k0. In summary:
the number k0 of distinct edge in the set {e1,e2,…,ek}
(50) is between k/2 and k − 1, and T ∪ {e1,…,ek} is acyclic.
1858 This extension of T by simultaneously adding k0 ≥ k/2 edges is called a “phase”. These k0 1859 edges could be chosen “in parallel” if we were using parallel computers. But since we only 1860 consider on sequential algorithms, here is the conventional form of this algorithm.
1861
1862
Boruvka’s MST Algorithm
Input: G = (V,E;C) a connected graph
Output: MST T ⊆ E of G
T ← ∅ / Initialize a Boruvka-good set of edges
While (|T| < n − 1) for each connected component C of G|T, / Do
Phase e ← argmin{C(e) : e = (u − v),u ∈ C,v /∈ C} T ← T + {e}
Assignment Project Exam
Help
1863
1864 How many phases can there be? If G|S has k components, and we form T0 by adding k0
1865 distinct edges to T, thenG|T0 has k − k0 connected components. From (50), we conclude that
1866 1 ≤ k − k0 ≤ k/2. In other words, the number of connected components it at least halved. 1867 Since we started with n components, the number of phases is at most lgn. We next show that 1868 each phase can be computed in time O(m + n), and so the overall complexity of Boruvka’s 1869 algorithm is O((m + n)logAdd n).
1870 ¶42. Implementation of a Phase. We now show how to implement a phase of Boruvka’s 1871 algorithm in time O(m + n). The key subroutine is a method to compute the connected 1872 components of a bigraph. In ¶IV.23, we have provided such an algorithm based on BFS.
1873 • The main data structure is an array CC[1..n] to keep track of the connected components
1874 of G|T. For each i ∈ {1,…,n} = V , let CC[i] refer to an arbitrary but fixed vertex j
1875 in the connected component of i. This j is called the representative of that connected 1876 component. In particular, we always have CC[j] = j. Equivalently, we have an “idempo1877 tent” property: for all i, CC[i] = CC[CC[i]]. Initially, T = ∅ and hence we have CC[i] = i 1878 for all i. Assume inductively that the array CC[1..n] is available at the beginning of the 1879 phase. If CC[i] = j, then we say i belongs to component j.
1880 • Next, we shall compute the minimum outgoing edge for each connected component with 1881 the help of an array, A[1..n]. Let A[j] store the current minimum outgoing edge from 1882 component
j. We initialize A[j] ← nil, reflecting the fact that no outgoing edges are 1883 initially known. Note that if there are k components, then only k entries of the arrays A 1884 are in use. We incrementally update A as follows:
For each edge (i − j) ∈ E,
If CC[i] 6= CC[j] / (i − j) is an outgoing edge of component of i If the cost of A[CC[i]] is “greater” than C(i − j) A[CC[i]] ← (i − j).
1885
1886
1887 We write
“greater” in quotes because in case of ties, we must break ties uniquely. One
1888 way is this: assume that the set E is totally sorted by <E. we say the cost of e ∈ E is 1889 “greater” than the cost of e0 ∈ E if C(e) > C(e0) or else C(e) = C(e0) and e >E e0. This 1890 is essential to avoid cycles. At the end of this for-loop, it is clear that the array A has 1891 the desired information.
1892 • We must now extend the set T to T0: this amounts to updating the array CC[1..n] for 1893 the next phase. Imagine the reduced graph Gr = (V r,Er) whose vertices are the set of 1894 representatives of connected components in G|S, and whose edges are the edges in A[1..n]. 1895 Viewed as a bigraph, our goal is to compute the connected components of Gr. For each 1896 i ∈ V , we retrieve the edge (j − k) ← A[CC[i]]. We add CC[i] to V r and (CC[j] − CC[k]) 1897 to Er. Then we use a BFS Driver to compute the connected components of Gr. Assume 1898 (see ¶IV.23) that the BFS Driver returns an array CCr such that for each j ∈ V r, we have 1899 CCr[j] is a representative vertex in the connected component of j. Now we update CC 1900 with the help of CCr:
For each i ∈ V ,
CC[i] ← CCr[CC[i]]
1901 1902
1903 This concludes the phase.
1904 Remarks: Boruvka (1926) has the first MST algorithm; his algorithm was rediscovered 1905 by Sollin (1961). The algorithm attributed to Prim (1957) was discovered earlier by Jarn´ık
1906 (1930). These algorithms have been rediscovered many times. See[10] for further references.
1907 Both Boruvka and Jarn´ık’s work are in Czech. The Prim-Jarn´ık algorithm is very similar in 1908 structure to Dijkstra’s algorithm which we will encounter in the chapter on minimum cost 1909 paths. Add
1910 Exercises
Exercise 6.1: Consider the bigraph G5 with vertex set V = {a,b,c,d,e} in Figure 10. We change its cost function C as follows: view G5 as an Euclidean graph where each vertex v ∈ V is a point pos(v) ∈ R2:
pos(a) = (5,2),pos(b) = (0,2),pos(c) = (0,0),pos(d) = (5,0),pos(d) = (8,1).
The cost of an edge u − v is the Euclidean distance between pos(u) and pos(v). E.g.,
√
C(a − c) = kpos(a) − pos(c)k = k(5,2) − (0,0)k = p52 + 22 = 29.
1911 Run Prim’s algorithm
and Kruskal’s algorithm on this bigraph. ♦ 1912 Exercise 6.2: We consider minimum spanning trees (MST’s) in an undirected graph G = 1913 (V,E) where each vertex v ∈ V is given a numerical value C(v) ≥ 0. The cost C(u,v) of 1914 an edge (u − v) ∈ E is defined to be C(u) + C(v). 1915 (a) Let G be the graph in Figure 14.
1916 Compute an MST of G using Boruvka’s algorithm. Please organize your computation so 1917 that we can verify intermediate results. Also state the cost of your minimum spanning
1918 tree.
1919 (b) Can you design an MST algorithm that takes advantage of the fact that edge costs 1920 has the special form C(u,v) = C(u) + C(v)? ♦

Figure 14: The house graph: The cost of edge vi − vj is defined as C(vi) + C(vj), where C(v) is the value indicated next to v. E.g. C(v1 − v4) = 1 + 6 = 7.
1921 Exercise 6.3: Redo the previous problem with a different cost function, where C(u − v) =
1922 C(u)C(v) (the product instead of the sum). ♦
Exercise 6.4:Simulating Prim’s and Kruskal’s Algorithm. Consider the graph Gag in Figure 15 with edge costs. In simulations, please do it ”canonically” meaning that if there is a choice, pick the smallest index vertex or value first.
Add
Figure 15: Graph Gag
(a) Simulate Prim’s algorithm using the tabular form shown in the text. At the end, list the edges and total cost of the MST.
(b) Simulate Kruskal’s algorithm by listing the sorted edges and then accepting or rejecting each in increasing order of cost. Is your Kruskal MST the same as the Prim MST?
(c) Although the sorted sequence in Kruskals algorithm has length m, we know that Kruskal’s algorithm can stop as soon as it has accepted n − 1 edges. Prove that in the worst case, Kruskal’s algorithm needs to examine Ω(n2) edges. How to show such a result?
Show this: there is an infinite family
Gn = (Vn,En;Cn), |Vn| = n
1923 of inputs for the MST problem such that Kruskal’s algorithm on Gn must examine Ω(n2)
1924 edges in the worst case. ♦
1925 Exercise 6.5: Suppose G is the complete bipartite graph Gm,n. That is, the vertices V are 1926 partitioned into two subsets V0 and V1 where |V0| = m and V1| = n and E = V0 × V1. 1927 Give a simple description of an MST of Gm,n. Argue that your description is indeed an 1928 MST. HINT: transform an arbitrary MST into your description by modifying one edge
1929 at a time. ♦
1930 Exercise 6.6: Let Gn be the bigraph whose vertices are V = {1,2,…,n}. It has two kinds
1931 of edges:
1932 (i) Prime edges: for each i ∈ V , if i is prime, then (1,i) ∈ E with cost i. [Recall that 1 1933 is not considered prime, so 2 is the smallest prime.]
1934 (ii) Divisibility edges: For 1 < i < j, if i divides j then we add (i,j) to E with cost 1935 j/i (which is an integer).
1936 (a) Draw the graph G10.
1937 (b) Compute the MST of G10 using Prim’s algorithm, using node 1 as the source vertex.
1938 State the cost of the MST.
1939 (c) Repeat part(b) but using Kruskal’s algorithm.
1940 (d) Repeat part(b) but using Boruvka’s algorithm. [Organize Boruvka’s simulation in a
1941 Phase-by-Phase manner] ♦
Exercise 6.7: Consider the weighted bigraph G7 in Figure 16. Add
Figure 16: Graph G7
1942
1943 (a) Please compute the MST of G7 using Kruskal’s algorithm.
What is the cost of the
1944 MST?
1945
1946 (b) Please compute the MST of G7 using Prim’s algorithm. You must also list the edges
1947 of the MST.
1948 ♦
1949 Exercise 6.8:
MST Update Problem: we are given a connected weighted bigraph G = (V,E;C) 1950 where the cost of edges can change. Suppose you have already computed an
MST T. Now
1951 C(u − v) is changed for some edge (u − v) ∈ E. This question is coupled with part(a) 1952 of the previous question: we assume you have computed an MST for the graph G7 in 1953 Figure 16). Consider two cases.
1954 (i) Suppose (u − v) ∈ T, and C(u − v) is increased. How can you update T? You do 1955 not need to justify why it is correct. Illustrate your method by explaining how MST 1956 T of G7 is updated when C(e − f) changes from 3 to 10.
1957 (ii) Suppose (u − v) 6∈ T, and C(u − v) is decreased. How can you update T? Illustrate 1958 your method by explaining how MST T of G7 is updated when C(c − d) changes 1959 from 11 to 3.
1960 ♦
1961 Exercis
e 6.9: Let G = (V,E;W)
be a connect ed bigraph with edge weight functio n W. Fix a 1962 constan t M and define the weight functio n W0 where W0(e)
= M
−W(e)
for each e ∈ E.
1963
Let G0
=
(V,E;W0 ). Show that T
is a
maxim um spanni
ng tree of G iff T is a
minimu m
1964 spanning tree of G0. NOTE: Thus we say that the concepts of maximum spanning tree 1965 and minimum spanning tree are “cryptomorphic versions” of each other. ♦
1966 Exercise 6.10: Describe the rule for reconstructing the MST from the matrix M using in our
1967 hand-simulation of Prim’s Algorithm. ♦
1968 Exercise 6.11: Hand simulation of Kruskal’s Algorithm on the graph of Figure 14. This 1969 exercise suggests a method for carry out the steps of this algorithm. We consider each 1970 edge in their sorted order, maintaining a partition of V = {1,…,12} into disjoint sets. 1971 Let L(i) denote the set containing vertex i. Initially, each node is in its own set, i.e., 1972 L(i) = {i}. Whenever an edge i − j is added to the MST, we merge the corresponding 1973 sets L(i) ∪ L(j). E.g., in the first step, we add edge 1 − 3. Thus the lists L(1) = {1}
1974 and L(3) = {1} are merged, and we get L(1) = L(3) = {1,3}. To show the computation
1975 of Kruskal’s algorithm, for each edge, if the edge is “rejected”, we mark it with an “X”.
1976 Otherwise, we indicate the merged list resulting from the union of L(i) and L(j): Please 1977 fill in the last two columns of the table (we have filled in the first 4 rows for you).
1 1 − 3: 1 {1,3} 1
2 6 − 11: 1 {6,11} 2
3 10 − 11: 1 {6,10,11} 3
4 6 − 10: 2 X 3
5 7 − 11: 2
6
7
8
9
10 11 − 12:
1 − 2:
3 − 8:
6 − 7:
7 − 10: 2
3
3 3
3 at po
11
12
13
14
15 2 − 5:
3 − 4:
5 − 7:
5 − 12:
9 − 10: 6
6 6
6
6
16
17
18
19
20 1 − 4:
4 − 6:
8 − 9:
4 − 5:
4 − 9: 7
7
8
10
11
Sorting OrderEdge
Weight Merged List Cumulative Weight
1978
1979 ♦
1980 Exercise 6.12:
This question considers two concrete ways to implement Kruskal’s algorithm.
1981 Let V =
{1,2,…,n} and D[1..n] be an array of size n that represents a forest G(D) 1982 with vertex set V and edge set E = {(i,D[i]) : i ∈
V }. More precisely,
G(D) is an
1983 directed graph that has no cycles except for self-loops (i.e., edges of the form (i,i)). 1984 A vertex i such that D[i] = i is called a root. The set V is thereby partitioned into 1985 disjoint subsets V = V1 ∪ V2 ∪ ··· ∪ Vk (for some k ≥ 1) such that each Vi has a unique 1986 root ri, and from every j ∈ Vi there is a path from j to ri. For example, with n = 7, 1987 D[1] = D[2] = D[3] = 3, D[4] = 4, D[5] = D[6] = 5 and D[7] = 6 (see Figure 17). We 1988 call Vi a component of the graph G(D) (this terminology is justified because Vi is a 1989 component in the usual sense if we view G(D) as an undirected graph).
1990 (i) Consider two restrictions on our data structure: Say D is list type if each component 1991 is a linear list. Say D is star type if each component is a star (i.e., each vertex in the

V1 V2 V3
Figure 17: Directed graph G(D) with three components (V1,V2,V3)
1992 component points to the root). E.g., in Figure 17, V2 and V3 are linear lists, while V1
1993 and V2 are stars. Let ROOT(i) denote the root r of the component containing i. Give a 1994 pseudocode for computing ROOT(i), and give its complexity in the 2 cases: (1) D is list 1995 type, (2) D is star type.
1996 (ii) Let COMP(i) ⊆ V denote the component that contains i. Define the operation 1997 MERGE(i,j) that transforms D so that COMP(i) and COMP(j) are combined into a 1998 new component (but all the other components are unchanged). E.g., the components in
1999 Figure 17 are {1,2,3},{4} and {5,6,7}. After MERGE(1,4), we have two components,
2000 {1,2,3,4} and {5,6,7}. Give a pseudo-code that implements MERGE(i,j) under the
2001 assumption that i,j are roots and D is list type which you must preserve. Your algorithm 2002 must have complexity O(1). To achieve this complexity, you need to maintain some 2003 additional information (perhaps by a simple modification of D).
2004 (iii) Similarly to part (ii), implementMERGE(i,j) when D is star type. Give the 2005 complexity of your algorithm.
2006 (iv) Describe how to use ROOT(i) and MERGE(i,j) to implement Kruskal’s algorithm
2007 for computing the minimum spanning tree (MST) of a weighted connected undirected
2008graph H. Add
2009 (v) What is the complexity of Kruskal’s in part (iv) if (1) D is list type, and if (2) D is 2010 star type. Assume H has n vertices and m edges. ♦
2011 Exercise 6.13: Give two alternative proofs that the suggested algorithm for computing mini-
2012 mum base is correct:
2014 (b) By replacing the cost C(e) (for each e ∈ E) by the cost c0 − C(e). Choose c0 large
2015 enough so that c0 − C(e) > 0. ♦
2025 (S,I;C) to the MIS problem for (S,I;C0) where C0 is a suitable transformation of C. See 2026 next section for matroid definitions.
2027 (a) Student Joe considers the modified cost function C0(e) = 1/C(e) for each e. Construct 2028 an example to show that the MIS solution for C0 need not be the same as the minimum 2029 base solution for C.
2030 (b) Next, student Joe considers another variation: he now defines C0(e) = −C(e) for each
2031 e. Again, provide a counter example. ♦
2032 Exercise 6.17: Extend the algorithm to finding MIS in contracted matroids. ♦
2033 Exercise 6.18: If T ⊆ E is Prim-good, then clearly G0 = (V (T),T) is clearly a tree. Prove 2034 that T is actually an MST of the restricted graph G0. ♦
2035 Exercise 6.19: Given a costed bigraph G = (V,E;C), let MST(G) denote the set of all MST’s 2036 of G. Define MST exchange graph Exch(G) of G to be the bigraph (MST(G),H) 2037 whose nodes are MST’s and whose edges T − T0 ∈ H are characterized by this property: 2038 the symmetric difference T ⊕ T0 = (T T) ∪ (T0 T) has size 2.
2039 (a) Let G be bigraph in Figure 11. Draw the MST exchange graph Exch(G5), assuming 2040 that is comprised of the 5 listed MST’s.
2041 (b) Prove that if T 6= T0 ∈ MST(G), then there exists e ∈ T T0 and e0 ∈ T0 T such 2042 that T + e0 − e ∈ MST(G). Conclude that Exch(G) is a connected graph. ♦ 2043 Exercise 6.20: Refer to the graph in Figure 11.
2044 (a) List all the X-good sets of size 1 for the graph in this figure, where X=Kruska, Boruvka 2045 or Prim. For Prim-goodness, assume that node a is the source in Figure 10.
2046 (b) Repeat part(a) but for sets of sizeAdd 2. ♦
2047 Exercise 6.21: (a) Let G5 be the bigraph in Figure 11. Prove that there are no other MST’s 2048 other than the 5 which are shown.
2049 (b) Draw the exchange graph if all the edges in Figure 11 are unit costs? ♦
2050 Exercise 6.22:
2051 (a) Enumerate the X-good sets of vertices in Figure 10. Here, X is ‘minimally’, ‘Kruskal’, 2052 ‘Boruvka’ or ‘Prim’.
2053 (b)
Characterize
the good
singletons
(relative to any of the three notions of goodness).
2054 ♦
2055 Exercise 6.23:
This question will develop Boruvka’s approach to MST: for each vertex v, pick 2056 the edge (v − u) that has the least cost among all the nodes u that are adjacent to v. 2057 Let P be the set of edges so picked. 2058 (a) Show that n/2 ≤ P ≤ n − 1. Give general examples to show that these two extreme 2059 bounds are achieved for each n.
2060 (b) Show that if the costs are unique, P cannot contain a cycle. What kinds of cycles can 2061 form if weights are not unique?
2062 (c) Assume edges in P are picked with the tie breaking rule: among the edges v − ui
2063 (i = 1,2,…) adjacent to v that have minimum cost, pick the ui that is the smallest 2064 numbered vertex (assume vertices are numbered from 1 to n). Prove that P is acyclic 2065 and has the following property: if adding an edge e to P creates a cycle Z in P +e, then 2066 e has the maximum cost among the edges in Z.
2067 (d) For any costed bigraph G = (V,E;C), and P ⊆ E, define a new costed bigraph 2068 denoted G/P as follows. First, two vertices of V are said to be equivalent modulo P if
2069 they are connected by a sequence of edges in P. For v ∈ V , let [v] denote the equivalence 2070 class of v. The vertex set of G/P is {[v] : v ∈ V }. The edge set of G/P comprises those
2071 ) such that there exists an edge (u0 − v0) ∈ E where u0 ∈ [u] and v0 ∈ [v]. The cost v
2072 of ([u] −) is defined as min{C(u0,v0) : u0 ∈ [u],v0 ∈ [v],(u0 − v0) ∈ E}. Note that G/P
2073 has at most n/2 vertices. Moreover, we can pick another set P0 of edges in G/P using the 2074 same rules
as before. This gives us another graph (G/P)/P0 with at most n/4 vertices. 2075 We can continue this until V has 1 vertex. Please convert this informal description into
2076 an algorithm to compute the cost of the MST. (You need not show how to compute the
2077 MST.)
2078 (e) Determine the complexity of your algorithm. You will need to specify suitable data 2079 structures for carrying out the operations of the algorithm. (Please use data structures
2080 that you know up to this point.) ♦
2081 Exercise 6.24: (Tarjan) Consider the following generic accept/reject algorithm for MST. 2082 This consists of steps that either accept or reject edges. In our generic MST algorithm,
2084 in the case of Kruskal’s algorithm. Let S,R be the sets of accepted and rejected edges (so 2085 far). We say that (S,R) is minimally-good if there is an MST that contains S but not
2086 containing any edge of R. Note that this extends our original definition of “minimally
2087 good”. Prove that the following extensions ofS and R will maintain minimal goodness:
2088 (a) Let U ⊆ V be any subset of vertices. The set of edges of the form (u,v) where u ∈ U
2091 (b) If e is the maximum cost edge in a cycle C and there are no rejected edges in C then
2093 Exercise 6.25: With respect to the generic accept/reject version of MST:
2096 (b) Can the rule in part (a) be fixed by some additional properties that we can maintain?
2097 (c) Can you make the criterion for rejection in the previous exercise (part (b)) compu2098 tationally effective? Try to invent the “inverses” of Prim’s and Boruvka’s algorithm in 2099 which we solely reject edges.
2100 (d) Is it always a bad idea to only reject edges? Suppose that we alternatively accept and
2101 reject edges. Is there some situation where this can be a win? ♦
2102 Exercise 6.26: Consider the following recursive “MST algorithm” on input G = (V,E;C):
2103 (I) Subdivide V = V1 ] V2.
2104 (II) Recursive find a “MST” Ti of G|Vi (i = 1,2).
2105 (III) Find e in the V1-cut of minimum cost. Return T1 + e + T2.
2106 Give a small counter example to this algorithm. Can you fix this algorithm? ♦
2107 Exercise 6.27: Is there an analogue of Prim and Boruvka’s algorithm for the MIS problem 2108 for matroids? ♦
2109 Exercise 6.28: Let G = (V,E;C) be the complete graph in which each vertex v ∈ V is a point

2110 in the Euclidean plane and C(u,v) is just the Euclidean distance between the points u
2111 and v. Give efficient methods to compute the MST for G. ♦
2112 Exercise 6.29: Fix a connected undirected graph G = (V,E). Let T ⊆ E be any spanning 2113 tree of G. A pair (e,e0) of edges is called a swappable pair for T if 2114 (i) e ∈ T and e0 ∈ E
T.
2115 (ii) The set (T {e}) ∪ {e0} is a spanning tree.
2116 Let T(e,e0) denote the spanning tree (T {e}) ∪ {e0} obtained from T by swapping e 2117 and e0 (see illustration in Figure 18(a), (b)).
u1
u`
u
(a) T (b) T(e,e0) (c) Path P(u0,u`).
Figure 18: (a) A swappable pair(e,e0) for spanning tree T. (b) The new spanning tree T(e,e0) [NOTE: tree edges are indicated by thick lines]
2118 (a) Suppose (e,e0) is a swappable pair for T and e0 = (u,v). Prove that e lies on the unique 2119 path, denoted by PAdd (u,v), of T from u to v. In Figure 18(a), e0 = (1 − 5) = (5 − 1). So 2120 the path is either P(1,5) = (1 − 2 − 3 − 5) or P(5,1) = (5 − 3 − 2 − 1).
2121 (b) Let n = |V |. Relative to T, we define a n×n matrix First indexed by pairs of vertices 2122 u,v, where First[u,v] = w means that the first edge in the unique path P(u,v) is (u,w). 2123 (In the special case of u = v, let First[u,u] = u.) In Figure 18(a), First[1,5] = 2 and 2124 First[5,1] = 3. Show the matrix First for the tree T in Figure 18(a). Similarly, give the 2125 matrix First for the tree T(e,e0) in Figure 18(b).
2126 (c) Describe an O(n2) algorithm called Update(First,e,e0) which updates the matrix 2127 First after we transform T to T(e,e0). HINT: For which pair of vertices (x,y) does the 2128 value of First[x,y] have to change? Suppose e0 = (u0,v0) and P(u0,v0) = (u0,u1,…,u`) 2129 is as illustrated in Figure 18(c). Then u0 = u0,v0 = u`, and also e = (uk,uk+1) for some 2130 0 ≤ k < `. Then, originally First[u0,u`] = u1 but after the swap, First[u0,u`] = u`. 2131 What else must change?
2132 (d) Analyze your algorithm to show that that it is O(n2). Be sure that your description
2133 in (c) is clear
enough to support this analysis.
♦
2134 End Exercises
2135 §7. Matroids
2136 An abstract structure that supports greedy algorithms is matroids. Indeed, we will see that 2137 Kruskal’s algorithm for MST is an instance of a general greedy method to solve a matroid 2138 problem. We first illustrate the idea of matroids.
2139 ¶43. Graphic matroids. Let G = (V,S) be a bigraph. A subset A ⊆ S is acyclic if it does 2140 not contain any cycle. The I comprising all acyclic subsets of S is called the graphic matroid 2141 of G. Let us prove 2 critical proper We note two properties of I:
2142 Hereditary property: If A ⊆ B and B ∈ I then A ∈ I. In particular, the empty set belongs
2143 to I.
2144 Exchange property: If A,B ∈ I and |A| < |B| then there is an edge e ∈ B − A such that 2145 A ∪
{e} ∈ I.
2146 The hereditary property is obvious. To prove the exchange property, note that the subgraph 2147 G|A:=(V,A) has |V | − |A| (connected) components; similarly the subgraph G|B :=(V,B) has 2148 |V | − |B| components. CLAIM: There exists a component U ⊆ V of G|B that is not contained 2149 in any component of G|A. [Pf: If every component U ⊆ V of G|B is contained in some 2150 component of U0 of G|A, then |V | − |B| < |V | − |A| implies that some component of G|A 2151 contains no vertices, contradiction.] Let T :=B|U be the restriction of B to U. Since U is a
2152 component, the graph (U,T) is a spanning tree. Hence there exists an edge e = (u − v) ∈ T
2153 such that u and v belongs to different components of G|A. This e will serve for the exchange 2154 property: that is,A + e contains no cycle and hence A + e ∈ I.
For example, in Figure 10 the sets A = {a − b,a − c,a − d} and B =
are acyclic. Then the exchange property between A and B is wit- 2157 nessed by the edge d − e∈ B A, since adding d − e to A will result in an acyclic set.
¶44. Matroids. The above system (V,I) is called the graphic matroid corresponding to graph G = (V,S). In general, aAdd matroid is a hypergraph
M = (S,I)
2158 with special properties: S and I ⊆ 2S are both non-empty sets such that I has both the 2159 hereditary and exchange properties. The set S is called the ground set. Elements of I are 2160 called independent sets; other subsets of S are called dependent sets. Note that the empty 2161 set ∅ is always a member of I.
2162 Another example of matroids arise with numerical matrices: for any matrix M, let S be its 2163 set of columns, and I be the family of linearly independent subsets of columns. Call this the 2164 matrix matroid of M. The terminology of independence comes from this setting. This was 2165 the motivation of Whitney, who coined the term ‘matroid’.
2166 The explicit enumeration of the set I is usually out of the question. So, in computational 2167 problems whose input is a matroid (S,I), the matroid is usually implicitly represented. The
2168 above examples illustrate this: a graphic matroid is represented by a graph G, and the matrix 2169 matroid is represented by a matrix M. The size of the input is then taken to be the size of G 2170 or M, not of |I| which can exponentially larger.
¶45. Submatroids. Given matroids M = (S,I) and M0 = (S0,I0), we call M0 a submatroid of M if S0 ⊆ S and I0 ⊆ I. There are two general methods to obtain submatroids, starting from a non-empty subset R ⊆ S:
(i) Induced submatroids. The R-induced submatroid of M is
M|R := (R,I ∩ 2R).
(ii) Contracted submatroids. The R-contracted submatroid of M is
M ∧ R := (R,I ∧ R)
2171 where I ∧ R:={A ∩ R : A ∈ I,S − R ⊆ A}. Thus, there is a bijective correspondence between 2172 the independent sets A0 of M ∧ R and those independent sets A of M which contain S − R. 2173 Indeed, A0 = A ∩ R. Of course, if S − R is dependent, then I ∧ R is empty.
2174 We leave it to an exercise to show that M|R and M ∧ R are matroids. Special cases of 2175 induced and contracted submatroids arise when R = S − {e} for some e ∈ S. In this case, we 2176 say that M|R is obtained by deleting e and M ∧ R is obtained by contracting e.
2182 “A ⊆ R being a base of R”, “e extends A in R”, etc. This is the same as viewing A as a set of 2183 the induced submatroidM|R.
M|R). The rank functionAdd
rM : 2S → N
2184 simply assigns the rank of R ⊆ S to rM(R).
2185 ¶48. Problems on Matroids. A costed matroid is given by M = (S,I;C) where (S,I)
2186 is a matroid and C : S → R. is a cost function. The cost of a set A ⊆ S is just the sum 2187 Px∈A C(x). The maximum independent set problem (abbreviated, MIS) is this: given a 2188 costed matroid
(S,I;C), find an independent set A ⊆ S with maximum cost. A closely related
2189 problem is the maximum base problem where, given (S,I;C), we want to find a base B ⊆ S
2190 of maximum cost. If the costs are non-negative, then it is easy to see the MIS problem and 2191 the maximum base problem are identical. The following algorithm solves the maximum base 2192 problem:
Greedy Algorithm for Maximum Base:
Input: matroid M = (S,I;C) with cost function C.
Output: a base A ∈ I with maximum cost.
1. Sort S = {x1,…,xn} by cost.
Suppose C(x1) ≥ C(x2) ≥ ··· ≥ C(xn).
2. Initialize A ← ∅.
3. For i = 1 to n, put xi into A provided this does not make A dependent.
4. Return A.
2193
2194
2195
2196 The steps in this abstract algorithm needs to be instantiated for particular representations
2197 of matroids. In particular, testing if a set A is independent is usually non-trivial (recall that 2198 matroids are usually given implicitly in terms of other combinatorial structures). We discuss 2199 this issue for graphic matroids below. It is interesting to note that the usual Gaussian algorithm 2200 for computing the rank of a matrix is an instance of this algorithm where the cost C(x) of each 2201 element x is unit.
2202 Let us see why the greedy algorithm is correct.
Lemma 17 (Correctness) Suppose the elements of A are put into A in this order: z1,z2,…,zm,
2203 where m = |A|. Let Ai = {z1,z2,…,zi}, i = 1,…,m. Then:
2204 1. A is a base.
2205 2. If x ∈ S extends Ai then i < m and C(x) ≤ C(zi+1).
2206 3. Let B = {u1,…,ukAdd } be an independent set where C(u1) ≥ C(u2) ≥ ··· ≥ C(uk). Then
2207 k ≤ m and C(ui) ≤ C(zi) for all i. 2208
2209 Proof.1. By way of contradiction, suppose x ∈ S extends A. Then x 6∈ A and we must have 2210 decided not to place x into the set A at some point in the algorithm. That is, for some j ≤ m, 2211 Aj ∪ {x} is dependent. This contradicts the hereditary property because Aj ∪ {x} is a subset 2212 of the independent set A ∪ {x}.
2213 2. Suppose x extends Ai. By part 1, i < m. If C(x) > C(zi+1) then for some j ≤ i, we must 2214 have decided not to place x into Aj. This means Aj ∪ {x} is dependent, which contradicts the 2215 hereditary property since Aj ∪ {x} ⊆ Ai ∪ {x} and Ai ∪ {x} is independent.
2216 3. Since all bases are independent sets with the maximum cardinality, we have k ≤ m. The 2217 result is clearly true for k = 1 and assume the result holds inductively for k − 1. So C(uj) ≤ 2218 C(zj) for j ≤ k − 1. We only need to show C(uk) ≤ C(zk). Since |B| > |Ak−1|, the exchange 2219 property says that there is an x ∈ B −Ak−1 that extends Ak−1. By part 2, C(zk) ≥ C(x). But 2220 C(x) ≥ C(uk), since uk is the lightest element in B by assumption. Thus C(uk) ≤ C(zk), as 2221 desired. Q.E.D.
2222 From this lemma, it is not hard to see that an algorithm for the MIS problem is obtained 2223 by replacing the for-loop (“for i = 1 to n”) in the above Greedy algorithm by “for i = 1 to m” 2224 where xm is the last positive element in the list (x1,…,xm,…,xn).
2225 ¶49. Greedoids. While the matroid structure allows the Greedy Algorithm to work, it 2226 turns out that a more general abstract structure called greedoids is tailor-fitted to the greedy

2227 approach. To see what this structure looks like, consider the set system (S,F) where S is a 2228 non-empty finite set, and F ⊆ 2S. In this context, each A ∈ F is called a feasible set. We 2229 call (S,F) a greedoid if
2230 Accessibility property If A is a non-empty feasible set, then there is some e ∈ A such that 2231 A {e} is feasible.
2232 Exchange property: If A,B are feasible and |A| < |B| then there is some e ∈ B A such 2233 that A ∪ {e} is feasible.
2234
2235 Exercises
2236 Exercise
7.1:
Consider the graphic matroid in Figure 10. Determine
its rank function.
♦
2237 Exercise
7.2: The text described a
modificatio
n of the
Greedy
Maximum
Base Algorithm so
2238 that it will solve the MIS problem. Verify its correctness.♦ 2239 Exercise 7.3:
2240 (a) Interpret the induced and contracted submatroidsM|R and M ∧ R in the bigraph of
2241 Figure 10, for various choices of the edge set R. When is M|R = M ∧ R? 2242 (b) Show that M|R and M ∧ R are matroids in general. ♦ Add
2243 Exercise 7.4: Show that rM(A ∪ B) + rM(A ∩ B) ≤ rM(A) + rM(B). This is called the 2244 submodularity property of the rank function. It is the basis of further generalizations
2245 of matroid theory. ♦
2246 Exercise 7.5: In Gavril’s activities selection problem, we have a set A of intervals of the form 2247 [s,f). Recall that a subset S ⊆ A is said to be compatible if S is pairwise disjoint. Does
2248 the set of compatible subsets of A form a matroid? If yes, prove it. If no, give a counter
2249 example. ♦
2250 End Exercises
2251 §8. Generating Permutations
2252 In §1, we saw how the general bin packing problem can be reduced to linear bin packing. 2253 This reduction depends on the ability to generate all permutations of n elements efficiently. 2254 Since there are many uses for such permutation generators, we take a small detour from greedy 2255 methods in order to address this interesting topic. A survey of this classic problem is given by 2256 Sedgewick [9]. Perhaps the oldest incarnation of this problem is the “change ringing problem” 2257 of bell-ringers in early 17th Century English churches [8]. This calls for ringing a sequence of 2258 n bells in all n! permutations.
2259 ¶50. Combinatorial Enumeration Problems. The problem of generating all permu2260 tations efficiently is representative of the important class of combinatorial enumeration 2261 problems. For instance, we might want to generate all k-sets (i.e., subsets of size k) of a 2262 set, all graphs of size n, all convex polytopes based some given set of n vertices, etc. Such an 2263 enumerations would be considered optimal if the algorithm takes O(1) time to generate each 2264 member.
2268 Here we are interested in the case n = |X|, i.e., permutation of distinct elements. We use a 2269 path-like notation for permutations, writing “(p(1) − p(2) − ··· − p(n))” for the permutation 2270 (p(1),p(2),…,p(n)).
Example: let X = {a,b,c} and n = 4. Two 4-permutations of X are (a − a − b − c) and ). However, (a − b − c) and (a − b − a − b) are not 4-permutations of X.
2273 The set of all n-permutations of X = {1,2,…,n} is rather special, and is denoted Sn. Each
2274 element of Sn is simply called an n-permutation (i.e., X is implicitly {1,…,n}). Note that 2275 |Sn| = n!. Here is an enumeration ofS3:
(1 − 2 − 3), (1 − 3 − 2), (3 − 1 − 2); (3 − 2 − 1), (2 − 3 − 1), (2 − 1 − 3). (51)
2276 Two n-permutations π = (x1 − ··· − xn) and ) are adjacent (to
2277 each other) if the two permutations are identical except that for somei = 2,…,n, we have
). In other words, (x0i−1,x0i) and (xi−1,xi) are interchanged. We write 2279 π0 = Exchi(π) in this case, and call π0 an exchange of π (and vice-versa). E.g., π = (1 − 2 − 2280 4 − 3) and π0 = (1 − 4 − 2 − 3) are adjacent since π0 = Exch3(π). Add
2281 An adjacency ordering of a set S of permutations is a listing of the elements of S such 2282 that every pair of consecutive permutations in this listing are adjacent. For instance, the listing 2283 of S3 in (51) is an adjacency ordering. The adjacency graph of Sn is the bigraph with vertex 2284 set Sn and edges given by adjacency permutations. For example, the adjacency graph of S3
2285 consists of one cycle given by (51): consecutive permutations in (51) are edges of this graph, 2286 and also the first (1 − 2 − 3) and last (2 − 1 − 3) permutations. Since each permutation in 2287 S3 is adjacent to exactly two other permutations, there are no other edges. Thus this cycle is
2288 unique. We need another concept: if π = (x1 − ··· − xn−1) is an (n−1)-permutation, and π0
2289 is obtained from π by inserting the letter n into π, then we call π0 an extension of π. Indeed, 2290 if n is inserted just before the ith letter in π, then we write π0 = Exti(π) for i = 1,…,n. 2291 When i = n, we intepret “Extn(π)” to mean that we append ‘n’ to the end of the sequence π. 2292 Note that there are n extensions of an (n−1)-permutation. E.g., if π = (1 − 2) then the three 2293 extensions of π are (3 − 1 − 2),(1 − 3 − 2),(1 − 2 − 3).
¶51. The Johnson-Trotter Ordering. Among the several known methods to generate npermutations, we will describe one that is independently discovered by S.M. Johnson and H.F. Trotter (1962), and apparently known to 17th Century English bell-ringers [8]. Hugo Steinhaus (1958) describes the problem of generating permutations by n particles moving along a line moving at variable speeds. The two main ideas in the Johnson-Trotter algorithm are (1) the npermutations are generated as an adjacency ordering, and (2) the n-permutations are generated recursively. Suppose π is an (n−1)-permutation that has been recursively generated.
Then we note that the n extensions of π can given one of two adjacency orderings. It is either
UP(π) : Ext1(π),Ext2(π),…,Extn(π)
or the reverse sequence
DOWN(π) : Extn(π),Extn−1(π),…,Ext1(π).
2294 E.g.,
UP(1 − 2 − 3) ≡ (4 − 1 − 2 − 3), (1 − 4 − 2 − 3), (1 − 2 − 4 − 3), (1 − 2 − 3 − 4). DOWN(1 − 3 − 2) ≡ (1 − 3 − 2 − 4), (1 − 3 − 4 − 2), (1 − 4 − 3 − 2), (4 − 1 − 3 − 2).
Note that if π0 is an (n−1)-permutation that is adjacent to π, then the concatenated sequences
UP(π);DOWN(π0)
and
DOWN(π);UP(π0) 2295 are both adjacency orderings. We have thus shown:
Lemma 18 (Johnson-Trotter ordering) If π1,…,π(n−1)! is an adjacency ordering of
Sn−1, then the concatenation of alternatingDOWN/UPsequences DOWN(π1);UP(π2);DOWN(π3);··· ;DOWN(π(n−1)!)
2296 is an adjacency ordering ofSn.
For example, starting from the adjacency ordering of 2-permutations (π1 = (1 − 2),π2 =
1)), our above lemma says thatAdd DOWN(π1),UP(π2) is an adjacency ordering. Indeed, this is 2299 the ordering shown in (51).
Let us define the permutation graph Gn to be the bigraph whose vertex set is Sn and whose edges comprise those pairs of vertices that are adjacent in the sense defined for permutations. We note that the adjacency ordering produced by Lemma 18 is actually a cycle in the graph Gn. In other words, the adjacency ordering has the additional property that the first and the last permutations of the ordering are themselves adjacent. A cycle that goes through every vertex of a graph is said to be Hamiltonian. If (π1 − π2 − ··· − πm) (for m = (n−1)!) is a Hamiltonian cycle for Gn−1, then it is easy to see that (DOWN(π1);UP(π2);··· ;UP(πm))
2300 is a Hamiltonian cycle for Gn.
2301 ¶52. The Permutation Generator. We proceed to derive an efficient means to generate 2302 successive permutations in the Johnson-Trotter ordering. We need an appropriate high level 2303 view of this generator. The generated permutations are to be used by some “permutation 2304 consumer” such as our greedy linear bin packing algorithm. There are two alternative views
In the following, an n-permutation is represented by the array per[1..n]. We will transform by exchange of two adjacent values, indicated by
per[i] ⇔ per[i − 1] (52)
for some i = 2,…,n, or per[i] ⇔ per[i + 1]
2314 where i = 1,…,n − 1.
¶53. A Counter for n factorial. To keep track of the successive exchanges in JohnsonTrotter generator, we introduce an array of n counters
C[1..n]
2315 where each C[i] is initialized to 1 but always satisfying the relation 1 ≤ C[i] ≤ i. Of course,
2317 array C can holdn! distinct values. We say the i-th counter is full iff C[i] = i. The level of
2318 the C is the largest index ` such that the `-th counter is not full. If all the counters are full, 2319 the level of C is defined to be 1. E.g., the level of C[1..5] = [1,2,3,4,5] is 1, but the level of 2320 C[1..5] = [1,2,2,1,5] is 4.
2321 We define the incrementof this counter array as follows: Let ` be the level of the counter.
2322 If ` = 1, then we reset each C[i] to 1. Otherwise, we increment C[`] and reset C[i] ← 1 for
2323 all i > `. E.g., the increment of C[1..5] = [1,2,3,4,5] is [1,1,1,1,1], and the increment of 2324 C[1..5] = [1,2,2,1,5] is [1Add ,2,2,2,1]. In code:
2325
Inc(C) ` ← n.
While (C[`] = `) ∧ (` > 1) C[`–] ← 1.
If (` > 1) C[`]++.
Return(`)
2326
2327 Note that Inc returns the level of the original counter value.
This macro is a generalization of 2328 the usual increment of binary counters (Chapter 6.1). E.g., for n = 4 and starting with the 2329 initial value C[2,3,4] = [1,1,1], the successive increments of this array produce the following 2330 cyclic sequence:
C[2,3,4] = [1,1,1] → [1,1,2] → [1,1,3] → [1,1,4] (53)
→ [1,2,1] → [1,2,2] → [1,2,3] → [1,2,4] →
[1,3,1] → ···
→ [2,1,1] → ···
→ [2,2,1] → ···
→ [2,3,1] → [2,3,2] → [2,3,3] → [2,3,4] →
[1,1,1] → ··· .
2331 Let the cost of incrementing the counter array be equal to n + 1 − ` where ` is the level.
2332 Lemma 19 The cost to increment the counter array from [1,1,…,1] to [1,2,3,…,n] is < 2333 4(n!).
Proof. The `th counter C[`] is updated at every (n!/`!)th step. In particular, C[n] is updated at every step. So that overall, C[`] is updated `! times. The total cost to update C[`] is therefore (n + 1 − `)`!. Summing up these costs for ` = 2,…,n,
.
2334 Q.E.D.
2335
2336 We can now describe a preliminary version our permutation generator, viewed as a “Shell 2337 Program” with macros:
2338
2339
Input:
where n ≥ 2 and I is application-dependent data
. Initialization per[1..n] ← [1,2,…,n]. / Initial permutation
C[2..n] ← [1,1,…,1]. / Initial counter value
AddINIT(n,I)
. Main Loop do
` ← Inc(C)
Update(`) / The permutation is updated
CONSUME(per,I)
/ Permutation is consumed
While (` > 1)
2340
2341 The input I is applicationdependent. In shell programming, the output is established by 2342 convention to be the value of some global variable(s). We have two shell macros
INIT(n,I) and
2343
CONSUME(per,I) . However,
Update(`) is not a macro, but a subroutine to be described 2344 next – its role is to generate the next permutation encoded in the array per.
2345 Here are two simple applications of this shell:
2346 • Printing all n-permutations: the input I is empty and INIT(n,I) is a NO-OP. The 2347 macro
CONSUME(per) simply print the permutation per.
• Computing Opt(w) in the global bin packing problem. Here the input I is w = (w1,…,wn) where each 0 < wi < 1. Recall that Opt(w) is the minimum number of unit bins that can hold all the weights in w. As output, we define a global integer variable b whose final value will be Opt(w). INIT(n,w) simply initializes a global variable b ← n. The macro CONSUME(per) is given by
CONSUME(per) ≡ b ← min{b,Grd(w)}
2348 where Grd is the greedy algorithm for linear bin packing.
2349 ¶54. How to update the permutation. We now describe the Update macro. It uses 2350 the previous counter level ` to transform the current permutation to the next permutation. 2351 For example, the successive counter values in (53) correspond to the following sequence of 2352 permutations:

To interpret the above, consider a general step of the form

2353 We start with the counter value [c2,c3,c4] and permutation (x1 − x2 − x3 − x4). After calling 2354 Inc, the counter is updated to [], and it returns the level ` of [c2,c3,c4]. If ` = 1,
2358 In (54), we indicate xi by an underscore, “xi”. The choice of which neighbor (xi−1 or xi+1)

2359 depends on whether we are in the “UP” phase or “DOWN” phase of level `. Let UP[1..n] be a 2360 Boolean array where UP[`] is true in the UP phase, and false in the DOWN phase when we are 2361 incrementing a counter at level `. Moreover, the value of UP[`] is changed (flipped) each time 2362 C[`] is reinitialized to 1. For instance, in the first row of (54), UP[4] = false and so the entry 2363 4 is moving down with each swap involving 4. In the next row, UP[4] = true and so the entry 2364 4 is moving up with each swap.
2365 We modify our previous Inc subroutine to include this update:
2366
Increment(C)
Output: Increments C, updates UP, and returns the previous level of C ` ← n.
While (C[`] = `) ∧ (` > 1) / Loop to find the counter level C[`] ← 1;
UP[`] ← ¬UP[`]; / Flips the boolean value UP[`]
`–.
If (` > 1)
C[`]++.
Return(`).
2367
For a given level `, the Update macro need to find the
“position” i where per[i] = ` (i = 1,…,n). We could search for this position in O(n) time, but it is more efficient to maintain this information directly: let pos[`] denote the current position of `. Thus the pos[1..n] is just the inverse of the array per[1..n] in the sense that
per[pos[`]] = ` (` = 1,…,n).
2368 We can now specify the Update macro to update both pos and per:
2369
2370
2371

2376 The Java code for this algorithm is presented in an appendix of this chapter. We conclude 2377 with this theorem about complexity.
2378 Theorem 20 (Complexity of Johnson-Trotter Generator) he time complexity to gener2379 ate each n-permutation is O(n). However, this complexity is O(1) in an amortized sense. 2380
2381 Proof. Inside the main loop, we call two subroutines, Increment(C) and Update. By 2382 Lemma 19, the cost of calling Inc(C) (and similarly for Increment(C)) is O(n) in the worst 2383 case, but O(1) when amortized over the entire algorithm. We also observe that Update is
2384 worst case O(1). Q.E.D.
2385
Remarks:
2395 3. The Johnson-Trotter enumeration of permutations can be extended to the enumeration of all
2396 strings of length n over a finite alphabet Σ. Now, we define two strings to be adjacent if they
2397 differ at only one position. For Σ = {0,1}, the most famous such enumerations is the Gray code
2398 (or reflected binary code): ifG(n) is the Gray code for strings of length n, then G(n + 1) = 0 ·
2399 G(n);1·GR(n) where GR(n) is the reverse (reflected) enumeration. E.g., G(2) = (00,01,11,10) 2400 and G(3) = 0 · (00,01,11,10);1 · (10,11,01,00)(000,001,011,010;110,111,101,100). An appli- 2401 cation is physical implementation of counters. To count to 2n, we want to cycle through all the
2406
2407 Exercises
2408 Exercise
8.1:
2409 (a) Draw
the adjacency bigraph
correspond ing to 4permutatio ns. HINT: first draw 2410 the adjacency graph for 3permutatio ns and view 4permutatio ns as
extension of 3-
2411 permutations.
2412 (b) How many edges are there in the adjacency bigraph of n-permutations?
2413 (c) What is the radius and diameter of the bigraph in part (b)? [See definition of radius 2414 and diameter in Exercise 4.8 (Chapter 4).] ♦
2415 Exercise 8.2: Another way to list all the n-permutations in Sn is lexicographic ordering:
2416 ) if the first index i such that satisfies.
2417 Thus the lexicographic smallest n-permutation is (1 − 2 − ··· − n). Give an algorithm
2418 to generate n-permutations in lexicographic ordering. Compare this algorithm to the
2419 Johnson-Trotter algorithm. ♦
2420 Exercise 8.3: All adjacency orderings of 2- and 3-permutations are cyclic. Is it true of 4-
2421 permutations? ♦
2422 Exercise 8.4: Two n-permutations π,π0 are cyclic equivalent if π = (x1 − x2 − ··· − xn) 2423 and π0 = (xi − xi+1 − ··· − xn − x1 − x2 − ··· − xi−1) for some i = 1,…,n. A cyclic 2424 npermutation is an equivalence class of the cyclic equivalence relation. Note that there 2425 are exactly n permutations in each cyclic n-permutation. Let denote the set of cyclic 2426 npermutations. So1)!. Again, we can define the cyclic permutation graph 2427 whose vertex set is, and edges determined by adjacent pairs of cyclic permutations. 2428 Give an efficient algorithm to generate a Hamiltonian cycle of. ♦
2429 Exercise 8.5: Suppose you are given a set S of n points in the plane. Give an efficient method 2430 to generate all the convex polygons whose vertices are from S. Give the complexity of
2431 your algorithm
as a function of n.
♦
2432 End Exercises
Add

2433 §9 APPENDIX: Java Code for Permutations
2434 /**************************************************** 2435 * Per(mutations) 2436 * This generates the Johnson-Trotter permutation order.
2437 * An n-permutation is a permutation of the symbols {1,2,…,n}. 2438 * 2439 * Usage:
2440 * % javac Per.java 2441 * % java Per [n=3] [m=0]
2442 *
2443 * will print all n-permutations. Default values n=3 and m=0.
2444 * If m=1, output in verbose mode.
2445 * Thus “java Per” will print
2446 * (1,2,3), (1,3,2), (3,1,2), (3,2,1), (2,3,1), (2,1,3).
2448 *

2449 ***************************************************/ 2450
2451 public class Per { 2452 2453 // Global variables
2454 //////////////////////////////////////////////////// 2455 static int n; // npermutations are being considered 2456 // Quirk: Following arrays are indexed from 1 to n 2457 static int[] per; // represents the current n-permutationAdd
2458 static int[] pos; // inverse of per: per[pos[i]]=i (for i=1..n) 2459 static int[] C; // Counter array: 1 <= C[i] <= i (for i=1..n) 2460 static boolean[] UP; // UP[i]=true iff pos[i] is increasing 2461 // (going up) in the current phase 2462
2463 // Display permutation or position arrays 2464 //////////////////////////////////////////////////// 2465 static void showArray(int[] myArray, String message){ 2466 System.out.print(message); 2467
System.out.print(“(” + myArray[1]); 2468 for (int i=2; i<=n; i++) 2469 System.out.print(“,” + myArray[i]); 2470 System.out.println(“)”);
2471 }
2472
2473 // Print counter 2474 //////////////////////////////////////////////////// 2475 static void showC(String m){ 2476 System.out.print(m); 2477 System.out.print(“(” + C[2]); 2478 for (int i=3; i<=n; i++) 2479 System.out.print(“,” + C[i]); 2480 System.out.println(“)”);
2481 } 2482
2483 // Increment counter 2484
//////////////////////////////////////////////////// 2485 static int inc(){
2486 int ell=n; 2487 while ((C[ell]==ell) && (ell>1)){ 2488 UP[ell] = !(UP[ell]); // flip Boolean flag 2489 C[ell–]=1;
2490 }
2491 if (ell>1) 2492 C[ell]++; 2493 return ell; // level of previous counter value 2494 } 2495
2496 // Update per and pos arrays 2497
//////////////////////////////////////////////////// 2498 static void update(int ell){ 2499 int tmpSymbol; // this is not necessary, but for clarity 2500 if (UP[ell]) { 2501 tmpSymbol = per[pos[ell]+1]; // Assert: pos[ell]+1 makes sense!
2502 per[pos[ell]] = tmpSymbol; 2503 per[pos[ell]+1] = ell; 2504 pos[ell]++; 2505 pos[tmpSymbol]–; 2506 } else { 2507 tmpSymbol = per[pos[ell]-1]; // Assert:
pos[ell]-1 makes sense!
2508 per[pos[ell]]= tmpSymbol; 2509 per[pos[ell]-1] = ell; 2510 pos[ell]–; 2511 pos[tmpSymbol]++;
2512 }
2513 }
2514
2515 // Main program 2516 ////////////////////////////////////////////////////
2517 public static void main (String[] args)Add 2518 throws java.io.IOException
2519 {
2520 //Command line Processing 2521 n = (args.length>0) ? Integer.valueOf(args[0]) : 3; 2522 int val = (args.length>1) ? Integer.valueOf(args[1]) : 0; 2523 boolean verbose = (val>0)? true : false;
2524
2525 //Initialize 2526 per = new int[n+1]; 2527 pos = new int[n+1]; 2528 C = new int[n+1];
2529 UP = new boolean[n+1]; 2530 for (int i=0; i<=n; i++) { 2531 per[i]=i; 2532 pos[i]=i; 2533 C[i]=1; 2534 UP[i]=false;
2535 }
2536
2537 //Setup For Loop 2538 int count=0; // only used in verbose mode 2539 int ell=1; 2540 System.out.println(“Johnson-Trotter ordering of ” 2541 + n + “-permutations”);
2542 if (verbose) 2543 showArray(per, count + “, level=”+ ell + ” : ” ); 2544 else
2545 showArray(per, “”); 2546
2547 //Main Loop
2548 do {
2549 ell = inc(); 2550 update(ell); 2551 if (verbose) 2552 count++; 2553
showArray(per, count + “, level=”+ ell + ” : ” );
2554 else
2555 showArray(per, “”); 2556
} while (ell>1);
2557
2558 }//main 2559 }//class Per
2560 References
2561 [1] J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. K. Wei. A locally adaptive data 2562 compression scheme.Comm. of the ACM, 29(4):320–330, 1986.
2563 [2] X. Cai and Y. Zheng. Canonical coin systems for change-making problems. 2564 arXiv:0809.0400v1 [cs.DS], 2009. 14 pages.
2565 [3] S. K. Chang and A. Gill. Algorithmic solution of the change-making problem. J. ACM, 2566 17(1):113–122, 1970.
2567 [4] G. D´osa and J. Sgall. First Fit bin packing: A tight analysis. In Proc. 30th STACS, volume
2571 [6] D. Kozen and S.Zaks. Optimal bounds for the change-making problem. Theor. Computer 2572 Science, 123(2):377–388, 1994.
2575 [8] T. W. Parsons. Letter: A forgotten generation of permutations, 1977.
2576 [9] R. Sedgewick. Permutation generation methods. Computing Surveys, 9(2):137–164, 1977. 2577 [10] R. E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA, 1974.
2578 [11] J. S. Vitter. The design and analysis of dynamic huffman codes. J. ACM, 34(4):825–845,
2579 1987.