Due by: September 10, 2003
Submit: by e-mail to TA at bdrew@cs.gmu.edu
(In the subject specify: CS483-002 HW1)
1. (5 points) Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1] (see exercise 2.3-4). Write pseudocode for this algorithm and a recurrence for its running time.
Solution:
RECURSIVE-INSERTION-SORT (A,n)
1 if n>1
2 RECURSIVE-INSERTION-SORT (A,n-1)
3 INSERT(A,n)
INSERT(A,k)
// Insert A[k] to the sorted A[1..k-1]
// Use Insertion-Sort without outside loop
1 key=A[k]
2 i=k-1
3 while i>0 and A[i]>key
4 A[i+1] = A[i]
5 i--
6 A[i+1] = key
T(1) = Q(1)
T(n) = T(n-1) + O(n)
2. (5 points) Rewrite the Merge procedure so that it does not use sentinel elements; see exercise 2.3-2.
Solution:
MERGE (A, p, q, r)
1 n1 = q-p+1
2 n2 = r-q
3 // create left and right arrays
4 for i=1 to n1
5 L[i] = A[p+i-1]
6 for i=1 to n2
7 R[i] = A[q+i]
8 i=1
9 j=1
10 for k=p to r
11 if (i > n1)
12 A[k]=R[j]
13 j = j+1
14 else if (j > n2)
15 A[k]=L[i]
16 i = i+1
17 else if L[i] <= R[j]
18 A[k]=L[i]
19 i = i+1
20 else
21 A[k]=R[j]
22 j = j+1
3. (Bonus 1 point) Verify and prove if the following statements are true (exercise 3.1-4):
Solution:
Part A. True. We need to prove that there exists c>0 that for all n>n0:
2n+1 <= c 2n
Choose n0 = 1, then we have
2 2n <= c 2n
c >= 2 ÿ
Part B. False. Similarly, we would have
22n <= c 2n
c >= 2n for any n>n0, hence c cannot be a constant.