Assignment VIII

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 is sufficient.