Computer Science, Algorithm Design and Analysis

1. Implement a merge sort algorithm in your favorite programming language (e.g. C, Java, Python, etc.). Modify the code, so that it prints the following:

The initial input sequence to be sorted, and its length. The order of the elements in the sequence, after the merge step has been performed on all the elements. Print this for every recursion depth, in the order the merges are performed. The total number of comparison operations performed during the run of the algorithm (a comparison operation is when 2 array elements are compared).

For instance, if the input array is [5, 3, 1, 2, 8, 4, 7, 6], you should print:

INPUT: 5,3,1,2,8,4,7,6 (length 8) MERGE STEP 1: 3,5,1,2,4,8,6,7 MERGE STEP 2: 1,2,3,5,4,6,7,8 MERGE STEP 3: 1,2,3,4,5,6,7,8 COMPARISONS: 14

Note that the number of comparisons will depend not only on the input given, but the specific way you implement merge sort, so you may get a slightly different number than above.

its output on the following input test cases: Array of numbers 1, 2, . . . , 50 (already in correct sorted order) Array of numbers 50, 49, . . . , 1 (reverse of correct sorted order) Array of 50 different random numbers

2. Insertion sort can be expressed as a recursive procedure. To sort A[1 . . . n], we recursively sort A[1 . . . n1] and then insert A[n] into the sorted array A[1 . . . n1]. Write a recurrence for the running time of this recursive version of insertion sort.

3. For parts (a)-(e), decide if it is true or false. If the statement is true, then prove it (to prove it you will either need to use the definition and find constants or use the limit laws). If the statement is false, then give a reason or a counterexample. Then answer part (f). 1. 10n2 = O(n3). 2. n2 (n3) 3. 2n O(2n+1) 4. n! ((n + 1)!) 5. n = O(nsin(n)) 6. What does O(1) mean? What does (1) mean?

4. Let f (n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures. a. f (n) = O(g(n)) implies g(n) = O(f (n)) b. f (n) + g(n) = (max(f (n), g(n))) c. f (n) = O(g(n)) implies g(n) = (f (n))

5. nalyze the running time of the code fragments below. For simplicity, assume that n is a power of 2.

for (i = 1; i <= n; i++) { j = n; while (j >= 1) { // body of the while loop //requires theta(1) time j = [j/2] }

}

6.

Let f (n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures. 1. f (n) = O(g(n)) implies 2f (n) = O(2g(n)).

2. f (n) = O((f (n))2).