**Ex. 1.1-1, p5**

Using Figure 1.2 as a model, illustrate the operation of INSERTION-SORT on the array A = <31, 41, 59, 26, 41, 58>.**Ex. 1.1-2, p5**

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.**Ex. 1.2-1, p10**(Modified)

Consider sorting n numbers stored in array A by first finding the smallest elements of A and putting it in the first entry of another array B. Then find the second smallest element of A and put it in the second entry of B. Continue in this manner for n elements of A. Write pseudocode for this algorithm. Give the best-case and worst-case running times of selection sort in Big-Theta-notation.Modifications: Assume there are no duplicates in the initial entries of A. Also assume that the symbol INFINITY is not in A. Each time an entry in A has been copied, replace that entry in A with INFINITY.

**Ex. 1.3-1, p15**

Using Figure 1.3 as a model, illustrate the operation of merge sort on the array

A = <3, 41, 52, 26, 38, 57, 9, 49>. **Ex. 1.3-3, p15**(Modified)

**Part I.**

Use weak mathematical induction to show that the solution of the recurrence{ 2 if n = 2 T(n) = { { 2T(n/2) + n if n= 2

^{k}, k > 1**Part II.**

Then use strong mathematical induction to show that the solution of the recurrence{ 0 if n = 0 or 1 T(n) = { { 2T( FLOOR(n/2) ) + n if n > 1

Last Modified: September 25, 1997