|
Instructions
|
||||
|
Exercises 13 and 16 on p. 90. Make sure you walk through your algorithm for exercise 13 carefully |
13. Write an algorithm that sorts a list of n items by dividing it into three sublists of about n/3 items, sorting each sublist recursively and merging the three sorted sublists. Analyze your algorithm, and give the results under order notation.
16. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into 10 subinstances of size n/3, and the dividing and combining steps take a time in Θ(n^2) . Write a recurrence equation for the running time T(n), and solve the equation for T(n).
Exercises 19/20 on p. 91 and 24 on p. 641.
Exercises 19/20 are really just one problem. Show the recursion tree as part of showing the actions step-by-step. Also, determine the number of comparisons performed. The work on this exercise provides a test case for programming assignment 2.
19. Use Quicksort*(Algorithm 2.6) to sort the following list. Show the actions step by step.
123 34 189 56 150 12 9 240
20. Give the tree of recursive calls in Exercise 19.
On 24
c) the problem should read Assuming in each case that T*(n) is eventually nondecreasing, use Theorem B.5 to determine the order of the following recurrence equations. T(n) = 16 T(n/2) + 7 n^4 for n > 1, n a power of 2 T(1) = 1
Find the longest common subsequence of the strings: PRINCIPLE and OPTIMALITY.
