Data Stracture & Algorithms Sem III (24/5/2012)

 

	Data Stracture & Algorithms Sem III (24/5/2012) (3 Hours)	GN-5382 [Total Marks :- 100]
N.B.	(1) Question No.1 is compulsory. (2) Attempt any four questions from remaining six questions.
1.	(a) What are linear and non-linear data structures?	5
	(b) What are Asymptotic notations?	5
	(c) Why is it necessary to analyze an algoruthm?	5
	(d) What are expression trees?	5
2.	(a) Develop an algorithm to delete a node from the given binary search tree. Consider all cases.	10
	(b) Explain the method of Huffman Encoding. Apply huffman Encoding method for the sentences 'STRUCTURE'.	10
3.	(a) What is a priority Queue? Explain the Insertion and Deletion operations on Priority Queue if its is implemented using Array .	10
	(b) Write any pattern matching algorithm and explain it with suitable example.	10
4.	(a) Explain selection sort and write a program to implement selection sort. Compare it with binary Sort.	10
	(b) Write an algorithm and explain with an example RADIX SORT method.	10
5.	(a) Using Prim's and krushkal's algorithm find Minimum Spanning tree for the following graph. (b) Give an INFIX expression, write a program to convert it to its 'PREFIX' from.	10
		10
6.	(a) Write a program to implement 'QUICK SORT' and comment on its complexity.	10
	(b) Write a program to implement 'Tower of Hanoi' using recursions.	10
7.	Write down short notes on any four : -	20
	(a) Expression and realization of ADT's in Java
	(b) Comparison of sorting algorithms
	(c) Infix, Prefix and Postfix expressions
	(d) Space and time complexity
	(e) Recursion

Also see Data structure & algorithms question papers for December 2011