B.E.
5th SEMENSTER (CSE)
Examination - December, 2009
ANALYSIS
AND DESIGN OF ALGORITHMS
Paper : CSE-305-E
Note
: Attempt any five questions. All questions carry equal marks.
1. (a) What is recurrence relation ?
Explain master method for solving recurrences.
10
(b) Explain Union
algorithm with weighted rule 10
2. (a) Explain the algorithm which runs
in O(n) time when the list is already sorted. Derive average and worst case
complexity for the same.
10
(b) Explain heap sort
algorithm and compute its complexity. 10
3. (a) Find the solution for following
fractional Knapsack problem using greedy method :
10
n = 3 m=50
wi = (10, 20, 30) pi = ( 60, 100, 120)
(b) Explain
Kruskal’s algorithm to find the minimum
spanning tree from a graph with example and derive its time complexity 10
4. (a) Explain job sequencing with
deadlines. 10
(b) Find the minimum spanning tree
using Prim’s algorithm for following graph:
10
1. (a) Explain backtracking . Write
algorithm for n queens problem and analyze the time complexity of the
same.
10
(b) Consider the knapsack
instance :
n =4, Wi = (2, 4, 6, 9 )
Pi = ( 10, 10, 12, 18 ) m =15.
Using dynamic approach
find the solution for this instance of 0-1 knapsack problem. 10
2. (a) Differentiate Greedy and dynamic
approach hence differentiate fractional and 0-1 Knapsack problem.
10
(b) Explain shortest path
algorithm.
10
3. Explain LC branch and bound
technique. Find the reduced cost matrix and draw the state space tree for
travelling salesperson problem having the following cost matrix. 20
∞ 20 30 10 11
15 ∞ 16 04 02
03 05 ∞ 02 04
19 06 18 ∞ 03
16 04 07 16 ∞
4. Write short notes on :
(i)
Strassen’s
matrix multiplication 10
(ii)
Cook’s
theorem.
10
No comments:
Post a Comment