Analysis of Algorithms, part 2
CS 288
May 6, 2005

  1. a) Trace the Floyd-Warshall algorithm on the graph whose adjacency matrix is given at left below 
       0  6  ∞  ∞                                  0  1  0  0
   2  0  3  ∞                                  1  0  0  0
  10  ∞  0  7                                  1  0  0  1
   ∞  5  ∞  0                                  0  1  0  0
    b) What is the time complexity of this algorithm?

    c) Recall that there is a version of the Floyd-Warshall algorithm that finds the transitive closure of a directed graph. Trace this version of the algorithm on the graph whose adjacency matrix is given at right above.

    d) What is the time complexity of this version of the algorithm?

  2. Recall that there is an activity selection problem for which an instance is a set S of n activities, where activity i has a starting time si and a finish time fi. Recall further that in this problem we are to find a subset A of S which is maximal subject to the constraint that any two tasks in the subset are compatible -- that is, for no i and j can the intervals [si, fi) and [sj, fj) overlap, if activities i and j are both in A.

    Consider the greedy algorithm that considers activities from earliest finish time to latest, and includes an activity in the output set A if and only if its starting time is no earlier than the latest finish time of any task that has already been included in A.

    a) What set A would this algorithm return if S = {x1, x2, ... , x7}, and si = i-1 and fi = i2 for each xi in S?

    b) What is the time complexity of this algorithm, assuming that the items are already sorted by their finish time?

    c) Show that an activity is included by the algorithm if and only if it is compatible with all activities that were included earlier.

    CLAIM: Let A be the solution returned by the greedy algorithm, and let O be any optimal solution different from A. Let k be the integer such that O contains the first k-1 activities selected by the greedy algorithm but not the kth item. Then there is another optimal solution that contains the first k activities selected by the greedy algorithm.

    d) Assuming (c) and (d), show that the greedy algorithm always returns an optimal solution.

    EXTRA CREDIT (applicable to Question 2 only, to a maximum of 20 points): Assuming (c), prove the claim. (Hint: show that O contains at most one activity that is incompatible with the kth item selected by the greedy algorithm).

  3. Consider the data structure that represents a collection of size n by a sequence of up to k sorted arrays, where the ith array A[i] is either empty or has size 2i, and 2k-1 <= n < 2k. The distribution of the elements of the sequence among the elements of the arrays may be arbitrary. So for example, the collection (3 13 19 22 23 33 43 44 53 63 73) of size 11 could be represented by having A[0] = (22), A[1] = (19 44), A[2] be empty, and A[3] = (3 13 23 33 43 53 63 73).

    a) What is the worst-case time complexity of searching this data structure for a given element?

    b) Consider the following insertion algorithm, which mimics the operation of adding 1 to a binary integer: 

          Insert(x):
         let C be an array of size 1 that contains only x 
         let i=0
         while A[i] is not empty
           let C = the result of merging C with A[i]
           let A[i] be empty
           let i = i+1
         let A[i] be C
    Show the result of inserting the integer 35 into the structure of size 11, where A[0] = (22), A[1] = (19 44), A[2] is empty, and A[3] = (3 13 23 33 43 53 63 73).

    c) What is the worst-case time complexity of the algorithm of (b)?

    d) What is the total time required to insert n = 2k items, using the algorithm of (b), into an initially empty data structure? (Hint: consider the probability that two arrays of size 2i will need to be merged).

    e) What is the amortized time complexity of the insertion algorithm of (b)?