Problem Set #1, CS 255, due February 19, 2007

FINAL VERSION

Problems are worth 20 points unless otherwise specified; there are 90 points in all.

Please look at the handout regarding assigments on the class web site before submitting your solutions.

 

  1. (30 points) In the simultaneous max & min problem, suppose that n is a power of 2 and a divide-and-conquer strategy is used in which the elements are divided into n/2 groups of size 2.
    1. How many element comparisons are needed to find the max and min of each group?
    2. After the max and min elements are found for each group, how many additional comparisons are needed to find the max and min of the original input set?
    3. Are your answers to #1 and #2 consistent with the theoretical lower bound that we obtained for the simultaneous max and min problem? Does the algorithm achieve this theoretical lower bound?
    4. How would you modify your algorithm if n was not a power of 2?
    5. How many element comparisons are required by the modified algorithm?
    6. Are your answers to #4 and #5 consistent with the theoretical lower bound that we obtained for the simultaneous max and min problem? Does your algorithm achieve this theoretical lower bound?

  2. In the Optimal Binary Search Tree problem of Section 15.5 of the text, suppose that n = 4, (pi) = (0.20, 0.15, 0.15, 0.15), and (qi) = (0.05, 0.10, 0.05, 0.05, 0.10).
    1. (15 points) Use the recursion (15.19) of the text and dynamic programming to find the optimal cost e[1,4] of a binary search tree using the given probabilities.
    2. (5 points) Find an binary search tree with 4 internal nodes that has the cost that you found to be optimal for the given probabilities. The cost of a tree is given by equation (15.16).
    For this problem, you may (but needn't) code and run the algorithm given in Section 15.5. If you do so, it's safest to turn in the code, just in case your final answer is wrong. It's a good idea to look at the handout regarding documentation on the class web site before turning in code.

  3. Suppose that the cost measure used in the Optimal Binary Search Tree problem is the expected number of element comparisons, rather than the expected number of nodes inspected.
    1. Redo part 1 of Problem 2, with this new cost measure. Note that the only difference in the appropriate recurrences is that in the recurrence (15.19), trees with only an external node have cost 0.
    2. Show that the tree you found in part 2 of Problem 2 remains optimal under this new cost measure.
    3. Prove that for any subtree of a binary search tree (external nodes included), the difference between the cost of the subtree under the old measure and the cost under the new measure is equal to the sum of the weights of the external nodes of the subtree.
    4. Verify that the claim of part 3 holds for the optimal tree of Problem 2.
    5. Using part 3, show that a search tree is optimal under the old cost measure iff it is optimal under the new cost measure.

    1. Consider the natural greedy algorithm for the assembly-line scheduling problem of Section 15.1 of the text that constructs a path as follows: 
        Let l1 = 1 if e1 + a1,1 < e2 + a2,1
                      2 otherwise
  Let lj = 1 if lj-1 = 1 and a1,j < t1,j-1 + a2,j 
                      2 if lj-1 = 1 and a1,j >= t1,j-1 + a2,j 
                      2 if lj-1 = 2 and a2,j < t2,j-1 + a1,j 
                      1 if lj-1 = 2 and a2,j >= t2,j-1 + a1,j
      Give an instance of this problem where x1 = x2=0, but this greedy algorithm will give an incorrect solution.

    2. Recall that to use the correctness proof technique considered in class, we need to define a notion of "closer to" that allows us to get from an arbitrary optimal solution to a greedy solution in a bounded number of steps. For the fractional knapsack problem, it's enough to find an integer-valued "distance" function d for optimal solutions of the problem, such that
      1. the value of d is never negative, and never greater than n
      2. the value of d on the greedy solution G is 0, and
      3. for any nongreedy optimal solution, there is another optimal solution with a smaller d value.
      Hint: consider how one could transfer weights among items to an arbitrary nongreedy optimal solution to make it look more like the greedy solution, without decreasing the profit.