1. Suppose you have an array of n items (the "member items") and a separate list of k items (the "test items"). The member items are not stored in any particular order. You want to know which of the k test items belong to the set of member items. Here are two di?erent ways to solve the problem:

• Algorithm 1: Look up each test item in the array of member items, using sequential search.

• Algorithm 2: Sort the array of member items, using an optimal comparison- based sorting algorithm, and then look up each test item in the array of member items using binary search. Answer the following problems, and brie?y justify your answer to each part. (a) What is the worst-case running time of Algorithm 1 (asymptotically, in terms of n and k)? (b) What is the worst-case running time of Algorithm 2 (asymptotically, in terms of n and k)? (c) For a given value of n, for what values of k is Algorithm 2 at least as e?cient as Algorithm 1? (Express your answer using asymptotic notation, in terms of n). 2. Suppose we are given n numbers, initially stored in an array A and we wish to sort them. When the sort concludes, the sorted output is to be in the array A, in ascending order (i.e., the smallest value in A[0], the next smallest in A[1], etc.). Suppose we use, as our measure of time, the number of times we store a value into the array. In other words,

• If x is any value, an assignment statement of the form A[i] = x has a cost of 1. In particular, an assignment statement of the form A[i] = A[j ] has a cost of 1.

• Any other operation (including a comparison between two array items A[i] and A[j ], or an assignment x = A[i] where x is not a location in the array A) has a cost of 0. (a) Under this cost model, give a lower bound on the worst-case time required to sort the array A. Your answer should be an exact expression in terms of n (i.e., it should not involve asymptotic notation). (b) Describe a sorting algorithm that is optimal with respect to this cost model and uses O(n) space. That is, time used by your algorithm should exactly match the lower bound given in (a).) describe why your algorithm satis?es the cost and space requirements. 1 (c) Describe an in-place sorting algorithm that is optimal with respect to this cost model. That is, the time used by your algorithm should exactly match the lower bound given in (a).) describe why your algorithm satis?es the cost requirement and is in-place. 3. De?ne a sorting algorithm to be parsimonious if it never compares the same pair of input values twice. (Assume that all the values being sorted are distinct.) For ex, it was shown in the notes that quicksort is parsimonious. (a) Is insertion sort parsimonious? Justify your answer with either a counterex or a brief argument. (b) Is merge sort parsimonious? Justify your answer with either a counterex or a brief argument. (c) Is heap sort parsimonious? Justify your answer with either a counterex or a brief argument.