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= 2^k, 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.

Last Modified: September 25, 1997