STUPIDSID
1 (a)
Explain all asymptotic notations used in algorithm analysis.
7 M
1 (b)
Using step count method analyze the time complexity when two m*n matrices
are added.
7 M
2 (a)
What is divide and conquer technique? Apply this method to find multiplication
of integers 2101 and 1130.
7 M
2 (b)
Sort the letter of the word "EXAMPLE" in alphabetical order using insertion
Sort.
7 M
2 (c)
Explain merge sort problem using divide and conquer technique. Give an
Example
7 M
3 (a)
Devise an algorithm to make a change for 1655 using the greedy strategy. The
coins available are {1000, 500, 100, 50, 20, 10, 5}.
7 M
3 (b)
What is an amortized analysis? Explain potential method of amortized analysis
using suitable example.
7 M
3 (c)
Give the algorithm for Depth First Search of a Graph. Also define 'Articulation Point' of the graph and explain how to find it.
7 M
3 (d)
Write the Quick sort algorithm. Trace the same on data set: 5, 3,1,9,8,2,4,7.
7 M
4 (a)
Solve the following knapsack problem with the given capacity W=5 using
dynamic programming.
| Item | Weight | Value |
| 1 | 2 | $12 |
| 2 | 1 | $10 |
| 3 | 3 | $20 |
| 4 | 2 | $15 |
7 M
4 (b)
Using greedy algorithm find an optimal schedule for following jobs with n=5
profits: (P1,P2,P3,P4,P5) = (3,5,18,20,38) and deadline :(d1,d2,d3,d4,d5) =
(1,3,3,4,1)
7 M
4 (c)
Write Dijkstra's algorithm and apply the same to find single source shortest path problem for the following graph taking vertex "a" as a source.
7 M
4 (d)
Using algorithm determine an Longest Common Sequence of S1="abbacdcba" S2="bcdbbcaac" (use dynamic programming).
7 M
5 (a)
What is the central principle of back tracking? Taking n-queens problem as an
example, explain the solution process.
7 M
5 (b)
What is polynomially Turing reducible problem? Explain with example how
problem A can be polynomially Turing reduced to problem B.
7 M
5 (c)
Explain with example how backtracking algorithm is useful in solving Hamilton
cycle problem.
7 M
5 (d)
With an example, explain how the branch and bound technique is used to solve
0/1 knapsack problem.
7 M
More question papers from Design And Analysis Of Algorithm