Solutions to Problem Set #1, CS 255, February 20, 2006

The analogous proof fails. Using the constant 3, the number of elements that can be guaranteed to be eliminated is at least 2[(n/3)(1/2) - 2] = n/3 - 4. So the analogous recurrence becomes T(n) <= an + c(1 + n/3) + c(2n/3 + 4) For this to be bounded above by cn, we need
```
  an + c(1 + n/3) + c(2n/3 + 4) <= cn, or
  an + c + cn/3 + 2cn/3 + 4c <= cn, or
  an + c + 4c <= 0.
```
Since all of the terms on the left-hand side of the inequality are positive, there is no value of c that will make the inequality true.
Note that showing that the recurrence does not have a linear solution isn't quite the same thing as showing that the algorithm doesn't have linear time complexity. For one thing, the recurrence is an overestimate, or pessimistic estimate, of the time required by the algorithm.
The time required for the last two steps of the algorithm is Θ(2^k + kn), which is Θ(n) assuming that k is independent of n. This is true since setting up the original tournament takes time Θ(2^k), and it has to be replayed Θ(n) times doing k comparisons at each replay.
By analogy with mergesort, the recursion tree method of Section 4.2 of the text can be used to observe there are logarithmically many levels of the recursion tree, each with linear cost. This gives an overall worst-case time complexity of Θ(n log n).
More formally, the relevant recurrence is
T(n) <= an + 2^kT(n/2^k) In the master theorem, a = b, so case 2 applies to give that T(n) is Θ(n log n). This asymptotic result could also be obtained by the substitution method. Θ(n log n) is a reasonable guess for the asymptotic result, since it's the best-possible worst-case time complexity for comparison-based sorting, as described in Section 8.1.
Although the algorithm of this exercise may not have any obvious advantages over the other
Θ(n log n) sorting algorithms, it does exhibit very good locality of reference. That is, data that is needed at any point of the algorithm is likely to be stored very close to data that has been recently used. This makes the algorithm a useful one for sorting sequences that are too large to fit into main memory.

The matrices corresponding to the arrays m and s of the text are given below.

      0 3000 1750 4750 4500                -  1  1  3  3
           0 1000 3000 3500                   -  2  3  3
                0 4000 3000                      -  3  3
                     0 2000                         -  4
                          0                            -

If the original matrices are called A₁ through A₅, then the optimal order of the computation is given by ((A₁ x (A₂ x A₃)) x (A₄ x A₅)) and requires 4500 element multiplications.

- No node in a Huffman tree may have just one child, since replacing the node by the child would give a lower-cost tree. So if L is a node on the lowest level, L must be a leaf, it must have a parent, and by the above, this parent must have another child. This child is a sibling of L, and it's also on the lowest level.
- Let C and D be the costs of the least profitable leaves, and assume they are at levels d_C and d_D in O. Let h be the lowest level, and let E and F be two siblings on that level. Swapping C with E and D with F changes the cost by
```
   E(dC-h) + F(d_D-h) - C(h-d_C) - D(h-d_D)
 = (E-C)(d_C-h) + (F-D)(d_D-h)
```
  Since C and D are the lowest costs, the factors (E-C) and (F-D) are nonnegative. And since h is the lowest (i.e., the highest numbered) level, the factors d_C-h and d_D-h are nonpositive. So the overall change is nonpositive, and the resulting tree O' has cost at least as low as O.
  And since O is optimal, O' has cost at least as high as O's cost. So O' is an optimal solution.
- In the argument above, we may assume that C and D are the costs of the two leaves that the greedy algorithm would first combine. So replacing the leaves with these costs by a new node with cost C+D would give an instance of size n-1. By the way the greedy algorithm works, the greedy solution to this new instance is the tree obtained by replacing C and D and their parent by a leaf of cost C+D. If C and D are at level d in the original greedy solution G, then the cost of this tree differs from the cost of G's tree by (C+D)(d-1) - Cd - Dd, or -C-D. The same argument shows that applying the same transformation to O' to get a new tree O'' will also change the cost by -C-D.
  It's not hard to see that O'' is an optimal solution to the new instance of size n-1. If there were a better solution B, we could replace its leaf with cost C+D by a nonleaf with two children of costs C and D to get a solution to the original instance of size n. The arguments of the previous paragraph show that the resulting tree would have a cost that exceeds B's cost by exactly C+D. But this cost would be cheaper than O's cost, which exceeds the cost of O'' by exactly C+D. Since O is optimal, we get a contradiction, and so we may conclude that no such B can exist.
  Now by the choice of n, the greedy solution to the instance of size n-1 is optimal, and thus has a cost equal to that of O''. Adding C+D to both sides of this equation gives that the cost of G is equal to the cost of O', which is optimal for the instance of size n. But we assumed that G wasn't optimal for this instance. This contradiction shows that there is no smallest value of n for which there exists a nonoptimal greedy solution, and thus that the greedy algorithm always gives the optimal solution.