JNTU Kakinada B-Tech 3-2 RT32054 I DESIGN AND ANALYSIS OF ALGORITHMS R13 April 2018 Question Paper

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) What are the four distinct areas of study of algorithm? [4M]
b) Is quick sort a stable sorting method? Justify. [3M]
c) What is meant by ?ordering paradi gm?? Give an example problem. How it is
different with ?subset paradigm ? of the greedy technique.
[4M]
d) What is purging or dominance rule. How it is applicable. [3M]
e) Define state space and state space tree. [4M]
f) Describe about Bounding with suitable example. [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+??+a
1
n+a
0
and a
m>
0,then f(n)=O(n
m
). [4M]
b) Write a recursive algorithm to find the sum of first n integers and Derive its time
complexity.
[8M]
c) Mention the important advantages and disadvantages of using randomized
algorithms.
[4M]
3 a) Can we say that the time for Merge Sort is O(n log n).What is its worst and best
time of procedure for Merge Sort.
[3M]
b) Write recursive binary search algorithm with an example and analyze time
complexity. List the applications of binary search.
[8M]
c) Describe the control abstraction for divide and conquer. [5M]
4 a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution
to the knapsack instance n=7,m=15 , (p1 ,p2?.,p7)= (10,5,15,7,6,18,3),and ( w 1,w2, ?w 7 ) =(2,3,5,7,1,4,1).
[8M]
b) Apply greedy algorithm to generate single-source shortest path with an example
graph. Mention its time complexity.
[8M]
5 a) Write about Dynamic Programming General method. [6M]
b) Describe the algorithm to find minimum-cost binary search tree. Show that the
computing time of function OBST is O (n
2
).
[10M]
6 a) Mention an algorithm that Presents a recursive formulation of the backtracking
technique.
[8M]
b) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35
and draw the portion of the state space tree that is generated.
[8M]
7 a) Draw the portion of the state space tree generated by LCBB for the knapsack
instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and
m=12.
[8M]
b) Apply branch and bound algorithm to solve the travelling salesman problem with
an example.
[8M]
*****
R13
SET – 2

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) What are the four distinct areas of study of algorithm? [4M]
b) Is quick sort a stable sorting method? Justify. [3M]
c) What is meant by ?ordering paradi gm?? Give an example problem. How it is
different with ?subset paradigm ? of the greedy technique.
[4M]
d) What is purging or dominance rule. How it is applicable. [3M]
e) Define state space and state space tree. [4M]
f) Describe about Bounding with suitable example. [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+??+a
1
n+a
0
and a
m>
0,then f(n)=O(n
m
). [4M]
b) Write a recursive algorithm to find the sum of first n integers and Derive its time
complexity.
[8M]
c) Mention the important advantages and disadvantages of using randomized
algorithms.
[4M]
3 a) Can we say that the time for Merge Sort is O(n log n).What is its worst and best
time of procedure for Merge Sort.
[3M]
b) Write recursive binary search algorithm with an example and analyze time
complexity. List the applications of binary search.
[8M]
c) Describe the control abstraction for divide and conquer. [5M]
4 a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution
to the knapsack instance n=7,m=15 , (p1 ,p2?.,p7)= (10,5,15,7,6,18,3),and ( w 1,w2, ?w 7 ) =(2,3,5,7,1,4,1).
[8M]
b) Apply greedy algorithm to generate single-source shortest path with an example
graph. Mention its time complexity.
[8M]
5 a) Write about Dynamic Programming General method. [6M]
b) Describe the algorithm to find minimum-cost binary search tree. Show that the
computing time of function OBST is O (n
2
).
[10M]
6 a) Mention an algorithm that Presents a recursive formulation of the backtracking
technique.
[8M]
b) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35
and draw the portion of the state space tree that is generated.
[8M]
7 a) Draw the portion of the state space tree generated by LCBB for the knapsack
instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and
m=12.
[8M]
b) Apply branch and bound algorithm to solve the travelling salesman problem with
an example.
[8M]
*****
R13
SET – 2

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) List out the criteria?s of an algorithm. [4M]
b) Mention the advantages and disadvantages of binary search. [3M]
c) Represent a high-level description of job sequencing algorithm. [4M]
d) List the features of dynamic programming. [3M]
e) Define chromatic number of a graph and planar graph. [4M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Show that the following equalities are incorrect with suitable notations
i)10n
2
+9=O(n) ii) n
2
logn=O(n
2
)[4M]
b) Implement an algorithm to generate Fibonacci number sequence and determine the
time complexity of the algorithm using the frequency method.
[8M]
c) Write about three popular methods to arrive at amortized costs for operations with
example.
[4M]
3 a) What is stable sorting method? Is merge sort a stable sorting method? Justify. [3M]
b) Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show
its computing time is O(n log n).
[8M]
c) Define internal and external nodes of binary decision tree. Draw the binary decision
tree for binary search with n=14.
[5M]
4 a) Describe the greedy method control abstraction for the subset paradigm. [8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using prim?s algorithm.

[8M]
5 a) Describe the Travelling sales person problem and discuss how to solve it using
dynamic programming.
[8M]
b) Design a three stage system with device types D
1
, D2, D3. The costs are $30, $15, $20
respectively. The cost of the system is to be no more than $105.the reliability of each
device type is 00.9, 0.8and 0.5 respectively.
1 of 2
[8M]
R13
SET – 3

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) What are the four distinct areas of study of algorithm? [4M]
b) Is quick sort a stable sorting method? Justify. [3M]
c) What is meant by ?ordering paradi gm?? Give an example problem. How it is
different with ?subset paradigm ? of the greedy technique.
[4M]
d) What is purging or dominance rule. How it is applicable. [3M]
e) Define state space and state space tree. [4M]
f) Describe about Bounding with suitable example. [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+??+a
1
n+a
0
and a
m>
0,then f(n)=O(n
m
). [4M]
b) Write a recursive algorithm to find the sum of first n integers and Derive its time
complexity.
[8M]
c) Mention the important advantages and disadvantages of using randomized
algorithms.
[4M]
3 a) Can we say that the time for Merge Sort is O(n log n).What is its worst and best
time of procedure for Merge Sort.
[3M]
b) Write recursive binary search algorithm with an example and analyze time
complexity. List the applications of binary search.
[8M]
c) Describe the control abstraction for divide and conquer. [5M]
4 a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution
to the knapsack instance n=7,m=15 , (p1 ,p2?.,p7)= (10,5,15,7,6,18,3),and ( w 1,w2, ?w 7 ) =(2,3,5,7,1,4,1).
[8M]
b) Apply greedy algorithm to generate single-source shortest path with an example
graph. Mention its time complexity.
[8M]
5 a) Write about Dynamic Programming General method. [6M]
b) Describe the algorithm to find minimum-cost binary search tree. Show that the
computing time of function OBST is O (n
2
).
[10M]
6 a) Mention an algorithm that Presents a recursive formulation of the backtracking
technique.
[8M]
b) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35
and draw the portion of the state space tree that is generated.
[8M]
7 a) Draw the portion of the state space tree generated by LCBB for the knapsack
instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and
m=12.
[8M]
b) Apply branch and bound algorithm to solve the travelling salesman problem with
an example.
[8M]
*****
R13
SET – 2

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) List out the criteria?s of an algorithm. [4M]
b) Mention the advantages and disadvantages of binary search. [3M]
c) Represent a high-level description of job sequencing algorithm. [4M]
d) List the features of dynamic programming. [3M]
e) Define chromatic number of a graph and planar graph. [4M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Show that the following equalities are incorrect with suitable notations
i)10n
2
+9=O(n) ii) n
2
logn=O(n
2
)[4M]
b) Implement an algorithm to generate Fibonacci number sequence and determine the
time complexity of the algorithm using the frequency method.
[8M]
c) Write about three popular methods to arrive at amortized costs for operations with
example.
[4M]
3 a) What is stable sorting method? Is merge sort a stable sorting method? Justify. [3M]
b) Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show
its computing time is O(n log n).
[8M]
c) Define internal and external nodes of binary decision tree. Draw the binary decision
tree for binary search with n=14.
[5M]
4 a) Describe the greedy method control abstraction for the subset paradigm. [8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using prim?s algorithm.

[8M]
5 a) Describe the Travelling sales person problem and discuss how to solve it using
dynamic programming.
[8M]
b) Design a three stage system with device types D
1
, D2, D3. The costs are $30, $15, $20
respectively. The cost of the system is to be no more than $105.the reliability of each
device type is 00.9, 0.8and 0.5 respectively.
1 of 2
[8M]
R13
SET – 3

