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

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

The respective arrays m and s are given below:
```
               2500                                  3
           2000    2000                            3   3
       1000    1500    1500                      1   3   3
   1000     500    1000    1000                1   2   3   4 
 0       0       0       0       0 
```
The entry 3 in position (1,5) at the top of the s array means that the matrix chain is parenthesized at the top level as (A₁A₂A₃)(A₄A₅) The entry 1 in position (1,3) of the s array shows how the first factor above is parenthesized. No further parenthesization is needed to disambiguate; the final expression may be written as (A₁(A₂A₃))(A₄A₅), which does have cost 2500.
1. INSERT and EXTRACT-MIN are invoked Θ(n) times. DECREASE-KEY is invoked Θ(e) times.
2. All three operations of the previous part have time complexity Θ(log n), so if INSERT is used to build the priority queue, the overall time complexity is Θ((n + e) log n). By the reachability assumption, this is just Θ(e log n). Since the cost of the calls to DECREASE-KEY is the dominant cost, it doesn't matter whether the Θ(n) cost of the BUILD-MIN-HEAP algorithm replaces Θ(n log n) cost of n invocations of INSERT.
3. Now the (amortized) cost of EXTRACT-MIN is Θ(log n) and the (amortized) cost of DECREASE-KEY is O(1). So these two routines contribute a cost of Θ(e + n log n). Once again, this cost exceeds both the cost of n insertions and the cost of BUILD-MIN-HEAP, so it represents the entire asymptotic cost of Dijkstra's algorithm.
4. Now the equivalents of INSERT and DECREASE-KEY take O(1) time, and EXTRACT-MIN takes Θ(n) time in the worst case. So the worst-case time complexity is Θ(n + e + n²), or Θ(n²). The BUILD-MIN-HEAP operation is not relevant.
5. The Floyd-Warshall algorithm has time complexity Θ(n³). So for part 2, we would need e to be O(n² / log n) but not Θ(n² / log n), which is possible. For part 3, we would just need e to be O(n²) but not Θ(n²), which is also possible. For part 4, n calls to Dijkstra's algorithm will always take time O(n³), so under no conditions would there be an asymptotic improvement.
1. If two n x n matrices are each split into four n/2 x n/2 submatrices, then it is possible to compute the product of the two original matrices by computing 7 products of these submatrices, and doing some matrix addition. Each addition has time complexity Θ(n²).
2. Θ(n^{lg 7}).
3. There are more efficient algorithms for dealing with the fairly common case of sparse arrays. Also, the constant factor hidden in the O-notation is large enough that the naive matrix multiplication algorithm is superior to Strassen for fairly large arrays.
4. To avoid division by 0, or more generally to avoid the instability that can result from division by small numbers.