Monday, July 5, 2010

Dynamic Programming Practise Problem Set 2

  1. 1. Below is a dynamic programming solution for this problem to illustrate how it can be used. There is a very straightforward O(1) time solution. It can be shown that इफ n >= 50 then any solution will include a set of coins that adds to exactly 50 cents.
    Hence it can be shown that an optimal solution uses 2 · [n/50 ] quarters along with un optimal solution for making n/50 − bn/50c cents which can be looked up in a table ऑफ़ size 50.
    Here’s the dynamic programming solution for this problem. (It does not use the फक्त that an optimal solution can be proven to use 2 · bn/50c quarters and hence is not अस efficient.) The general subproblem will be to make change for i cents for 1 i n. Let
    c[i] denote the fewest coins needed to make i cents. Then we can define c[i] recursively
    by:
    c[i] =
    8><
    >:
    use i pennies if 1 i < 9
    c[i − 10] + 1 if 10 i < 24
    min(c[i − 10] + 1, c[i − 25] + 1) if i 25
    Note that c[n] is the optimal number of coins needed for the original problem.
    Clearly when i < 10 the optimal solution can use only pennies (since that is the
    only coin available). Otherwise, the optimal solution either uses a dime or a quarter
    and both of these are considered. Finally, the optimal substructure property clearly
    holds since the final solution just adds one coin to the subproblem solution. There
    are n subproblems each of which takes O(1) time to solve and hence the overall time
    complexity is O(n).
  2. Recall that D1 is a DNA sequence with n1 characters and D1 is a DNA sequence with
    n2 characters. The general form of the subproblem we solve will be: Find the best
    alignment for the first i characters of D1 and the first j characters of D2 for 1 i n1
    and 1 j n2. Let D(i) be the ith character in string D. Let c[i, j] be the cost of
    an optimal alignment for D1(1), . . . ,D1(i) and D2(1), . . . ,D2(j). We can define c[i, j]
    recursively as shown (where c[n1, n2] gives the optimal cost to the original problem):
    c[i, j] =
    8>>><
    >>>: i
    if j
    =
    0
    j if i = 0
    c[i − 1, j − 1] if D1(i) = D2(j)
    min{c[i − 1, j − 1], c[i − 1, j], c[i, j − 1]} + 1 otherwise

    We now argue this recursive definition is correct. You can form D01 and D02 (and hence
    the alignment) for the subproblem from the right to left as follows. In an optimal
    alignment either the last character of D01 is a space or it is the last character (character
    i) of D1 and the last character of D02 is a space or it is the last character (character
    j) of D2. If D1(i) = D2(j) then clearly it is best to align them (so add a space to
    neither). However, if D1(i) 6= D2(j) then a space could be added to neither or just
    one. In all three cases one mismatch is caused by the last characters. Notice that
    there would never be any benefit in ending both D1 and D2 with a space. Hence the
    above recursive definition considers all possible cases that the optimal alignment could
    have. Since the solution to the original problem is either the value of the subproblem
    solution (if D1(i) = D2(j)) or otherwise one plus the subproblem solution, the optimal
    substructure property clearly holds. Thus the solution output is correct.
    For the time complexity it is clearly O(n1 · n2) since there are n1 · n2 subproblems each
    of which is solved in constant time. Finally, the c[i, j] matrix can be computed in row
    major order and just as in the LCS problem a second matrix that contains which of
    the above 4 cases was applied can also be stored and then used to construct an optimal
    alignment.
  3. Let m[i] be the rental cost for the best solution to go from post i to post n for 1 i n.
    The final answer is in m[1]. We can recursively, define m[i] as follows:
    m[i] =
    8<
    :
    0 if i = n
    min
    i
    (fi,j + m[j]) otherwise
    We now prove this is correct. The canoe must be rented starting at post i (the starting
    location) and then returned next at a station among i + 1, . . . , n. In the recurrence
    we try all possibilities (with j being the station where the canoe is next returned).
    Furthermore, since fi,j is independent from how the subproblem of going from post
    j, . . . , n is solved, we have the optimal substructure property.
    For the time complexity there are n subproblems to be solved each of which takes
    O(n) time. These subproblems can be computed in the order m[n],m[n−1], . . . ,m[1].
    Hence the overall time complexity is O(n2).
    NOTE: One (of several) alternate general subproblem form that also leads to an O(n2)
    algorithm is to find the best solution to get from post i to post n where the canoe
    cannot be exchanged until post j is reached (for 1 i < j n).
  4. The general form of the subproblem we solve will be: determine if z1, . . . , zi+j is an
    interleaving of x1, . . . , xi and y1, . . . yj for 0 i m and 0 j n. Let c[i, j] be
    true if and only if z1 . . . , zi+j is an interleaving of x1, . . . , xi and y1, . . . , yj . We use the
    convention that if i = 0 then xi = (the empty string) and if j = 0 then yj = . The
    subproblem c[i, j] can be recursively defined as shown (where c[m, n] gives the answer

    to the original problem):
    c[i, j] =
    8>>>>>><
    >>>>>>:
    true if i = j = 0
    false if xi 6= zi+j and yj 6= zi+j
    c[i − 1, j] if xi = zi+j and yj 6= zi+j
    c[i, j − 1] if xi 6= zi+j and yj = zi+j
    c[i − 1, j] _ c[i, j − 1] if xi = yj = zi+j
    We now argue this recursive definition is correct. First the case where i = j = 0 is
    when both X and Y are empty and then by definition Z (which is also empty) is a
    valid interleaving of X and Y . If xi 6= zi+j and yj = zi+j then there could only be a
    valid interleaving in which xi appears last in the interleaving, and hence c[i, j] is true
    exactly when z1, . . . , zi+j−1 is a valid interleaving of x1, . . . , xi−1 and y1, . . . yj which is
    given by c[i − 1, j]. Similarly, when xi 6= zi+j and yj = zi+j then c[i, j] = c[i − 1, j].
    Finally, consider when xi = yj = zi+j . In this case the interleaving (if it exists) must
    either end with xi (in which case c[i − 1, j] is true) or must end with yi (in which
    case c[i, j − 1] is true). Thus returning c[i − 1, j] _ c[i, j − 1] gives the correct answer.
    Finally, since in all cases the value of c[i, j] comes directly from the answer to one of
    the subproblems, we have the optimal substructure property.
    The time complexity is clearly O(nm) since there are n ·m subproblems each of which
    is solved in constant time. Finally, the c[i, j] matrix can be computed in row major
    order.

0 comments:

Post a Comment