Data Structure & Algorithm Analysis - Dec 2015

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 with example
i) Degree of tree
ii) Height of tree
iii) Depth of tree(3 marks) 1 (b) What is linked list? Give its applications.(3 marks) 1 (c) Define Graph. List the types Graph with example.(3 marks) 1 (d) What is Asymptotic Notations.(3 marks) 1 (e) Write down the properties of Red-Black trees.(3 marks) 1 (f) What are linear and non-linear data structures.(3 marks) 1 (g) Define minimum spanning tree. List the techniques to compute minimum spanking tree.(2 marks) 2 (a) Write a program to implement Queue ADT using array.(10 marks) 2 (b) Define Binary search tree. Write an algorithm to implement Insertion and Deletion Operation.(10 marks) 3 (a) Write a program to convert INFIX expression into POSTFIX expression.(10 marks) 3 (b) Define AVL tree? Construct AVL tree for following data [ Mention type of rotation for each case]
1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12.(10 marks) 4 (a) Using Prim's and Kruskal's algorithm find minimum spanning tree for the following Graph. (10 marks) 4 (b) Write an algorithm to implement shell sort.(10 marks) 5 (a) Write a program to create singly linked list and display the list.(10 marks) 5 (b) Explain BFS and DFS algorithm with example.(10 marks)

Write short note on any four.

6 (a) B-Tree(5 marks) 6 (b) Red Black Trees(5 marks) 6 (c) Searching Algorithms(5 marks) 6 (d) Sparse Matrix(5 marks) 6 (e) Euclid's algorithm(5 marks) 6 (f) Marge Sort(5 marks)