- Give a careful proof that ∑
^{n}_{i=1}i log(i) = Θ(n^{2}log n). - (a) Give an example input where it is possible to make correct change but the greedy algorithm fails to do so (the algorithm gives back insufficient change).
ANSWER: Take denominations 4 and 5 and desired total 8.

(b) Suppose the denominations are American coins: c[1] = 1, c[2] = 5, c[3] = 10, c[4] = 25. Is it the case that, for

*these*denominations, for any positive integer T, the greedy algorithm makes change totaling T using the minimum possible number of coins?ANSWER: Yes, it is the case.

In this case we think of the greedy algorithm as the following recursive procedure:

greedy(T)

1. If T == 0, return: {} (the empty set of coins)

2. If T > 25, return: {quarter} ∪ greedy(T-25)

3. If T > 10, return: {dime} ∪ greedy(T-10)

4. If T > 5, return: {nickel} ∪ greedy(T-5)

5. return: {penny} ∪ greedy(T-1)We will prove by induction on T that the greedy algorithm returns the unique minimum-size set of coins totalling T.

The base case is T=0. In this case, the claim is clearly true.

Next consider any T>0. We will show that the claim is true, assuming by induction that the claim is true for any T' < T.

Let S be a minimum-size set of coins totalling T. We wil show by induction that greedy(T) = S.

Suppose the coin that greedy adds before recursing is a quarter. Suppose S also has a quarter in it. Let S' be the set S, minus the quarter. S' must be a best-possible way of making change T-25 (otherwise S would not be a best-possible way of making change T, because S' could be replaced in S by a smaller set with the same total). So, by induction, we can assume greedy(T-25) = S'. But then greedy(T) = S, because

- greedy(T) = {quarter} ∪ greedy(T-25) = {quarter} ∪ S' = {quarter} ∪ (S-{quarter}) = S.

By the same reasoning, if greedy is adding a dime, nickel, or penny before recursing, and S also has that same coin in it, we can show using induction as above that greedy(T) = S.

Otherwise, S does not have the same coin, that greedy is adding. We consider the possible cases and show that none of them can happen.

**CASE 1:**T=1,2,3,4 (so greedy is adding a penny, and S has no penny in it).This cannot happen, since S cannot make change for T < 5 without pennies.

**CASE 2:**T=5,6,7,8,9, so greedy is adding a nickel, and S has no nickel in it.In this case S must be making change worth 5,6,7,8, or 9 with only pennies. (S clearly cannot use coins of value more than T, so dimes and quarters are out). So in this case, S would have to have at least 5 pennies. But S is a minimum-size set totalling T, so it cannot have 5 pennies (because they could be replaced by a nickel to get a smaller set). So this case cannot happen.

**CASE 3:**T is at least 10 and at most 24, so greedy is adding a dime, and S has no dime in it.In this case, S must be making change worth at least 10 with only nickels and pennies. In any way of doing so, S would have to have two or more coins of total worth 10. (Check this.) Replacing these coins by a dime would yield a set smaller than S but with the same total. This would contradict our assumption that S is optimal. So this case cannot happen.

**CASE 4:**T is at least 25, so greedy is adding a quarter, but S has no quarter in it.In this case, S would have to make change worth at least 25 with only dimes, nickels, and pennies.

S cannot have three or more dimes --- they could be replaced by a quarter and a nickel.

So S has at most 20 cents worth of dimes, and the rest in pennies and nickels, totalling 25 or more. But then the dimes, together with some of the nickels and/or pennies, must total 25. But these coins could be replaced by a quarter to give a smaller set. So this cannot happen either.

**summary**: We've shown that whatever coin that greedy adds, the optimal set S must also have the same coin. We conclude by induction that the greedy set returns the same set as S. - ... L(n) satisfies the recurrence relation L(n) = L(n/4)+L(n/4) + 2, L(1) = 1.
Describe the recurrence tree for L(n).
How many levels does it have?
What is the depth?
How many children does each node have?
ANSWER: it has #levels = depth = log

_{4}n, because at each level, n decreases by a factor of 4. Each node has two children.What is the value of L(n)? (Give a careful proof.)

ANSWER: Using the method from class, the value of L(n) is the number of nodes in the recursion tree, times 2. The recursion tree is a complete binary tree of depth d = log

_{4}n, so it has 2^{d}-1 = Θ(2^{log4 n}) = Θ(n^{log4 2}) = Θ(n^{1/2}) nodes. So L(n) = Θ(n^{1/2}).What is the area used by a drawing of this kind? Explain your reasoning.

ANSWER: the area is the width times the height, each of which is L(n) = Θ(n

^{1/2}). So the area is Θ(n). You can see this directly from the diagram, since for each of the n leaves there is a 2x2 box in the grid for that leaf.

ANSWER: Each term in the sum is at most n log n and there are n terms,
so the sum is at most n^{2} log n. Applying the definition of big-O
with c = 1 and n_{0} = 1, we see easily that this is O(n^{2}log n).

The largest n/2 terms in the sum are at least (n/2) log (n/2),
so the sum is at least (n/2)^{2} log(n/2) = (n^{2}/4)( log(n) - log(2)).

Since log(2) ≤ log(n)/2 for n larger than some n_{0} (how large depends on the base of the logarithm),
the sum is at least
(n^{2}/4) log(n)/2 = n^{2}/8 log(n) for n ≥ n_{0}.
Thus, taking c=(1/8) and applying the definition of Ω,
the sum is Ω(n^{2} / log n).