ANALYSIS OF ALGORITHMS (AOA) MAY 2012 COMPUTER AND SCIENCE SEMESTER 4

ANALYSIS OF ALGORITHMS (AOA) MAY 2012  COMPUTER AND SCIENCE SEMESTER 4

Con. 4608-12.                                                                                             GN-8795
                                                   (3 Hours)                                         [Total Marks : 100]

N.B. (1) Question No.1 is compulsory.
        (2) Attempt any four questions from remaining six questions.
        (3) Assumption made should be clearly stated.
        (4) Assume suitable data whenever required.

1. (a)	Explain Big-oh, Omega and Theta Notations with help of example. How do we	10
	Analyse and measure time and space complexity of algorithms ?
(b)	Construct the Optimal Binary Search Tree for the identifier set	10
	(a1, a2, a3, a4) = (cout, float, if, while).
2. (a)	Explain Flow Shop Scheduling with help of suitable examples.	10
(b)	Write down Prim's Algorithm and solve following problem :-	10

3. (a)	Write Randomized Quick Sort Algorithm and explain with help of example.	10
(b)	Explain 0/1 Knapsack problem using Branch and Bound Method.	10
4. (a)	Describe Traveling Salesperson problem. Explain how to solve using Branch	10
	and Bound Method.
(b)	Write algorithm of Sum of Subsets. Solve following problem and draw portion	10
	of state space tree.
	w={5, 7, 10, 12, 15, 18, 20} and m=35. Find all possible subsets of w that sum to m.
5. (a)	Explain Strassen's Matrix multiplication and derived its time complexity.	10
(b)	Write down Knuth-Morris-Pratt Algorithm.	10
6. (a)	Write algorithm of job Sequencing with Deadlines. Solve the following problem	10
	n = 5.
	(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and
	(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3).
(b)	Explain Hamiltonian Cycles Algorithm, and draw static space tree.	10
7.	Write short notes on (Any four) :-	20
	(a) Tries
	(b) Randomized Algorithm
	(c) N-Queens Problem
	(d) Bellman and Ford Algorithm
	(e) Optimal Storage on Tapes.