Code No: RT32054

6 a) Describe general iterative backtracking algorithm. [8M]
b) Write a backtracking algorithm to solve sum of subsets problem with m=35,
w= {20, 18, 15, 12, 10, 7, 5} to the variable tuple size formulation.
[8M]
7 a) Describe about Control Abstractions for LC-search. [8M]
b) Draw the portion of the state space tree generated by LCBB for the knapsack instance:
n=5,(p1,p2,p3,p4,p5)=(w1,w2,w3,w4,w5)=(4,4,5,8,9), and m=15.
[8M]

*****

2 of 2
R13
SET – 3

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) What are the four distinct areas of study of algorithm? [4M]
b) Is quick sort a stable sorting method? Justify. [3M]
c) What is meant by ?ordering paradi gm?? Give an example problem. How it is
different with ?subset paradigm ? of the greedy technique.
[4M]
d) What is purging or dominance rule. How it is applicable. [3M]
e) Define state space and state space tree. [4M]
f) Describe about Bounding with suitable example. [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+??+a
1
n+a
0
and a
m>
0,then f(n)=O(n
m
). [4M]
b) Write a recursive algorithm to find the sum of first n integers and Derive its time
complexity.
[8M]
c) Mention the important advantages and disadvantages of using randomized
algorithms.
[4M]
3 a) Can we say that the time for Merge Sort is O(n log n).What is its worst and best
time of procedure for Merge Sort.
[3M]
b) Write recursive binary search algorithm with an example and analyze time
complexity. List the applications of binary search.
[8M]
c) Describe the control abstraction for divide and conquer. [5M]
4 a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution
to the knapsack instance n=7,m=15 , (p1 ,p2?.,p7)= (10,5,15,7,6,18,3),and ( w 1,w2, ?w 7 ) =(2,3,5,7,1,4,1).
[8M]
b) Apply greedy algorithm to generate single-source shortest path with an example
graph. Mention its time complexity.
[8M]
5 a) Write about Dynamic Programming General method. [6M]
b) Describe the algorithm to find minimum-cost binary search tree. Show that the
computing time of function OBST is O (n
2
).
[10M]
6 a) Mention an algorithm that Presents a recursive formulation of the backtracking
technique.
[8M]
b) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35
and draw the portion of the state space tree that is generated.
[8M]
7 a) Draw the portion of the state space tree generated by LCBB for the knapsack
instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and
m=12.
[8M]
b) Apply branch and bound algorithm to solve the travelling salesman problem with
an example.
[8M]
*****
R13
SET – 2

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) List out the criteria?s of an algorithm. [4M]
b) Mention the advantages and disadvantages of binary search. [3M]
c) Represent a high-level description of job sequencing algorithm. [4M]
d) List the features of dynamic programming. [3M]
e) Define chromatic number of a graph and planar graph. [4M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Show that the following equalities are incorrect with suitable notations
i)10n
2
+9=O(n) ii) n
2
logn=O(n
2
)[4M]
b) Implement an algorithm to generate Fibonacci number sequence and determine the
time complexity of the algorithm using the frequency method.
[8M]
c) Write about three popular methods to arrive at amortized costs for operations with
example.
[4M]
3 a) What is stable sorting method? Is merge sort a stable sorting method? Justify. [3M]
b) Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show
its computing time is O(n log n).
[8M]
c) Define internal and external nodes of binary decision tree. Draw the binary decision
tree for binary search with n=14.
[5M]
4 a) Describe the greedy method control abstraction for the subset paradigm. [8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using prim?s algorithm.

[8M]
5 a) Describe the Travelling sales person problem and discuss how to solve it using
dynamic programming.
[8M]
b) Design a three stage system with device types D
1
, D2, D3. The costs are $30, $15, $20
respectively. The cost of the system is to be no more than $105.the reliability of each
device type is 00.9, 0.8and 0.5 respectively.
1 of 2
[8M]
R13
SET – 3

