Data Structure & Algorithm Analysis - Dec 2012

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) Write an algorithm for Binary search method with example.(5 marks) 1(b) Explain Asymptotic notations and write the properties of asymptotic notations.(5 marks) 1(c) What are linear and non-linear data structures?(5 marks) 1(d) What is a vector? Explain any four functions.(5 marks) 2(a) Define Binary Tree. Write an algorithm to implement different tree traversal techniques.(10 marks) 2(b) Write a program to create a singly linked list and display the list.(10 marks) 3(a) Write an algorithm for merge sort and comment on its complexity.(10 marks) 3(b) Hash the following in a table of size 11. Use any two collision resolution techniques.
99 67 41 0 17 2 98 20 94 27(10 marks) 4(a) Write a program to implement queue using array.(10 marks) 4(b) Explain Huffman algorithm. Construct Huffman tree for MAHARASHTRA with its optimal code.(10 marks) 5(a) Write an algorithm to traverse a graph using :
i) Breadth first search
ii) Depth first search(10 marks) 5(b) Write an ADT for stack and implement it using array. The ADT should support the following operations.
i)Create
ii)Push
iii)Pop
iv)Display(10 marks) 6(a) Write a program to implement Quick sort and show the steps to sort the following elements by Quick sort method:-
19, 27, 5, 9, 86, 45(10 marks) 6(b) What is a Doubly linked list? Write an algorithm to implement to following operations with DLL :
1.Insertion (All cases)
2.Traverse (Forward and backward)(10 marks)

Write short notes on any four of the following:-

7(a) Pattern Matching(5 marks) 7(b) Expression tree(5 marks) 7(c) Red and Black trees(5 marks) 7(d) Shortest path algorithm(5 marks) 7(e) Priority and circular queue(5 marks) 7(f) Selection sort(5 marks)