Code: 13A05402
R13
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech II Year II Semester Examinations, May - 2015
--- Content provided by FirstRanker.com ---
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, IT)
Time: 3 Hours Max. Marks: 75
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A.
--- Content provided by FirstRanker.com ---
Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks.
PART - A (25 Marks)
-
- Define algorithm. What are the characteristics of an algorithm? [2M]
- Write the control abstraction for Divide-and-Conquer strategy. [3M]
- What is principle of optimality? [2M]
- Define dynamic programming. [3M]
- Write any two differences between Backtracking and Branch and Bound. [2M]
- Define Graph Coloring. [3M]
- What is meant by NP-Hard? [2M]
- What is meant by NP-Completeness? [3M]
- Define Approximation algorithm. [2M]
- Define Biconnected graph. [3M]
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
PART - B (50 Marks)
(Answer all five units, choosing one question from each unit)
UNIT - I
-
Explain the algorithm for finding the maximum and minimum problem using Divide and Conquer technique. [10M]
OR
--- Content provided by FirstRanker.com ---
-
Explain the algorithm for finding the Quick Sort problem using Divide and Conquer technique. [10M]
UNIT - II
-
Write the algorithm for Single source shortest path problem with example. [10M]
--- Content provided by FirstRanker.com ---
OR
-
Explain about matrix chain multiplication with example. [10M]
--- Content provided by FirstRanker.com ---
UNIT - III
-
Explain Graph traversals techniques. [10M]
OR
-
Write and explain the algorithm for finding articulation points. [10M]
--- Content provided by FirstRanker.com ---
UNIT - IV
-
Explain the algorithm for sum of subsets problem. [10M]
OR
-
Explain the algorithm for graph coloring problem. [10M]
--- Content provided by FirstRanker.com ---
UNIT - V
-
Explain about NP-Hard and NP-Complete problems. [10M]
OR
-
Explain approximation algorithms. [10M]
--- Content provided by FirstRanker.com ---
---oo0oo---
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU M.Tech 1st Semester Last 10 Years 2010-2020 Previous Question Papers|| Punjab Technical University
--- Content provided by FirstRanker.com ---