HW 5

For all divide-and-conquer algorithms follow these steps:

        1. Describe the steps of your algorithm in plain English.
        2. Write a recurrence equation for the runtime complexity.
        3. Solve the equation by the master theorem

    1. Solve the following recurrences by giving tight Θ-notation bounds in terms of n for sufficiently large n. Assume that T(·) represents the running time of an algorithm, i.e. T(n) is positive and non-decreasing function of n and for small constants c independent of n, T(c) is also a constant independent of n. Note that some of these recurrences might be a little challenging to think about at first.

            a) T(n) = 4T(n/2) +  !logn

            b) T(n) = 8T(n/6) + nlogn

            c) T(n) = √6000 T(n/2) +  √#$$$
            d) T(n) = 10T(n/2) + 2
            e) T(n) = 2T(√ ) + log!

    2. Consider an array A of n numbers with the assurance that n > 2, A[1] ≥ A[2] and A[n] ≥ A[n−1]. An index i is said to be a local minimum of the array A if it satisfies 1<i<n, A[i − 1] ≥ A[i] and A[i + 1] ≥ A[i].

                (a) Prove that there always exists a local minimum for A.

                (b) Design an algorithm to compute a local minimum of A.


Your algorithm is allowed to make at most O(log n) pairwise comparisons between elements of A.

    3. The recurrence T(n) = 7T (n/2) + ! describes the running time of an algorithm ALG. A competing algorithm ALG% has a running time of %( ) = a %(  /4) + ! log . What is the largest value of a such that ALG% is asymptotically faster than ALG?


    4. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.




    5. Given a binary search tree T, its root node r, and two random nodes x and y in the tree. Find the lowest common ancestry of the two nodes x and y. Note that a parent node p has pointers to its children p.leftChild() and p.rightChild(), a child node does not have a pointer to its parent node. The complexity must be O(log n) or better, where n is the number of nodes in the tree.

Recall that in a binary search tree, for a given node p, its right child r, and its left child l, r.value() ≥ p.value() ≥ l.value(). Hint: use divide and conquer


    6. Suppose that you are given the exact locations and shapes of several rectangular buildings in a city, and you wish to draw the skyline (in two dimensions) of these buildings, eliminating hidden lines. Assume that the bottoms of all the buildings lie on the x-axis. Building Bi is represented by a triple (Li, Hi, Ri), where Li and Ri denote the left and right x coordinates of the building, respectively, and Hi denotes the building’s height. A skyline is a list of x coordinates and the heights connecting them arranged in order from left to right.

For example, the buildings in the figure below correspond to the following input

(1, 5, 5), (4, 3, 7), (3, 8, 5), (6, 6, 8).

The skyline is represented as follows: (1, 5, 3, 8, 5, 3, 6, 6, 8). Notice that the x-coordinates in the skyline are in sorted order.

    a) Given a skyline of n buildings and another skyline of m buildings in the form (x1, h1, x2, h2, ….xn) and (x’1, h’1, x’2, h’2, ….x’m) , show how to compute the combined skyline for the m + n buildings in O(m + n) steps.

    b) Assuming that we have correctly built a solution to part a, give a divide and conquer algorithm to compute the skyline of a given set of n buildings. Your algorithm should run in O(n log n) steps.