$30.00
Description
1. Heapsort (4 points)
Originally we stored our heap in an array. Consider instead storing our heap as a doubly linked list.

(2 points) For a node i what are the new asymptotic run times for lef t(i), right(i), and parent(i)? Justify your answer.
For each operation you calculate the index you need using the appropriate formulas then return the pointer to the calculated index by traversing there using the di erence between i and the calculated index. Thus given
i, then each operation is O(2i + 1 i), O(2i + 2 i), O(i (b(i 1)=2c)) respectively. Ignoring constants they are all O(i).

(2 points) How does this a ect the run times of ndMax(), insert(key), extractMax()? Justify your answer.
ndMax() will still be (1) since the rst element will still be the maximum. For insert(key), the list must rst be traversed which takes (n)
time, then in the worst case key is greater than all other elements and will

logn
c
log^{2}n
take O(
(i
1)=2
)
O(
), since you must check each elements
_{i}^{P} b
4
=0
parent as you traverse up the list, thus insert(key) will take (n) worst case run time since you always traverse the entire list to start at the end when inserting. Finally, for extractMax() using similar logic, it is easy to see that it will also be (n) runtime since you must traverse the entire last to get the element that will replace the extracted element at the top of the heap.

Counting Sort (4 points)


(2 points) Illustrate the operation of countingSort(f2; 1; 5; 3; 1; 2; 5g; 6). Speci cally, show the changes made to the arrays A, B, and C for each pass through the for loop at line 16.

Algorithm 1 void countingSort(int A[1 : : : n], int k)

//Precondition: The n values in A are all between 0 and k

Let C[0 : : : k] be a new array

//We will store our sorted array in the array B.

Let B[1 : : : n] be a new array

for i = 0 to k do

C[i] = 0;

end for

for i = 1 to n do

C[A[i]] = C[A[i]] + 1;

end for

//C[i] now contains the # of elements in A equal to i

for i = 1 to k do

C[i] = C[i] + C[i 1];

end for

//C[i] now contains the # of elements in A that are to i

for i = n down to 1 do

B[C[A[i]]] = A[i];

C[A[i]] = C[A[i]] 1;

end for

return B;

A remains the same through the algorithm.
2
1
5
3
1
2
5
Now each line will show B and C at each pass through the loop.
B!
0
0
0
0
0
0
0
C!
0
2
4
5
5
7
7
B!
0
0
0
0
0
0
5
C!
0
2
4
5
5
6
7
B!
0
0
0
2
0
0
5
C!
0
2
3
5
5
6
7
B!
0
1
0
2
0
0
5
C!
0
1
3
5
5
6
7
B!
0
1
0
2
3
0
5
C!
0
1
3
4
5
6
7
B!
0
1
0
2
3
5
5
C!
0
1
3
4
5
5
7
B!
1
1
0
2
3
5
5
C!
0
0
3
4
5
5
7
B!
1
1
2
2
3
5
5
C!
0
0
2
4
5
5
7

(2 points) Describe an algorithm that, given an unsorted array of n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range a to b in O(1) time. Your algorithm should use O(n + k) preprocessing time.
(Hint: Look at the array C which is computed by the above code for inspiration)
Algorithm 2 int countInRange(int A[1 : : : n], int a, int b)

1:
//Precondition: The n values in A are all between 0 and k
2:
Let C[0 : : : k] be a new array
3:
for i = 0 to k do
4:
C[i] = 0;
5:
end for
6:
for i = 1 to n do
7:
C[A[i]] = C[A[i]] + 1;
8:
end for
9:
//C[i] now contains the # of elements in A equal to i
10:
for i = 1 to k do
11:
C[i] = C[i] + C[i 1];
12:
end for
13:
//C[i] now contains the # of elements in A that are to i
14:
int count;
15:
if a = 0 then
16:
count = C[b];
17:
else
18:
count = C[b] C[a 1];
19: end if
20: return count;
3. Hash Table (7 points)
(1) Consider
inserting
the
keys
2; 21; 3; 58; 11; 42; 34 into a hash table of
length m = 10 with the hash function h(k) = k mod 10.
(a) (2 points) Illustrate the result of inserting these keys using linear
probing to resolve collisions.
0
1
2
3
4
5
6
7
8
9
21
2
3
11
42
34
58
(b) (2 points) Illustrate the result of inserting these keys using chaining
to resolve collisions.
0
1
2
3
4
5
6
7
8
9
21
2
3
34
58
11
42
(2) Consider inserting the keys 8; 5; 14 into a hash table of length m = 8 with the hash function h(k) = bm(kA bkAc)c where A = 0:625.
(a) (2 points) Illustrate the result of inserting these keys.

0
1
2
3
4
5
6
7
8
5
14
implementation we described in our notes.
You can assume we have a word size w = 4. Since m = 8 = 2^{3}, p = 3. Since A = 0:625 = 10=2^{4} = 10=2^{w}, s = 10.
(Hint: Compute ks and convert it to a binary number. This number
will consist of 2w bits. Look at the rightmost w bits. Of those bits, convert the leftmost p bits back to an integer. This integer is your hash table slot.)
k s = 14 10 = 140 = 0100 1100_{2} with 2w = 8 bits the rst p = 4 bits are 1100
1100_{2} = 6_{10} so the hash slot is 6