## Data Structure & Algorithm Analysis - Dec 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)** Define Algorithm and write its properties.(3 marks)
**1(b)** Write properties of B-Tree.(3 marks)
**1(c)** Define minimum spanning trees with examples.(3 marks)
**1(d)** What is Queue ADT? Mention its operations.(3 marks)
**1(e)** What is linked list? Explain types of linked list.(3 marks)
**1(f)** Define Recursion? State its advantages and disadvantages.(3 marks)
**1(g)** Explain linear and non-linear data structures.(2 marks)
**2(a)** Write a program to implement queue using arrays.(10 marks)
**2(b)** Write an algorithm for insertion and traversal in a circular linked list.(10 marks)
**3(a)** Write a program to convert INFIX expression into POSTFIX expression.(10 marks)
**3(b)** Wriet an algorithm to implement Heap-sort. Also comment on its complexity.(10 marks)
**4(a)** Define AVL Tree? Construct AVL Tree for the following data (Mention type of rotation for each case) 10,40,30,20,70,50,45.(10 marks)
**4(b)** Write a program to implement Priority Queue.(10 marks)
**5(a)** Explain BFS and DFS algorithm with examples.(10 marks)
**5(b)** What is Binary Search-Tree? Construct the Binary Search Tree for the following set of data: 14, 10, 1, 20, 17, 24, 18, 12, 15, 11, 4, 6.(10 marks)

### Write a short note any four Q6..(a,b,c,d,e,f)

**6(a)** Red-black Trees(5 marks)
**6(b)** Searching Algorithms(5 marks)
**6(c)** Adjacency list and Adjacency matrix(5 marks)
**6(d)** Euclid's Algorithm(5 marks)
**6(e)** Expression Trees(5 marks)
**6(f)** Asymptotic Notations.(5 marks)