Data Structure & Algorithm Analysis - May 2011

Information Technology (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1(a) What is a data structure and Abstract Data type?(5 marks) 1(b) Explain the Asymptotic notations to measure the time complexity of algorithm.(5 marks) 1(c) What is Recursion? State the advantages and disadvantages.(5 marks) 1(d) What is a vector? Explain any four functions.(5 marks) 2(a) Write an ADT for stack and implement it using array. The ADT should support the following operations.
i) Create
ii) Push
iii) Pop
iv) Display(10 marks) 2(b) Write an algorithm to implement Quick Sort. Derive its Best case and Worst case time complexity.(10 marks) 3(a) What is a Priority queue? Explain the insertion and deletion operations on a Priority queue if implemented using an array.(10 marks) 3(b) Explain the working of merge sort.(10 marks) 4(a) Define Binary Tree. Write an algorithm to implement different tree traversal techniques.(10 marks) 4(b) What is a Doubly linked list? Write an algorithm to implement to following operations with DLL :
1.Insertion (All cases)
2.Traverse (Forward and backward)(10 marks) 5(a) What is an AVL tree? Construct the AVL tree for the following set of data:14,10,1,20,17,24,18,12,15, 11, 4, 6(10 marks) 5(b) Explain Huffman algorithm for encoding the characters. And construct the Huffman's code for following characters.

(10 marks) 6(a) Using Prim's and Kruskal's algorithm find Minimum Spannin tree for the following graph.

(10 marks) 6(b) What do you mean by Hashing and Collision. How do you resolve hash clashes?(10 marks)

Write short notes on any four of the following:-

7(a) MAP abstract Data Type(5 marks) 7(b) Splay Tree(5 marks) 7(c ) Pattern Matching(5 marks) 7(d) Graph Traversal(5 marks) 7(e) Expression Tree(5 marks)