Due date May 2
1. From text: R-5.4: recurrence relations for divide-and-conquer algorithms.
2. Consider the Longest Subsequence problem described on page 446. Show that
the table in figure 9.20 shows two different solutions for the given strings.
3. From text: R-9.14: solve the Longest Subsequence problem by tracing the
algorithm we described, and building the subsequence table.
4. Consider the example of an optimal search tree discussed in class: the
keys are the characters a, b .. g. Suppose now that their relative frequencies
are: 5, 3, 1, 3, 5, 2, 1 (not the ones we used in class). Build the optimal
search tree for these values.
5. Suppose that we have built an optimal search tree for a set of keys, and
the frequency of one key is increased by some amount k. Can you find the new
optimal search tree without recomputing it in full? A sketch of the algorithm