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(n

^{2}) 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 (P

_{1}, P_{2}, P_{3}, P_{4}) = (100, 10, 15, 27) and dead lines (d_{1}, d_{2}, d_{3}, d_{4}) = (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 (w

n = 4, weights (w

_{1}, w_{2}, w_{3}, w_{4}) = (2, 1, 3, 2), profit (p_{1}, p_{2}, p_{3}, p_{4}) = (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 (w

Profit (p

W=10 capacity knapsack.

N=4 weight (w

_{1}, w_{2}, w_{3}, w_{4}) = (4, 7, 5, 3)Profit (p

_{1}, p_{2}, p_{3}, p_{4}) = (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