# Homework 1

Due: Thursday, September 11, 1997
• 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= 2k, k > 1
```
is T(n) = n lg(n) when n is a positive power of 2.

• 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
```
is T(n) =< n lg(n) for n >= 0, where 0 lg(0) is defined to be 0.