Posted Date: 09 May 2016      Posted By:: Krishna Teja Yeluripati    Member Level: Gold  Points: 3 (Rs. 3)

# 2015 B.Tech Computer Science and Engineering B.Tech - CSE - CS315 - Design & Analysis of Algorithms (DAA) - November 2015 - Question Paper - Acharya Nagarjuna University Question paper

 Course: B.Tech Computer Science and Engineering University/board: Acharya Nagarjuna University

Feel comfortable if you are looking for the old question papers of Acharya Nagarjuna University - B.Tech - CSE - CS315 - Design & Analysis of Algorithms (DAA). This is the original question paper of the exam conducted by Acharya Nagarjuna University to III/IV B.Tech - 1st Semester students in November 2015. Feel free to make a copy of this previous paper and use it to prepare for your upcoming exams.

[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 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.

### Related Question Papers:

• Acharya Nagarjuna University, B.A. (Economics, History, Sociology) - II YEAR , MAY 2015 Question Paper (Distance Mode)

• Acharya Nagarjuna University, B.A. (Economics, History, Sociology) - I YEAR , MAY 2015 Question Paper (Distance Mode)

• Acharya Nagarjuna University, B.A. (Economics, Public Administration, Sociology) - III YEAR , May 2015 Question Paper (Distance Mode)

• Acharya Nagarjuna University, B.A. (Economics, Public Administration, Sociology) - II YEAR , May 2015 Question Paper (Distance Mode)

• Acharya Nagarjuna University, B.A. (Economics, Public Administration, Sociology) - I YEAR , May 2015 Question Paper (Distance Mode)

• ### Categories

Submit Previous Years University Question Papers and make money from adsense revenue sharing program

Are you preparing for a university examination? Download model question papers and practise before you write the exam.

 Join Group

Top Contributors
TodayLast 7 Daysmore...

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email
• ### Online Members

himanshuchouhan
Sankalan Bhattacharya
Saikat Majhi
More...