H.T.
No: Course Code No: 20CS5T01
VISHNU INSTITUTE OF TECHNOLOGY::BHIMAVARAM (AUTONOMOUS)
II B. Tech II Semester (R20) - Regular Examinations, ______
Design and Analysis of Algorithms
(CSE, IT, AI&DS, CS&BS)
Time: 3 Hours Max. Marks: 70M
Note: 1. Answer all the 5 Questions
2. Each Question carries 14 Marks
UNIT – I
1 a Write an algorithm for linear search and analyze the algorithm for its L2 CO1 [7M]
time complexity.
b Write different pseudo code conventions used to represent an algorithm. L1 CO1 [7M]
(OR)
2 a Explain the different asymptotic notations used in algorithm analysis. L3 CO1 [7M]
b Write a recursive algorithm to find the sum of first n integers and Derive L2 CO1 [7M]
its time complexity.
UNIT – II
3 a Apply Merge Sort to sort the list L1 CO2 [7M]
a[1:10]=(31,28,17,65,35,42.,86,25,45,52).
Draw the tree of recursive calls of merge sort, merge functions.
b Derive the worst-case time complexity of Quick Sort. L3 CO2 [7M]
(OR)
4 a Devise an algorithm using Divide and Conquer for the problem of finding L2 CO2 [7M]
the maximum and minimum items in a set of N elements and compare the
number of comparisons required for Divide-and-Conquer and Brute-force
approach.
b State the Defective Chess Board Problem and suggest a solution to solve L2 CO2 [7M]
the problem using Divide-and-Conquer.
UNIT – III
1 of 2
5 a Discuss the Dijkstra’s single source shortest path algorithm and derive its L3 CO3 [7M]
time complexity.
b State Optimal Merge Pattern problem. Find optimal merge pattern for ten L2 CO3 [7M]
files whose record lengths are 28, 32, 12, 5, 84, 53, 91, 35, 3, and 11.
(OR)
6 a Summarize the prim's algorithm to generate a Minimum Spanning Tree L1 CO3 [7M]
and derive a minimum-cost spanning for the given graph using prims
algorithm.
b Solve the following instance of 0/1 KNAPSACK problem using L2 CO3 [7M]
Dynamic programming n = 3, (W1, W2, W3) = (2, 3, 4), (P1, P2, P3) =
(1, 2, 5), and m = 6.
UNIT – IV
7 a Present the dynamic programming solution for all pairs shortest path L2 CO4 [7M]
problem and analyze its time complexity.
b Design a three stage system with device types D1, D2, D3. The costs are L3 CO4 [7M]
$30, $15, $20 respectively. The cost of the system is to be not more than
$105 and the reliability of each device type is 00.9, 0.8 and 0.5
respectively.
(OR)
8 a State the Principle of Optimality. Compare Dynamic Programming with L1 CO4 [7M]
Greedy and Divide-and-Conquer.
b Let X = a,a,b,a,a,b,a,b,a,a and Y = b,a,b,a,a,b,a,b. Find a minimum-cost L2 CO4 [7M]
edit sequence that transforms X and Y.
2 of 2
UNIT – V
9 a What is LC–Search? Discuss LC–Search algorithm. L1 CO5 [7M]
b Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20} L2 CO5 [7M]
and m=35 and draw the portion of the state space tree that is generated
using backtracking.
(OR)
10 a Write an algorithm for finding m-coloring of a graph and explain with an L2 CO5 [7M]
example.
b Generate FIFO branch and bound solution for the given knapsack L3 CO5 [7M]
problem, m = 15, n = 3, (P1, P2, P3) = (10, 6, 8) and (w1, w2, w3) = (10,
12, 3).
*****
1 of 2
