Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Note:
i) Answer any five questions.
ii) All questions carry equal marks.
iii) In case of any doubt or dispute the English version question should be treated as final.
a) Define the algorithm and its properties. Explain asymptotic notations for analyzing algorithm with example and Show that 10n² + 5 ∈ O(n²). (7)
b) Find the upper bound of recurrences given below by substitution method (7)
i) 2T(n/2) + n
ii) T(n/2) + 1
a) Explain the Brute Force method. Write an algorithm for selection sort and apply it to the list of items 66, 11, 33, 55, 44, 22, 77. Also computer time complexity for the average case. (7)
b) Design Binary Search algorithm and derive its complexity by applying Master Theorem. (7)
a) Discuss how to find maximum and minimum elements in an array recursively? Trace the same for the following data sets 65, 70, 75, 80, 85, 60, 55, 50. Also derive the worst-case complexity. (7)
b) Briefly explain Strassen's matrix multiplication. Apply it to multiply the following matrices. Explain how this method is better than the direct multiplication method. (7)
[1 0 2] [2 1 0]
[4 1 1] x [3 2 0]
[0 1 3] [2 0 1]
a) Explain the concept of Divide & Conquer. Design an algorithm for Merge Sort and derive its time complexity. (7)
b) Explain the concept of the Greedy Technique for Prim's Algorithm, determine the minimum cost spanning tree of the graph of figure: (7)
a) Explain the dynamic programming. Compute the shortest path from vertex 1 to all other vertices using a dynamic programming approach. (7)
b) Using Floyd's algorithm, find all pairs of shortest path for the graph in the figure given below: (7)
a) Explain Backtracking Concept. Construct the state-space tree for solving 4-Queen's problem using backtracking. (7)
b) How Branch and Bound algorithm is different from Backtracking? Solve the following instance of the Knapsack Problem by the Branch and Bound method. Given Knapsack capacity = 10. (7)
| Item | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Weight | 4 | 7 | 5 | 3 |
| Value | 40 | 42 | 15 | 12 |
a) What is a Decision Tree? Give a decision tree for 3 elements selection sort for arranging the items in ascending order and estimate its lower bound. (7)
b) Design a BFS algorithm to check the connectivity of a given graph. Explain with an example. (7)
Explain any four of the followings with examples: (14)
i) Class P
ii) Class NP
iii) NP-Complete Problem
iv) NP-Hard Problem
v) Graph Coloring
vi) Hamilton Cycle