Data Structure & Algorithm Analysis - May 2016

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.(2 marks) 1(c) What is recursion? State its advantages and disadvantages.(3 marks) 1(d) Define Asymptotic Notation along with exmaple.(3 marks) 1(e) What is Expression Tree? Give Example.(3 marks) 1(f) What are linear and non-linear data structure?(3 marks) 1(g) What is time Complexity? Determine the Time complexity for the following code :
for (c = 0 {
for (d = 0(3 marks) 2(a) Write a program to implement queue using array.(10 marks) 2(b) Write an algorithm for merge sort and comment on its complexity.(10 marks) 3(a) Define binary search tree. Write algorithm to implement insertion and deletion operation.(10 marks) 3(b) Write a program to crete single link list and display the list.(10 marks) 4(a) What is priority? Give implementation of it.(10 marks) 4(b) Using Prim's and Kruskal's algorithm find minimum spanning tree for the following graph:

Write short note on any four of the following

6(a) Euclid's Algorithm(5 marks) 6(b) Red and Black Trees(5 marks) 6(c) DFS and BFS(5 marks) 6(d) B-Tree(5 marks) 6(e) Radix Sort(5 marks)