Data Structure & Algorithms (December 2012)

	Data Structure & Algorithms  (3 Hours)    KR-3353  [Total Marks : 100]
N.B.:	(1) Question No. 1 is compulsory. (2) Attempt any four questions out of remaining six questions.
1.	(a) Write an algorithm for binary search method with example.	5
	(b) Explain Asympotic notations and write the properties of asympotic notations.	5
	(c) What are linear and non-linear data structures?	5
	(d) What is a vector? Expalin any four functions.	5
2.	(a) Define Binary Tree. Write on algorithm to implement different tree traversal techniques.	10
	(b) Write a program to create singly linked list and dispaly the list.	10
3.	(a) Write an algorithm for merge sort and comment on its complexity.	10
	(b) Hash the following in a table of size 11. Use any two collision resolution techniques.	10
	99 67 41 0 17 2 98 20 94 27.
4.	(a) Write a program to implement queue using array.	10
	(b) Explain Huffman Algortithm. Construct Huffman tree for "MAHARASHTRA" with its optimal code.	10
5.	(a)Write an algortithm to traverse a graph using -	10
	(i) Breadth first search.
	(ii) Depth first search.
	(b) Write an ADT for Stack. And implement it using array. The ADT should support the following operations.	10
	(i) Create
	(ii) Push
	(iii) POP
	(iv) Display
6.	(a) Write a program to implement Quick sort and show the steps to sort the following element       by Quick sort method :-	10
	19 27 5 9 86 45
	(b) What is Doubly Linked List? Write an algorithm to implement following operations with DLL	10
	(i) Insertion (All Cases)
	(ii) Traverse (Forward and Backward)
7.	Write short note on (Any Four) :-	20
	(a) Pattern Matching
	(b) Expression Tree
	(c) Red and Black Trees
	(d) Shortest Path Algorithm
	(e) Priority and Circular Queue
	(f) Selection Sort

Also see Data structure & algorithms question papers for May 2012