6.006 Final Exam Solutions Name 17
The second mistake was over the definition of DP(i, b). In the problem, we explicitly
define DP(i, b) to be the length of the longest subsequence that ends on x
i
and is
increasing iff b is TRUE. As a result, DP(6, TRUE) is equal to 1, not 4, because the
only ascending subsequence ending on the value x
6
= 4 is the subsequence hx
6
i.
(b) [4 points] Give a recurrence relation to compute DP(i, b).
Solution: The following formula computes DP (i, b) as defined in the problem:
DP(i, TRUE) = 1 + max DP(j, FALSE)
1≤j<i and x
i
>x
j
DP(i, FALSE) = 1 + max DP(j, TRUE)
1≤j<i and x
i
<x
j
The most common mistake for this problem involved confusion over the definition of
DP(i, b). Many people gave or attempted to give the following recurrence:
DP(i − 1, TRUE)
DP(i, TRUE) = max
DP(i − 1, FALSE) + 1 if x
i
> x
i−1
DP(i
DP(i, FALSE) = max
− 1, FALSE)
DP(i − 1, TRUE) + 1 if x
i
< x
i−1
Unfortunately, this recurrence does not compute the value that we asked for. The value
DP(i, b) is specifically defined as “the length of the longest alternating subsequence
that ends with x
i
, and ends in an ascending pair if and only if b is TRUE.” The above
recurrence relation instead computes the length of the longest alternating subsequence
of x
1
, . . . , x
i
, not necessarily ending on x
i
, that ends in an ascending pair if and only
if b is TRUE.
(c) [4 points] Give the base cases of your recurrence relation.
Solution: The base cases matching the recurrence relation above are:
DP(i, TRUE) = 1 if x
i
= min{x
1
, . . . , x
i
}
DP(i, FALSE) = 1 if x
i
= max{x
1
, . . . , x
i
}
(d) [3 points] Give a valid ordering of subproblems for a bottom-up computation.
Solution: The correct order is to iterate through the values of i in increasing order,
and compute DP (i, TRUE) and DP (i, FALSE) for each i. The recurrence relation has
DP(i, b) dependent only on values DP(j, b) for j < i, so increasing order will give us
what we want.
(e) [3 points] If you were given the values of DP (i, b) for all 1 ≤ i ≤ n and all b ∈
{TRUE, FALSE}, how could you use those values to compute the length of the longest
alternating subsequence of x
1
, x
2
, . . . , x
n
?