18

19

20

a)
b)

a)
b)

a)

b)

08000CS205122001

Write the algorithm for insertion sort. Analyse its performance for sorted input.
What are the limitations of linear probing? How can double hashing be used to
resolve these limitations? Illustrate with examples.

Write the algorithm for mergesort. Give its best and worst case performances.
What is open hashing? How is it used to resolve collisions in a hash table?
Compare its performance with closed hashing.

Write the algorithm for Quicksort. Analyse its worst case and best case
performances.

Let the size of the hash table be 12. Consider the keys 43, 24, 57, 12, 10, 64,
19, 82, 36, 39 in the order. Show how the keys are occupied using chaining

method.

मे ‏بد‎ RR

(4)
(6)

(5)
(5)

(6)

(4)

3/3