CS502 Final Term Highlighted Handouts by Masters

cents (called a “nickle”), ten cents (called a “dime”) and twenty five cents (a “quarter”). The notes are also called “bills”. The coins are one cent, five

Chapter 7

Greedy Algorithms

An optimization problem is one in which you want to find, not just a solution, but the best solution. Search techniques look at many possible solutions. E.g. dynamic programming or backtrack search. A “ greedy algorithm” sometimes works well for optimization problems A greedy algorithm works in phases. At each phase:

For some problems, greedy approach always gets optimum. is called a greedy heuristic, or approximation. For still others, greedy approach can do very poorly.

7.1 Example: Counting Money

Suppose you want to count out a certain amount of money, using the fewest possible bills (notes) and coins. A greedy algorithm to do this would be: at each step, take the largest possible note or coin that does not overshoot.

while (N > 0){ give largest denomination coin ≤ N reduce N by value of that coin

Consider the currency in U.S.A. There are paper notes for one dollar, five dollars, ten dollars, twenty dollars, fifty dollars and hundred dollars. In Pakistan, the currency notes are five rupees, ten rupees, fifty rupees, hundred rupees, five hundred rupees and thousand best. If so, it For others, greedy finds good, but not always

• You take the best you can get right now, without regard for future consequences.
• You hope that by choosing a local optimum at each step, you will end up at a global optimum. krons” come in 1 kron, 7 kron, and 10 kron coins Using

rupees. The coins are one rupee and two rupees. Suppose you are asked to give change of $6.39 (six dollars and thirty nine cents), you can choose:

• a $5 note
• a $1 note to make $6
• a 25 cents coin (quarter), to make $6.25
• a 10 cents coin (dime), to make $6.35
• four 1 cents coins, to make $6.39

Notice how we started with the highest note, $5, before moving to the next lower denomination. Formally, the Coin Change problem is: Given k denominations d1, d2, . . . , dk and given N, find a way of writing

such that N = i1d1 + i2d2 + · · · + ikdk

The “size” of problem is k. The greedy strategy works for the coin change problem but not always. Here is an example where it fails. Suppose, in some (fictional) monetary system, “

15 krons This r kron pieces, for a total of . A better solution, however, would be to use two 7 kron pieces and one 1 kron piece This only requires three coins The greedy algorithm results in a solution, but not in an optimal solution The greedy approach gives us an optimal solution when the coins are all powers of a fixed denomination.

N = i0D0 + i1D1 + i2D2 + · · · + ikDk

Note that this is N represented in based D. U.S.A coins are multiples of 5: 5 cents, 10 cents and 25 cents.

7.1.1 Making Change: Dynamic Programming Solution

The general coin change problem can be solved using Dynamic Programming. Set up a Table, C[1..k, 0..N] in which the rows denote available denominations, di; (1 i k) and columns denote the amount from 0 . . . N units, (0 j N). C[i, j] denotes the minimum number of coins, required to pay an amount j using only coins of denominations 1 to i. C[k, N] is the solution required. To pay an amount j units, using coins of denominations 1 to i, we have two choices:

1.

2. or chose at least one coin of denomination i, and also pay the amount (j − di). i1 + i2 + · · · + ik is minimized.

equires six coins a greedy algorithm to count out 15 krons, you would get A 10 kron piece Five 1

either chose NOT to use any coins of denomination i,

7. 2. GREEDY ALGORITHM: HUFFMAN ENCODING

COINS(N) 1 d[1..n] = {1, 4, 6} // (coinage, for example) 2 for i = 1 to k 3 do c[i, 0] ← 0 4 for i = 1 to k 5 do for j = 1 to N do if (i = 1 & j < d[i]) then c[i, j] ← ∞ else if (i = 1) then c[i, j] ← 1 + c[1, j − d[1]]

2k so To pay (j − di) units it takes C[i, j − di] coins. Thus,

C[i, j] = 1 + C[i, j − di]

Since we want to minimize the number of coins used,

C[i, j] = min(C[i − 1, j], 1 + C[i, j − di])

Here is the dynamic programming based algorithm for the coin change problem.

else if (j < d[i]) then c[i, j] ← c[i − 1, j] else c[i, j] ← min (c[i − 1, j], 1 + c[i, j − d[i]]) 13 return c[k, N]

7.1.2 Complexity of Coin Change Algorithm

Greedy algorithm (non-optimal) takes O(k) time. Dynamic Programming takes O(kN) time. Note that N can be as large as the dynamic programming algorithm is really exponential in k.

7.2 Greedy Algorithm: Huffman Encoding

The Huffman codes provide a method of encoding data efficiently. Normally, when characters are coded using standard codes like ASCII. Each character is represented by a fixed-length codeword of bits, e.g., 8 bits per character. Fixed-length codes are popular because it is very easy to break up a string into its individual characters, and to access individual characters and substrings by direct indexing. However, fixed-length codes may not be he most efficient from the perspective of minimizing the total quantity of data. Consider the string “ abacdaacac”. if the string is coded with ASCII codes, the message length would be 8 = 80 bits. We will see shortly that the same string encoded with a variable length Huffman encoding scheme will produce a shorter message.