Code No: RT32054

6 a) Describe general iterative backtracking algorithm. [8M]
b) Write a backtracking algorithm to solve sum of subsets problem with m=35,
w= {20, 18, 15, 12, 10, 7, 5} to the variable tuple size formulation.
[8M]
7 a) Describe about Control Abstractions for LC-search. [8M]
b) Draw the portion of the state space tree generated by LCBB for the knapsack instance:
n=5,(p1,p2,p3,p4,p5)=(w1,w2,w3,w4,w5)=(4,4,5,8,9), and m=15.
[8M]

*****

2 of 2
R13
SET – 3

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Define Little Oh notation with example. [3M]
b) Describe the time complexity of Divide And Conquer in the recurrence form. [4M]
c) What is knapsack problem? State knapsack problem formally. [4M]
d) Distinguish Greedy method and Dynamic Programming. [3M]
e) Denote live node and dead node with example. [4M]
f) Compare LC and FIFO brand- and-bound. [4M]
PART ?B
2 a) Write a recursive algorithm to solve Towers of Hanoi problem with an example. [4M]
b) Describe about probabilistic analysis in detail. [8M]
c) Implement iterative function for sum of array elements and find the time complexity
use the increment count method.
[4M]
3 a) Why is it necessary to have the auxiliary array b[low: high] in function Merge? [3M]
b) Apply Merge Sort to sort the list a[1:10]=(31,28,17,65,35,42.,86,25,45,52). Draw the
tree of recursive calls of merge sort, merge functions.
[8M]
c) Write iterative binary search algorithm with example.
[5M]
4 a) Use the greedy algorithm for sequencing unit time jobs with deadlines and profits to
generate the solution when n= 7,( p1,p2,?p7 )=( 3,5,20,18 ,1,6,30) ,and ( d1,d2,?,d7)=(1,3,4,3,2,1,2).
[8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using kruskal?s algorithm.

[8M]
5 a) Describe All-pairs shortest path algorithm with example. Give the time complexity of
the algorithm.
[8M]
b) Consider A
1
=5X4, A
2
=4X6, A
3
=6X2, A
4
=2X7.P
1
=5, P
2
=4, P
3
=6, P
4
=2, P
5
=7 and
Apply matrix chain multiplication to obtain optimal sequence.

