Data Structure & Algorithm Analysis - May 2014

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 stack? Give application of it.(2 marks) 1 (b) What is time complexity? Determine time complexity of following code:-
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x=x+1;(3 marks) 1 (c) Explain with e.g. :-
(i) Complete binary tree
(ii) Degree of tree
(iii) Height of tree
(3 marks) 1 (d) Explain linked list with its various types.(3 marks) 1 (e) Define double ended queue and give its applications.(3 marks) 1 (f) Define asympotic notation along with example.(3 marks) 1 (g) Define Graph List its types with example.(3 marks) 2 (a) Find the shorted path using Dijkstra's algorithm
(10 marks) 2 (b) Implement quick sort with example and find its complexity(10 marks) 3 (a) Explain BFS and DFS with algorithm and proper example.(10 marks) 3 (b) What is linked list? Write 'C' function for insertion of 'n' elements.(10 marks) 4 (a) Traverse the following binary tree into preorder, inorder, postorder by giving its algorithm
(10 marks) 4 (b) Using Prim's algorithm find minimum spanning tree of a graph with example. Write algorithm of it.(10 marks) 5 (a) What is priority queue? Give implementation of it.(10 marks) 5 (b) What is graph? Give representation of graph with example. State applications of it.(10 marks)

Solve any four :-

6 (a) AVL Tree(5 marks) 6 (b) Euclids algorithm(5 marks) 6 (c) Sparse matrix(5 marks) 6 (d) B-Tree(5 marks) 6 (e) Circular linked list.(5 marks)