Analysis of Algorithms, part 2, CS 288,
May 10, 2006

 

  1. Trace the behavior of the dynamic programming algorithm for matrix-chain multiplication on the instance A1A2A3A4A5, where Show the contents of the array m that gives the optimal cost information for subproblems, and the array s that tells how each entry of m was chosen. Also trace how the array s is used to find the parenthesization for the matrix chain that gives the minimal cost. Don't forget to say what this minimal cost is.

     

  2. This question deals with the analysis of Dijkstra's algorithm for the single-source shortest-paths problem, for a graph with n = |V| vertices and e = |E| edges, under the assumption that an adjacency list is used to represent the graph. Express your answers using O-notation (Θ-notation where appropriate).

     

    1. If a priority queue is used to find minima, how many invocations of each of INSERT, EXTRACT-MIN, and DECREASE-KEY are required in the worst case? Assume that the priority queue is built with n invocations of INSERT.

    2. Using your answer to the previous part, what is the worst-case time required for Dijkstra's algorithm if the priority queue is implemented as a binary min-heap? Assume that all vertices of the graph are reachable from the source vertex. Also assume that handles are maintained so that DECREASE-KEY may be applied to arbitary nodes in the priority queue. Does it matter whether BUILD-MIN-HEAP, rather than successive insertion, is used to build the priority queue?

    3. Redo the previous part under the assumption that the priority queue is instead implemented as a Fibonacci heap.

    4. Redo the previous part under the assumption that no priority queue is used, and that the cost function d is simply stored in an array indexed from 1 to n. Assume that EXTRACT-MIN requires a sequential search through this array.

    5. For each of the three previous parts, determine whether there are conditions on e such that n calls to Dijkstra's algorithm are asymptotically faster in the worst case than the use of the Floyd-Warshall algorithm for the all-pairs shortest-paths algorithm.

     

  3. This question deals with matrix operations, and in particular with Strassen's algorithm for efficient matrix multiplication.

    1. Justify the claim that the time complexity T(n) of Strassen's algorithm is given by the formula
      T(n) = 7T(n/2) + Θ(n2)
      You needn't get into great algebraic detail.

    2. What is the asymptotic solution to this recurrence?

    3. Give a reason why someone might use an algorithm other than Strassen's for multiplying large matrices.

    4. There are at least two ways of solving systems of linear equations -- using an LU decomposition and using an LUP decomposition. Why might someone use the more complicated LUP decomposition instead of the simpler LU decomposition?