Till KTH:s startsida Till KTH:s startsida

Exercises

Exercises and solutions

Exercise 1 Problems

Exercise 1 Solutions

Exercise 2 Problems

Exercise 2 Solutions

Exercise 3+4 Problems

Exercise 3+4 Solutions

Exercise 5 Problems

Exercise 5 Solutions

Exercise 6 Problems

Exercise 6 Solutions

Exercise 7 Problems

Exercise 7 Solutions

Exercise 8 Problems

Exercise 8 Solutions

Exercise 9 Problems

Exercise 9 Solutions

Johan Karlander skapade sidan 9 januari 2017

kommenterade 9 februari 2017

I failed during today's exercise to motivate that all q[b+1][c] have been computed when q[a][b] is computed for the binary string accordion fold problem. I post the motivation here.

profit computes the number of horizontal pairs where indexes b and b+1 are the folding points between a and c.
profit(p[1, ..., n], a, b, c)
    //shortest is the length of the parallel traits.
    if b-a < c-(b+1) then
      shortest := b-a
    else
      shortest := c-(b+1)

    //s is the number of horizontal 1-neighbors.
    s := 0
    for (i := 1; i ≤ shortest; i := i+1)
      if p[b-i]=1 ∧ p[b+1+i]=1 then
          s := s + 1

    return s

//protein_folding computes the maximum number of horizontal 1-pairs not next to each other in p over all possible accordion folds of p.

protein_folding(p[1, ..., n])
    //Step 1.
    for (a := 1; a ≤ n-1; a := a+1)                        //ϴ(n) iterations.
        q[a][n] := 0

    //Step 2.
    for (b := n-1; b ≥ 2; b := b-1)                        //O(n) iterations.
        for (a := 1; a ≤ b-1; a := a+1)                    //O(n) iterations.
            t := 0

            for (c := b+2; c ≤ n; c := c+1)                //O(n) iterations.
                v := profit(p, a, b, c) + q[b+1][c]        //O(n) iterations.
                if v > t then
                    t := v

            q[a][b] := t

    //Step 3.                                            //ϴ(n) iterations.
    max := 0
    for (b := 2; b ≤ n; b := b+1)
        if q[1][b] > max then
            max := q[1][b]

    return max



View q[][] as a square matrix. q[][] is computed by the following steps (marked in the algorithm above):

  1. Column n is initialized to zero, except for the bottom element at row n (q[i][i] denote no trait).
  2. q[a][b] = MAX(profit(p, a, b, c) + q[b+1][c]), maximized over c, b+2 ≤ c ≤ n.
    1. q is computed column-wise starting from right: b = n - 1 to b = 2 (b goes to 2 since q[a][b], b = 1, is not a trait since a must be less than b).
    2. Each column is computed downwards: a = 1 to a = b - 1 (recall that a must be less than b to form a trait).
    3. When q[a][b] is computed, q[b+1][c] must have been computed, for each c, b + 2 ≤ c ≤ n. Is this the case? Yes, which can be reasoned as follows. Since c ≥ b + 2, and columns are processed from n down to 2, column c has already been processed. When column c was processed, q[a][c] was computed for a, 1 ≤ a ≤ c - 1 (see middle for loop: 1 ≤ a ≤ b - 1), meaning that all entries in column c were computed down to row c - 1. Since c ≥ b + 2, all entries in column c were computed at least down to row c - 1 ≥ b + 2 - 1 = b + 1. Also, the rightmost column n is computed during initialization down to row n - 1. Hence, the entries at row b + 1 for columns c, b + 2 ≤ c ≤ n, q[b+1][c], have been computed when q[a][b] is computed.
  3. Check maximum value of q[1][b], for 1 < b ≤ n.
Anmäl missbruk
2 personer gillar kommentaren