## 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)