STUPIDSID
1(a)
Define big oh, omega and theta notations' for analyzing algorithm. Give at least one example for each.
10 M
1(b)
Write a algorithm for selection sort in ascending order. Show that its complexity is O(n2) and sort the following list 65, 50, 21, 43, 10, 15.
6 M
1(c)
Write the algorithm for sequential search, obtain the time complexity of this algorithm for successful and unsuccessful search in the worst case and best case.
4 M
2(a)
Explain the concept of divide and conquer. Design an algorithm for merge sort and derive time complexity.
10 M
2(b)
Write a algorithm for Quick sort, and sort the following number's 10, 8, 5, 15, 25, 75, 12. Obtain its time complexity.
10 M
3(a)
Obtain the optimal solution for the job sequencing problem with deadline, where n = 4 profit (P1, P2, P3, P4) = (100, 10, 15, 27) and dead lines (d1, d2, d3, d4) = (2, 1, 2, 1).
4 M
3(b)
Explain the concepts of greedy technique for prim's algorithm. Obtain minimum cost spanning tree for the graph whose weight matrix is given below \[\begin{bmatrix}
0 & 3 & \infty & 7 & \infty\\
3 & 0 & 4 & 2 & \infty\\
\infty & 4 & 0 & 5 & 6\\
7 & 2 & 5 & 0 & 4\\
\infty & \infty & 6 & 4 & 0
\end{bmatrix}\]
8 M
3(c)
Write a Kruskal algorithm to find minimum cost spanning tree and obtain spanning tree of the graph shown below:
8 M
4(a)
Write Floyd's algorithm and solve the all pair shortest path problem for the graph shown below :
10 M
4(b)
Write a algorithm for Knapsack problem for dynamic programming and solve the following instance of the knapsack problem,
n = 4, weights (w1, w2, w3, w4) = (2, 1, 3, 2), profit (p1, p2, p3, p4) = (12, 10, 20, 15) Capacity W=5.
n = 4, weights (w1, w2, w3, w4) = (2, 1, 3, 2), profit (p1, p2, p3, p4) = (12, 10, 20, 15) Capacity W=5.
10 M
5(a)
Explain the concept of decrease and conquer method, indicating the three major variations of the same with examples.
6 M
5(b)
Write insertion sort algorithm and obtain its time complexity. Apply insertion sort on these elements: 25, 75, 40, 10, 20.
8 M
5(c)
Write a algorithm to sort by counting method. Obtain its time complexity, sort by count for given data 25, 45, 10, 20, 50, 15.
6 M
6(a)
Explain the lower bound and trivial lower bound arguments.
8 M
6(b)
What is a decision tree? Obtain decision tree to find minimum of three numbers.
6 M
6(c)
Explain the P, NP and NP complete problems.
6 M
7(a)
What is a N-Queen's problem? Give the state space tree for solving 4 Queen problem for at least one solution?
6 M
7(b)
With help of a state space tree solve the following instance of the knapsack problem by the branch and bound algorithm
N=4 weight (w1, w2, w3, w4) = (4, 7, 5, 3)
Profit (p1, p2, p3, p4) = (40, 42, 25, 12)
W=10 capacity knapsack.
N=4 weight (w1, w2, w3, w4) = (4, 7, 5, 3)
Profit (p1, p2, p3, p4) = (40, 42, 25, 12)
W=10 capacity knapsack.
6 M
7(c)
Obtain the optimal solution for the given assignment problem as a matrix shown below using branch and bound method :
8 M
8(a)
What is a prefix computation problem? Give the algorithm for prefix computation which use i) n-processor ii) n/log n
6 M
8(b)
Explain the different types of computational models.
8 M
8(c)
Obtain the maximum speed up when P=10 and for various value of f=(0.5, 0.1, 0.01).
6 M
More question papers from Design and Analysis of Algorithms