16

17

18

19

20

b)

a)

a)

b)

a)
b)

08000CS205122003

Sort the following elements using quick sort algorithm
< 2, 10, 9, 6, 1, 15,5, 11 >
Write an algorithm to perform Depth First Search. Apply DFS on below graph

۰
rey

Sort the following sequence using insertion sort
3, 10, 4, 2, 8, 6, 5, 1
What is heap? Write an algorithm to perform heap sort.

Illustrate heap sort algorithm using the following list

82, 90, 10, 12, 15, 77, 55, 23
Define hashing and collision? Discuss the advantages and disadvantages of
hashing over other searching techniques.
Apply Binary search to find 123 in a list
49, 198, 101, 123, 149, 194, 199, 211, 240, 286, 840, 930
Mention the best case and worst case time complexity of binary search
algorithm.
Consider a hash table with 9 slots. The hash function h(k) = k mod 9. The
following keys are inserted in the order 5, 28, 19, 15, 20, 33, 12, 17, 10. Draw the
contents of hash table when the collision are resolved by

1) Chaining

2) Linear Probing

3) Double hashing. The second hash function h2(x) = 7- (x mod 7)

Write the algorithm for linear search. Analyse the best and worst case
performances.
What is hash function? Explain any two hash functions with examples.

Explain the different collision resolution techniques.

KKK KK

Page 3 of 3

(6)
(5)

(5)
(5)
(5)
(5)
(5)

(6)

(4)

(5)
(5)