Homework #4 Solution

$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.

  1. (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).

  1. (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 max-imum. 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

log2n

take O(

(i

1)=2

)

O(

), since you must check each elements

iP 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.

  1. Counting Sort (4 points)

    1. (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)

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

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

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

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

  1. for i = 0 to k do

  1. C[i] = 0;

  1. end for

  1. for i = 1 to n do

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

  1. end for

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

  1. for i = 1 to k do

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

  1. end for

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

  1. for i = n down to 1 do

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

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

  1. end for

  1. 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

  1. (2 points) Describe an algorithm that, given an unsorted array of n in-tegers 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

  1. (1 point) Now compute the hash function of the key 14 using the

implementation we described in our notes.

You can assume we have a word size w = 4. Since m = 8 = 23, p = 3. Since A = 0:625 = 10=24 = 10=2w, 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 11002 with 2w = 8 bits the rst p = 4 bits are 1100

11002 = 610 so the hash slot is 6