1 of 2
[8M]
R13
SET – 4

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Devise an algorithm that sorts a collection of n=1 elements of arbitrary type. [3M]
b) State the best, average and worst case complexities of binary search for successful
and unsuccessful search.
[4M]
c) Write the functional difference of divide and conquer greedy method. [4M]
d) State the principle of optimality. Find two problems for which the principle does
not hold.
[4M]
e) Define Implicit constraints and Explicit constraints with example. [3M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+ ??+ a
1
n+a
0
,then f(n)=O(n
m
). [4M]
b) Describe the Pseudo code conventions for specifying algorithms of recursive and
an iterative algorithm to compute n!
[8M]
c) Determine the frequency counts for all statements in the following algorithm
segment.

[4M]
3 a) Solve the recurrence relation using substitution method
T(n)= { T(1) n=1
aT(n/b)+f(n) n>1 ,where a=5,b=4,and f(n)=cn
2
.
[3M]
b) Apply quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order.
[8M]
c) Analyze the best, average and worst case complexity of quick sort.
[5M]
4 a) Compare BFS and DFS algorithm with an example graph and denote its time
complexities.
[8M]
b) Derive time complexity of job sequencing with deadlines .Obtain the optimal
solution when n=5, (p1, p2, ?)=(20,15,10,5,1) and ( d1,d2,? )=( 2,2,1,3,3 ).

