STUPIDSID
1(a)
Explain different Asymptotic notations and all cases of Master method. Solve following Recurrences using Master method.
1) T(n) =2T(n/2)+n3
2) T(n)=3T(n/4) nlog2n
3) T(n) = 2T(n/2) + n/logn
4) T(n) = 16T(n/4) + n!
5) T(n) = 0.5T (n/2) + 1/n
1) T(n) =2T(n/2)+n3
2) T(n)=3T(n/4) nlog2n
3) T(n) = 2T(n/2) + n/logn
4) T(n) = 16T(n/4) + n!
5) T(n) = 0.5T (n/2) + 1/n
10 M
1(b)
Explain Johnson's all pair shortest path algorithm with example.
10 M
2(a)
What is binomial heap? Expalain it's properties. Expalin the operations that can be carried out on binomial heap with example.
12 M
2(b)
Explain Graham's algorithm to find convex hull.
8 M
3(a)
What is red-black tree? Show the red-black tree that results from the successive insertion of the following keys 9,
8,
7,
3,
5,
2 and the successive deletion of the following keys 2,
5,
3,
7,
8,
9
8,
7,
3,
5,
2 and the successive deletion of the following keys 2,
5,
3,
7,
8,
9
10 M
3(b)
Find the maximum flow using Ford Flukerson Algorithm.
!mage
!mage
10 M
4(a)
Explain Cutting Rod problem. Given a table of prices pi determine the maximum revenue rn obtainable by cutting the rod.
| Len | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Price | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 |
8 M
4(b)
Find an optimal parentesization of a matrix-chain product whose sequene of dimensions is <30,
35,
15,
5,
10,
20,
25>
35,
15,
5,
10,
20,
25>
12 M
5(a)
Solve the following linear program using simplex method. Maximize 5x1+3x2 Subject to the condition
X1+X2≤2
5X1+2X2≤10
3X1+8X2≤12
X1, X2≥0
X1+X2≤2
5X1+2X2≤10
3X1+8X2≤12
X1, X2≥0
12 M
5(b)
Explain Closest Pair of Points using divide and conquer.
8 M
6(a)
Explain maximum bipartite matching with example.
10 M
6(b)
Explain insertion and deletion in B-tree with a example.
10 M
More question papers from Advanced Algorithm