Question

When using its associated dynamic-programming recurrence to compute the entries of wac(i, j), how many times is entry wac(25, 32) used in order to compute other entries of wac that represent larger subproblems, assuming n = 76 keys? Explain and show work.

5b. The general form of a divide-and-conquer recurrence may be expressed as

T(n) = Xr i=1 T(n/bi) + f(n),

for some integer r ≥ 1 and real constants bi > 1, i = 1, . . . , r. Assuming T(n) is an increasing function of n, and f(n) = n α for some α > 0, prove that T(n) has growth that is O(n k ) for some integer k ≥ 1. Hint: Show that T(n) ≤ T 0 (n), for some T 0 (n) that satisfies a uniform recurrence

T 0 (n) = aT0 (n/b) + n α .

Obtain T 0 by using the fact that, since T(n) is increasing, T(n/b1) < T(n/b2) when b1 > b2. (20 points)

Answer 1

A

1. The first step in solving an optimization problem by dynamic programming is to characterize the structure of an optimal solution.
2. problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
3. Whenever a problem exhibits optimal substructure, it is a good clue that dynamic programming might apply.
4. problem of matrix-chain multiplication exhibits optimal substructure.
5. observed that an optimal parenthesization of A₁ A_{2 .......}A_nthat splits the product between A_kand A_k + 1 contains within it optimal solutions to the problems of parenthesizing A₁A₂ .......A _k and A_{k +} 1A_{k +} 2. . . A_n. The technique that we used to show that subproblems have optimal solutions is typical.
6. assume that there is a better solution to the subproblem and show how this assumption contradicts the optimality of the solution to the original problem.
7. The optimal substructure of a problem often suggests a suitable space of subproblems to which dynamic programming can be applied.
8. Typically, there are several classes of subproblems that might be considered "natural" for a problem.
9. For example, the space of subproblems that we considered for matrix-chain multiplication contained all subchains of the input chain.
10. We could equally well have chosen as our space of subproblems arbitrary sequences of matrices from the input chain, but this space of subproblems is unnecessarily large.
11. A dynamic-programming algorithm based on this space of subproblems solves many more problems than it has to.

12. Investigating the optimal substructure of a problem by iterating on subproblem instances is a good way to infer a suitable space of subproblems for dynamic programming.

13. For example, after looking at the structure of an optimal solution to a matrix-chain problem, we might iterate and look at the structure of optimal solutions to subproblems, subsubproblems, and so forth. We discover that all subproblems consist of subchains of A_l, A₂, . . . , A_n. Thus, the set of chains of the form A_i, A_j+l, . . . , A_j.for 1  i  j n makes a natural and reasonable space of subproblems to use.

    1 if i = j
    

    2 then return 0
    

    3 m[i, j]  
    

    4 for k  i to j - 1
    

    5      do q RECURSIVE-MATRIX-CHAIN(p, i, k)
    

    + RECURSIE-MATRIX-CHAIN(p, k + 1, j) + pi-1pkpj
    

    6         if q < m[i, j]
    

    7            then m[i, j] q
    

    8 return m[i, j]

B.

function multiply(x, y)

Input: Positive integers x and y, in binary

Output: Their product

n = max(size of x, size of y)

if n = 1: return xy xL,

xR = leftmost dn/2e, rightmost bn/2c bits of x yL,

yR = leftmost dn/2e, rightmost bn/2c bits of y

P1 = multiply(xL, yL)

P2 = multiply(xR, yR)

P3 = multiply(xL + xR, yL + yR)

return P1 × 2 n + (P3 − P1 − P2) × 2 n/2 + P2