Data Structure & Algorithm Analysis - May 2013

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 linear and non-linear data structure with example.(5 marks) 1 (b) What is recursion? State its advantages and disadvantages.(5 marks) 1 (c) What is AVL tree? Give example.(5 marks) 1 (d) Explain Abstract data type.(5 marks) 2 (a) Write any Pattern Matching Algorithm and explain it with suitable example.(10 marks) 2 (b) Write a program to implement queue using array.(10 marks) 3 (a) Write a program to search an element in an array using binary search technique.(10 marks) 3 (b) Write algorithm for heap sort and explain Descending heap with suitable example.(10 marks) 4 (a) Hash the following in a table of size 12. Use any two collision resolution technique.
98, 20, 94, 27, 67, 99, 41, 0, 4, 17, 2, 15.(10 marks) 4 (b) Write a program to implement a stack ADT using linked list.(10 marks) 5 (a) Write and explain QUICK SORT algorithm with suitable example.(10 marks) 5 (b) Write an algorithm to traverse a graph using :-
(i) Breadth first search
(ii) Depth first search (10 marks) 6 (a) Define Binary Tree. Write an algorithm to implement INSERTION and DELETION operation.(10 marks) 6 (b) What is Doubly Linked List? Write an algorithm to implement following operations :-
(i) Insertion (All Cases)
(ii) Traversal (Forward and Backward)(10 marks)

Write short notes on (any four)

7 (a) Shortest Path Algorithm(5 marks) 7 (b) Priority and Circular Queue (5 marks) 7 (c) Red and Black Tree(5 marks) 7 (d) Pattern Matching(5 marks) 7 (e) Expression Tree.(5 marks)