Question

Q : Give a brief answer to the following questions: :

a) Given an array A [ 20, 60 , 80 , 90 , 90 , 100 , 110 ] and key = 90 ; in how many iterations would the liner search and binary search reach to the key ? And why ? (2 marks )

b) What is the name of the algorithm that is able to find the k^th smallest element in an unordered list (1 mark) ?

c) If several elements are competing for the same bucket in the hash table, what is it called? and list two techniques to avoid this scenario?

d) In simple uniform hashing, what is the search complexity ? (1 mark)

e) Let A be an array with N integer numbers, where all N numbers has a value between 1 and 3N. How fast can the N numbers be sorted? O(1), O(3N), O(N log N), or O(N²). What’s the sorting algorithm that should be used to achieve your choice?

f) Arrange the complexities of the following operations (from worst to best):   2 n², 2 log n , n log 3n , 4 n , 55 log 64 , 2ⁿ . (3 marks )

g) mention one advantage of the heap-sort over the merge-sort algorithm and list their complexities (3 marks )

Answer 1