1 of 2

[8M]
R13
SET – 1

Code No: RT32054

5 a) Describe about reliability design with an example. [8M]
b) Obtain the solution to knapsack problem by Dynamic Programming method n=6, (p1, p2,?p6)=(w1,w2,?w6)=(100,50,20,10,7,3) and m=165.
[8M]
6 a) Explain how backtracking is used for solving n- queens problem. Show the state
space tree.
[8M]
b) Describe the algorithm for Hamiltonian cycles and Determine the order of
magnitude of the worst-case computing time for the backtracking procedure that
finds all Hamiltonian cycles.
[8M]
7 a) Explain the principles of FIFO Branch- and-Bound. [8M]
b) Consider the travelling salesperson instance defined by the cost matrix.
Obtain the reduced cost matrix and the portion of the state space tree that will be
generated by LCBB.

[8M]

*****

2 of 2

R13
SET – 1

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) What are the four distinct areas of study of algorithm? [4M]
b) Is quick sort a stable sorting method? Justify. [3M]
c) What is meant by ?ordering paradi gm?? Give an example problem. How it is
different with ?subset paradigm ? of the greedy technique.
[4M]
d) What is purging or dominance rule. How it is applicable. [3M]
e) Define state space and state space tree. [4M]
f) Describe about Bounding with suitable example. [4M]
PART ?B
2 a) Prove the theorem if f(n)=a
m
n
m
+??+a
1
n+a
0
and a
m>
0,then f(n)=O(n
m
). [4M]
b) Write a recursive algorithm to find the sum of first n integers and Derive its time
complexity.
[8M]
c) Mention the important advantages and disadvantages of using randomized
algorithms.
[4M]
3 a) Can we say that the time for Merge Sort is O(n log n).What is its worst and best
time of procedure for Merge Sort.
[3M]
b) Write recursive binary search algorithm with an example and analyze time
complexity. List the applications of binary search.
[8M]
c) Describe the control abstraction for divide and conquer. [5M]
4 a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution
to the knapsack instance n=7,m=15 , (p1 ,p2?.,p7)= (10,5,15,7,6,18,3),and ( w 1,w2, ?w 7 ) =(2,3,5,7,1,4,1).
[8M]
b) Apply greedy algorithm to generate single-source shortest path with an example
graph. Mention its time complexity.
[8M]
5 a) Write about Dynamic Programming General method. [6M]
b) Describe the algorithm to find minimum-cost binary search tree. Show that the
computing time of function OBST is O (n
2
).
[10M]
6 a) Mention an algorithm that Presents a recursive formulation of the backtracking
technique.
[8M]
b) Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35
and draw the portion of the state space tree that is generated.
[8M]
7 a) Draw the portion of the state space tree generated by LCBB for the knapsack
instance: n=5,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2), and
m=12.
[8M]
b) Apply branch and bound algorithm to solve the travelling salesman problem with
an example.
[8M]
*****
R13
SET – 2

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) List out the criteria?s of an algorithm. [4M]
b) Mention the advantages and disadvantages of binary search. [3M]
c) Represent a high-level description of job sequencing algorithm. [4M]
d) List the features of dynamic programming. [3M]
e) Define chromatic number of a graph and planar graph. [4M]
f) What is branch and bound algorithm? How it is different from backtracking? [4M]
PART ?B
2 a) Show that the following equalities are incorrect with suitable notations
i)10n
2
+9=O(n) ii) n
2
logn=O(n
2
)[4M]
b) Implement an algorithm to generate Fibonacci number sequence and determine the
time complexity of the algorithm using the frequency method.
[8M]
c) Write about three popular methods to arrive at amortized costs for operations with
example.
[4M]
3 a) What is stable sorting method? Is merge sort a stable sorting method? Justify. [3M]
b) Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show
its computing time is O(n log n).
[8M]
c) Define internal and external nodes of binary decision tree. Draw the binary decision
tree for binary search with n=14.
[5M]
4 a) Describe the greedy method control abstraction for the subset paradigm. [8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using prim?s algorithm.

[8M]
5 a) Describe the Travelling sales person problem and discuss how to solve it using
dynamic programming.
[8M]
b) Design a three stage system with device types D
1
, D2, D3. The costs are $30, $15, $20
respectively. The cost of the system is to be no more than $105.the reliability of each
device type is 00.9, 0.8and 0.5 respectively.
1 of 2
[8M]
R13
SET – 3

