STUPIDSID
1 (a)
Explain Divide and Conquer strategy. Write control abstraction (general method) for it. List any four examples that can be solved by divide and conquer.
10 M
1 (b)
Explain asymptotic notations. Explain time complexity and space complexity in detail.
10 M
2 (a)
Explain Graph Colouring problem using backtracking. Write algorithm for same.
10 M
2 (b)
Find out single source shortest path for following problem using Dijkstra's Algorithm.
10 M
3 (a)
Find the longest common subsequence from the given two sub-sequences:-
P = {100101101101}
Q = {0110}
P = {100101101101}
Q = {0110}
10 M
3 (b)
Explain 15 puzzle problem using Branch and Bound.
10 M
4 (a)
Sort following numbers using Quicksort algorithm.
65, 70, 75, 80, 85, 60, 55, 50, 45.
Show all passes of execution. Also state the time complexity.
65, 70, 75, 80, 85, 60, 55, 50, 45.
Show all passes of execution. Also state the time complexity.
10 M
4 (b)
Explain and write Knuth-Morris Pratt algorithm. Explain with an example.
10 M
5 (a)
Explain job sequencing with deadlines. Solve the following instance: n=5
(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)
(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)
10 M
5 (b)
Solve the following sum of subset problem using backtracking:
w= {1, 3, 4, 5}, m=8.
Find the possible subsets of 'w' that sum to 'm'.
w= {1, 3, 4, 5}, m=8.
Find the possible subsets of 'w' that sum to 'm'.
10 M
6 (a)
Solve shortest path from source 1 for following graph using dynamic programming.
10 M
6 (b)
Explain travelling Salesperson Problem using branch and bound method.
10 M
Write short notes:-
7 (a)
Differentiate between greedy approach and dynamic programming.
5 M
7 (b)
Optimal Storage On Tapes
5 M
7 (c)
Radix Sort
5 M
7 (d)
Minimum Spanning Tree using Kruskal's algorithm.
5 M
More question papers from Analysis of Algorithms