Categories: Third Year Second Semester (3-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

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

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.

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

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.

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

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

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.

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

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

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

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.

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

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

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

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.

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

746268 PAPER V - REHABILITATION MEDICINE INCLUDING GERIATRIC MEDICINETHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY…

4 years ago

746268 PAPER V - REHABILITATION MEDICINE INCLUDING GERIATRIC MEDICINETHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY…

4 years ago

746267 PAPER IV - P.T. IN ORTHOPAEDICSTHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY [LN 6267]…

4 years ago

746267 PAPER IV - P.T. IN ORTHOPAEDICSTHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY [LN 6267]…

4 years ago

746266 PAPER III – CLINICAL ORTHOPAEDICSTHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY [LN 6266] AUGUST…

4 years ago

746265 PAPER II – P.T. IN NEUROLOGYTHE TAMIL NADU DR. M.G.R. MEDICAL UNIVERSITY [LN 6265]…

4 years ago