Jawaharlal Nehru Technological University Kakinada 2010-1st Sem M.Tech Computer and Information Science SUBJECT CODE: C4001 REGULAR S ADVANCED DATA STRUCTURES AND ALGORITHMS (CSE – Common t

1. define queue ADT. Illustrate linked list implementation of a queue.

2.What is a Skip List? Show how to use a skip list to implement the dictionary ADT?

3.(a) define Heap sort. Take the input sequence 31,41,59,26,53,58,97. Construct the
Heap.
(b) How does the heap look after deleting the minimum element?
(c) How many comparisons does Heap sort take?

4. (a) What is meant by path compression? discuss.
(b) What is meant by union by size and union by height? discuss.

5. (a) Write a program to perform a topological sort on a graph.

6. Implement Dijkstra's Greedy algorithm.

7. (a) What is skew heap?
(b) Show that the amortized bound of?? (log N) for the skew heap.

8. (a) What is a Red-Black tree? provide example.
(b) Write the procedure for deletion in Red-Black tree.

Earning:   Approval pending.