Description

1. A = [6,8,6,10,12,9,15,13,14,19,18,17,16]

2. a. A = [10, 3, 9, 4, 8, 5, 7, 6], p = 1, r = 8, k =2
A = [3, 4, 5, 6, 9, 8, 7, 10], p = 1, r = 8, k = 2 A = [3, 4, 5, 6, 8, 9, 7, 10], p = 1, r = 8, k = 2
A = [3, 4, 5, 6, 8, 9, 7, 10]
b. 1. The first base occurs when the starting and ending indexes are equal.
Executed steps: step 1 (passes).
T(first base case) = 7
2. The second base case occurs when kth smallest number is equal to the pivotDistance, so then the number at the pivot index is returned, A[q].
Executed steps: step 1 (fails), step 2, step 3, step 4 (passes), step 5. T(second base case) = 20n + 17
3. Excecuted steps: step 1 (fails), step 2, step 3, step 4 (fails), step 6 , step 7 (executed if step 6 passes), step 8 (executed if step 6 fails).
Worst case: T(n) = (T(n-1) (20n + 16 + T(n-1))) + 7
Best case (one element): T(n) = 7
Best case (sorted array): T(n) = 20n + 7

3. A = [19, 6, 10, 7, 16, 17, 13, 14, 12, 9]
C =
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1
=
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 0 0 0 0 0 1 2 2 3 4 4 5 6 7 7 8 9 9 10

=
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 0 0 0 0 0 0 1 2 2 3 4 4 5 6 7 7 8 9 9

B = [6, 7, 9, 10, 12, 13, 14, 16, 17, 19]

4. 1. [3210, 4321, 2345, 4567, 5678]
2. [3210, 4321, 2345, 4567, 5678]
3. [3210, 4321, 2345, 4567, 5678]
4. [2345, 3210, 4321, 4567, 5678]

5. If length(A)=15
Bucket0: 0..1/15
Bucket1: 1/15..2/15
Bucket2: 2/15..3/15
Bucket3: 3/15..4/15
Bucket4: 4/15..5/15
Bucket5: 5/15..6/15
Bucket6: 6/15..7/15
Bucket7: 7/15..8/15
Bucket8: 8/15..9/15
Bucket9: 9/15..10/15
Bucket10: 10/15..11/15
Bucket11: 11/15..12/15
Bucket12: 12/15..13/15
Bucket13: 13/15..14/15
Bucket14: 14/15..15/15

If length(A)=n
Bucket0: 0..1/n
Bucket1: 1..2/n
Bucket(n-2): n-2/n..n-1/n
Bucket(n-1):n-1/n..n/n

6. a.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 14 3 3 3 1 1 8 3 3 3 3 1 14 18 16 19 20 1

b.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-3 1 14 3 3 3 1 1 8 3 3 3 3 1 14 1 16 16 16 16

c.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 1 -20 3 3 3 1 1 8 3 3 3 3 3 14 3 16 16 16 16

d.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 14 3 3 3 1 1 8 3 3 3 3 1 14 1 1 1 1 1

7.