Sample solutions for hw3

• [9.3-5] The basic idea is change the algorithm on page 187, calling the black-box algorithm before calling the partition function. When calling the partition function, use the median value found with the black-box algorithm as the pivot.

  select(A, p, r, i)  
  {
    if (p = r) then return A[p];
    mid = median(A, p, r);
    q = partition(A, p, r, mid);
    k = q - p + 1;
    if (i <= q) return select(A, p, q, i);
    else return select(A, q+1, r, i-k);
  }
            

• [10.3-9] Assume the x-coordinate is from West to East and y-coordinate is from South to North, and that the positions of the n wells are represented as (x1, y1), ..., (xn,yn), also assume that the pipeline has a y-coordinate of Y, then the problem reduces to calculating a certain Y that makes the following expression have the smallest value: |Y-y1| + |Y-y2| + ... + |Y-yn| We can prove that this Y is the median of y1,...,yn, for instance, by induction on n. The intuitiven meaning of the solution is that in order to minimize the total length of the spurs, there should be an equal number of wells to the North and to the South of the pipeline. When n is odd, the pipeline should pass through the median of abscissae of these wells; if n is even, the pipeline can be set to pass throgh any point between the two medians of these. Clearly, given the coordinates of the wells, we can determine the optimal location in linear time.

• [10-1]
  • a. Theta(n log n + i)
  • b. Theta(i log n + n)
  • c. Theta(n + i log i)

• [last problem]
  • a. A simple traversal of the dummy nodes reachable from the root of the min-heap solves this problem.

    In the following function head(h) returns the head (think it as a pointer) of h, left(h) and right(h) return the left and right subtrees of h respectively. @ is concatenation operator on lists.

    function list (h)
      return if h == nil then []
             else if h <> nil and head(h) is not marked 'deleted' then [h]
                  else if h <> nil and head(h) is marked 'deleted'
                       then list(left(h))@list(right(h))
    

  • b. Clearly the complexity of the list function is O(k) because we only visit k nodes of the heap.

  • c. Purging lazily deleted (dummy) nodes requires time O(k), while merging the heaps on the list obtained from the list function requires O(k max {1, log(n/(k+1))}), so the complexity of FIND-MIN that includes purging lazily deleted nodes is O(k max {1, log(n/(k+1))})