Student Name: J#: 4) Given the following array, do the following (show all the w
ID: 3701838 • Letter: S
Question
Student Name: J#: 4) Given the following array, do the following (show all the work). A = {56, 89, 23, 58, 22, 11, 45, 48, 90) (a - 5 pts) Construct a hash table for the given array using the hash function H(K)- K mod 5 (b - 4 pts) Determine the average number of comparisons for a successful search using the hash table of (c - 3 pts) What is the worst case number of comparisons for an unsuccessful search in the hash table of (d - 7 pts) Show the sequence of iterations run on the array to get it sorted using the Selection Sort algorithm. (e-8 pts) Use the sorted array of (d) to construct a binary search tree (f- 5 pts) Determine the average number of comparisons for a successful search in the binary search tree of (e). (g-8 pts) Determine average number of comparisons for an unsuccessful search in the binary search tree of (f)Explanation / Answer
a.)Given no. of Keys = 9. but we have been given the hash function H(K)= K mod 5 by this we can only make Hash Table of size= 5. So, I have made some assumption: 1. The collision is resolved by Linear Probing (If we find index K %5 occupied then we will search the next unoccupied index), 2. First we take the Hash Table of size 5, but when during searching the next unoccupied index we reach the last index(which is also occupied) then we increase the size of the table by 5, 3.Let if we get a key K and index K%5 is occupied and during searching the next unoccupied index we reach the last index then we place the key at index j*5*(K%5), means in the next segment of the table and in next we got the same situation then in the next to next and so on.
Here, we have been given the keys: {56,89,23,58,22,11,45,48,90}
first we have table of size 5 indexing 0 to 4:
Insert 56, 56%5=1 at i=1
Insert 89, 89%5=4 at i=4
Insert 23, 23%5=3 at i=3
Insert 58, 58%5=3 at i=3 but i=3 is already occupied so, will search next unoccupied index but we reach to last index which is also occupied so increase the size of the table by 5 and put the key at (K%5) +5=3+5=8
insert 22: 22%5=2 s at i=2
Insert 11: 11%5=1 but i=1 is already occupied so search for the next unoccupied index and we reached to 5*j-1=4, so go to 5+(K%5) =6 and 6 is unoccupied so place 11 here:
Insert 45: 45%5=0 so at i=0:
Insert 48: 48%5=3 but i=3 is already occupied so search for the next unoccupied index and we reached to 5*j-1=4, so go to 5+(K%5) =8 but 8 is also occupied so search for the next unoccupied index i.e. 9
Insert 90: 90%5=0, but i=0 is already occupied so search for the next unoccupied index we reached to 5*j-1 i.e.4 so go to 5+(K%5) =5 :
i.e. the final hash table after inserting all the elements
b.) average no. of comparisons for successful search in above HashTable:
for 56: 1
for 89: 1
for 23: 1
for 58: 1+(1)+1=3
for 22: 1
for 11: 1+(1+1+1)+1=5
for 45: 1
for 48: 1+(1)+1+(1)=4
for 90: 1+(1+1+1+1)+1=6
therefor average no. of comparison= (1+1+1+3+1+5+1+4+6)/9=23/9 =:3
c.)Worst case for unsuccessful search will be when we search multiple of 5 (other than 45 and 90) for this we will need : 1+(4)+1+(4)= 10 no. of comparisons
d.)Selection sort says that, select the ith smallest element in the list and swap it with ith element of the list.
Sorting the above HashTable using selection sort:
each below step shows the result of selecting ith smallest element and swapping that with ith element:
1.11,56,22,23,89,90,45,58,48
2.11,22,56,23,89,90,45,58,48
3.11,22,23,56,89,90,45,58,48
4.11,22,23,45,89,90,56,58,48
5.11,22,23,45,48,90,56,58,89
6.11,22,23,45,48,56,90,58,89
7.11,22,23,45,48,56,58,90,89
8.11,22,23,45,48,56,58,89,90
9.11,22,23,45,48,56,58,89,90
//If you have any doubt regarding the answer please ask in the comment section, due to insufficient time I have not soled the rest part
//Please upvote
0 1 2 3 4