Data Structure & Algorithm Analysis - Dec 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) Explain the Asymptotic notations to measure the time complexity of algorithm.(5 marks) 1(b) What are linear and non-linear data structures?(5 marks) 1(c) Explain vectors with at least five methods.(5 marks) 1(d) Discuss circular and priority queue.(5 marks) 2(a) Write a program to create ?QUEUE? ADT using Linked list implementation. ADT should support following operations:-
(i) Create queue
(ii) Enqueue
(iii) Dequeue
(iv) Display(10 marks) 2(b) Explain Huffman Coding algorithm with example.(10 marks) 3(a) Write a program to implement Quick sort and comment on its complexity.(10 marks) 3(b) Implement the function to delete a node from Binary search tree. (consider all cases) (10 marks) 4(a) Write a program to create Binary tree and inorder, preorder and postorder traversal of the tree.(10 marks) 4(b) Write any pattern matching algorithm and explain with an example.(10 marks) 5(a) Using Prim's and Kruskal's algorithm find Minimum Spannin tree for the following graph.

(10 marks) 5(b) What is Hashing? What is meant by collision? Hash the following in table of size 10. Use any two collision resolution techniques:- 99, 33, 23, 44, 56, 43, 19(10 marks) 6(a) Given a 'INFIX' expression, write a program to convert it to its 'POSTFIX' form.(10 marks) 6(b) Write an algorithm to traverse a graph using:
i) Breadth first search
ii) Depth first search(10 marks)

Write short notes on any four of the following:-

7(a) Red Black trees(5 marks) 7(b) Searching algorithms(5 marks) 7(c) Recursion(5 marks) 7(d) Doubly linked list(5 marks) 7(e) Expression Trees(5 marks) 7(f) Comparison of sorting algorithms(5 marks)