STUPIDSID
1 (a)
With the help of a flow chart. Explain the various steps of algorithm design and analysis process.
8 M
1 (b)
If f1(n) ∈ O(g1(n)) and f2(n) ∈ O(g2(n)) prove that f1(n)+f2(n) ∈ O(max |g(n).g2(n)|)
4 M
1 (c)
Write an algorithm for selection sort and show that the time complexity of this algorithm is quadratic.
8 M
2 (a)
What is divide and conquer method. Show that the worst case efficiency of binary search algorithm is 0 (log n).
10 M
2 (b)
Explain quick sort algorithm. Find the time complexity of quick sort for best case, worst case and average case.
10 M
3 (a)
Write Kruskal's algorithm to construct a minimum spanning tree and show that the time efficiency is O(|∈|log|&isi;|).
8 M
3 (b)
Apply Kruskal's algorithm to find the min spanning tree of the graph.
8 M
3 (c)
Write Dijkstra's algorithm to find single source shortest path.
4 M
4 (a)
Write the dynamic programming algorithm to computer binomial co-efficient and obtain its time complexity.
4 M
4 (b)
Explain Warshall algorithm to find the transitive closure of a directed graph. Apply this algorithm to the graph given below.
8 M
4 (c)
State Floyd's algorithm. Solve all pairs shortest path problem for the given graph using Floyd algorithm.
8 M
5 (a)
Explain decrease and conquer method. With a suitable example.
4 M
5 (b)
Apply the DFS-based algorithm to solve the topological sorting problem for given graph.
-
8 M
5 (c)
State Horspool's algorithm for pattern matching. Apply the same to search for the pattern BARBER in a given text.
8 M
6 (a)
Prove that the classic recursive algorithm for the tower of Hanoi puzzle makes the minimum number of disks moves needed to solve it.
8 M
6 (b)
Write short notes on:
i) Tight lower bound
ii) Trivial lower bound
iii) Information theoretic lower bound.
i) Tight lower bound
ii) Trivial lower bound
iii) Information theoretic lower bound.
12 M
7 (a)
Explain how the TSP problem can be solved, using branch and bound method.
6 M
7 (b)
Explain back-tracking concept and apply the same to n-queens problem
8 M
7 (c)
Solve 8-queens problem for a feasible sequence (6, 4, 7, 1)
6 M
8 (a)
Write short notes on:
i) Hamiltonian problem
ii) M- Colouring.
i) Hamiltonian problem
ii) M- Colouring.
10 M
8 (b)
Explain prefix computation problem and list ranking algorithm, with suitable examples.
10 M
More question papers from Design and Analysis of Algorithms