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)