[Total No. of Questions : 09]
CS/IT 315 (CR)
III/IV B.Tech Degree Examinations, October - November 2015
First Semester
CS/IT
Design & Analysis of Algorithms
Time : 3 hours
Maximum Marks : 70
Answer question No.1 Compulsory
Answer ONE question from each Unit
1. Briefly explain following [7 x 2 = 14M]
a) Algorithm
b) Space Complexity
c) Pseudo Code
d) Binary Search
e) Mention Time Complexity of DFS and BFS
f) Complexity measure
g) Connected components
UNIT - I [1 x 14 = 14M]
2. a) Write the non recursive algorithm for finding the Fibonacci sequence and derive its time complexity.
2. b) Write and explain the control abstraction for Divide and Conquer. (OR)
3. a) List some of the relative advantages and disadvantages of the partition algorithm.
3. b) Write the Quick Sort algorithm? Analyze the time complexity in worst case.
UNIT - II [1 x 14 = 14M]
4. a) Compare Greedy and Divide & Conquer methods with suitable examples for each.
4. b) What is the Principle of Optimality? Explain its significance. (OR)
5. What is a Travelling salesperson's problem and what are its applications? For the travelling sales person algorithm, show that the time complexity is O((n^2).(2^n)) and space complexity is O((n).(2^n)).
UNIT - III [1 x 14 = 14M]
6. a) Explain the Depth First Search algorithm with a suitable example and its applications.
6. b) Write a brief on Bi-connected components. (OR)
7. a) Write a Backtracking algorithm for solving the Knapsack optimization problem using the variable tuple size formulation.
7. b) Obtain a Knapsack instance for which nodes are generated by Backtracking algorithm using a static tree than using a dynamic tree.
UNIT - IV [1 x 14 = 14M]
8. a) Explain the satisfiability problem and write the algorithm for the same.
8. b) Differentiate between NP-Complete and NP-Hard. (OR)
9. a) Describe clique decision problem and write the algorithm for the same.
9. b) Explain the method of reduction to solve TSP problem using Branch and Bound.