Q1.

(a) Write an appropriate class in Java for implementing a priority  queue data structure using a linked list.  It is enough to explain the variables and the method definitions (no need to write the bodies of the methods).

(5)

(b) Write an insertion method for a priority  queue in Java using the class you have written above. Analyse the complexity of this method.

(5)

Q2.

(a) A heap can be constructed in O(n) time for n inputs. Design an algorithm for finding the k-th smallest element in an unsorted array of length n that is faster than O(n log n) asymptotically.   Analyse the complexity of your algorithm assuming k as a constant.

(5)

(b) Explain the quicksort algorithm clearly.   Analyse the complexity of quicksort.

(5)

Q3.

(a) Given two functions f(n) and g(n), give a formal definition when we can say f(n) = O(g(n)).

(5)

(b)

● Prove that n log n is O(n2 ).

● Prove that n3 log n is not O(n3 ).

(5)

Q4.