Neapolitan, Foundations of Algorithms, 5th, Jones and Bartlett, 2015.

Instructions Exercises 1, 2 and 8-9 on pp. 88 - 89. Both 1 and 8 ask you to show the actions step-by-step.  To do this, show the recursion tree for both, also show what is returned "up" the tree in the BinarySearch, and the merging done in MergeSort.  Indicate the order of the recursive calls to MergeSort.
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.