Code No: RT32054

6 a) Describe general iterative backtracking algorithm. [8M]
b) Write a backtracking algorithm to solve sum of subsets problem with m=35,
w= {20, 18, 15, 12, 10, 7, 5} to the variable tuple size formulation.
[8M]
7 a) Describe about Control Abstractions for LC-search. [8M]
b) Draw the portion of the state space tree generated by LCBB for the knapsack instance:
n=5,(p1,p2,p3,p4,p5)=(w1,w2,w3,w4,w5)=(4,4,5,8,9), and m=15.
[8M]

*****

2 of 2
R13
SET – 3

Code No: RT32054
III B. Tech II Semester Regular/Supplementary Examinations, April -2018
DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science Engineering and Information Technology)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B)2. Answering the question in Part-A is compulsory
3. Answer any THREE Questions from Part-B
*****
PART ?A
1 a) Define Little Oh notation with example. [3M]
b) Describe the time complexity of Divide And Conquer in the recurrence form. [4M]
c) What is knapsack problem? State knapsack problem formally. [4M]
d) Distinguish Greedy method and Dynamic Programming. [3M]
e) Denote live node and dead node with example. [4M]
f) Compare LC and FIFO brand- and-bound. [4M]
PART ?B
2 a) Write a recursive algorithm to solve Towers of Hanoi problem with an example. [4M]
b) Describe about probabilistic analysis in detail. [8M]
c) Implement iterative function for sum of array elements and find the time complexity
use the increment count method.
[4M]
3 a) Why is it necessary to have the auxiliary array b[low: high] in function Merge? [3M]
b) Apply Merge Sort to sort the list a[1:10]=(31,28,17,65,35,42.,86,25,45,52). Draw the
tree of recursive calls of merge sort, merge functions.
[8M]
c) Write iterative binary search algorithm with example.
[5M]
4 a) Use the greedy algorithm for sequencing unit time jobs with deadlines and profits to
generate the solution when n= 7,( p1,p2,?p7 )=( 3,5,20,18 ,1,6,30) ,and ( d1,d2,?,d7)=(1,3,4,3,2,1,2).
[8M]
b) Define spanning tree. Compute a minimum cost spanning tree for the graph of figure
using kruskal?s algorithm.

[8M]
5 a) Describe All-pairs shortest path algorithm with example. Give the time complexity of
the algorithm.
[8M]
b) Consider A
1
=5X4, A
2
=4X6, A
3
=6X2, A
4
=2X7.P
1
=5, P
2
=4, P
3
=6, P
4
=2, P
5
=7 and
Apply matrix chain multiplication to obtain optimal sequence.

1 of 2
[8M]
R13
SET – 4

Code No: RT32054

6 a) Describe an algorithm to solve 8-queen problem and Show the state space tree. [8M]
b) Write an algorithm for finding all m-coloring of a graph with example.
[8M]
7 a) What is branch & bound? Explain the role of bounding function in it using LC – search [8M]
b) Generate FIFO branch and bound solution for the given knapsack problem. m = 15,
n = 3. (P
1
P
2
P
3
) = ( 10, 6, 8 ) (w
1
w
2
w
3
) = ( 10, 12, 3 )
[8M]

*****

2 of 2
R13
SET – 4