Code No: R2032423 R20 SET -1
III B. Tech II Semester Regular/Supplementary Examinations, May/June -2024
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE(AIML),CSE(AI),CSE(DS),CSE(AIDS), AIDS,AIML,CSD)
Time: 3 hours Max. Marks: 70
Answer any FIVE Questions ONE Question from Each unit
All Questions Carry Equal Marks
*****
UNIT-I
1. a) Compare the features of the algorithm with pseudocode. [7M]
b) Find the Time complexity of the following code [7M]
int fun(int n)
{ int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;}
(OR)
2. a) Explain the algorithm specification for conditional and iterative statements. [7M]
b) Develop an algorithm to solve the Towers of Honai problem with n disks with [7M]
three towers.
UNIT-II
3. a) Develop the control abstraction and derive the time expression for the divide [7M]
and conquer logic.
b) Derive the time complexity for the successful search in the binary search tree. [7M]
(OR)
4. a) Develop the quick sort algorithm and trace it for an example. [7M]
b) Explain the method of vertex splitting with an example. [7M]
UNIT-III
5. a) Design the algorithm to find the shortest path in the multistage graph using [7M]
forworrd approach..
b) Explain the 0/1 Knapsack problem in the dynamic programming approach. [7M]
(OR)
6. a) List and explain any two dynamic programming approaches with examples. [7M]
b) Discuss the issues in designing reliable systems. [7M]
UNIT-IV
7. a) Illustrate the eight-queen problem with suitable diagrams. [7M]
b) Develop the backtracking solution to the 0/1 Knapsack problem. [7M]
(OR)
8. a) Explain the advantages of backtracking algorithms in detail. [7M]
b) Develop an algorithm to find all Hamiltonian cycles in graphs. [7M]
UNIT-V
9. a) Develop a non-deterministic algorithm to search for an element in an array. [7M]
b) Explain NP-Hard and NP-Complete problem with example.. [7M]
(OR)
10. a) Explain the relation among P, NP, Np-complete and NP-hard problems. [7M]
b) Explain the Cook’s theorem. [7M]
1 of 1
|''|''|||''|'''|||'|
Code No: R2032423
R2031011
R2031351
R203135A
R203147A
R203147C
R203105O
P2031051 R20 SET
SET
RA--22
III B. Tech II Semester Regular/Supplementary Examinations, May/June -2024
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE(AIML),CSE(AI),CSE(DS)CSE(AIDS), AIDS,AIML,CSD)
Time: 3 hours Max. Marks: 70
Answer any FIVE Questions ONE Question from Each unit
All Questions Carry Equal Marks
*****
UNIT-I
1. a) List and explain the characteristics of the algorithm. [7M]
b) Develop an algorithm for selection sort. [7M]
(OR)
2. a) Find the Time complexity of the following code [7M]
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 3)
for (int j = 0; j < i; j=j+2)
count += 1;
return count;
}
b) Discuss the design issues of iterative algorithms. [7M]
UNIT-II
3. a) Derive the time complexity for the Unsuccessful search in the binary search [7M]
tree.
b) Derive the time complexity of the logic that finds max and min numbers within [7M]
an array.
(OR)
4. a) Solve the recurrence relation. [7M]
C(n)=2C(n/2)+3 if n>2 and 2 if n=2
b) Develop the randomised quick sort algorithm and trace it for an example. [7M]
UNIT-III
5. a) Define optimal binary search tree with example.. [7M]
b) Explain traveling sales person problem with an example.. [7M]
(OR)
6. a) Develop the algorithm for the 0/1 knapsack problem using a dynamic [7M]
programming approach.
b) Write a function Largest(pair,w, t, h, i,m) that uses binary search to determine [7M]
the largest q, t ≤q ≤h, such that pair[q].w+w[i] ≤m.
UNIT-IV
7. a) Develop an algorithm to generate an m-coloring graph. [7M]
b) Develop an algorithm to find all Hamiltonian cycles in graphs. [7M]
(OR)
8. a) Compare planar and non-planar graphs with examples. [7M]
b) Explain the steps in recursive backtracking with an example. [7M]
1 of 2
|''|''|||''|'''|||'|
Code No: R2032423
R2031011
R2031351
R203135A
R203147A
R203147C
R203105O
P2031051 R20 SET
SET
RA--22
UNIT-V
9. a) List and explain any two NP-complete problems. [7M]
b) Explain the Cook’s theorem. [7M]
(OR)
10. a) Is code generation an NP-hard problem? Justify your answer. [7M]
b) Develop a non-determinsitic clique pseudocode. [7M]
2 of 2
|''|''|||''|'''|||'|
Code No: R2032423
R203105O
R2031011
R2031351
R203135A
R203147A
R203147C
P2031051 R20 SET
SET
RA--32
III B. Tech II Semester Regular/Supplementary Examinations, May/June -2024
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE(AIML),CSE(AI),CSE(DS)CSE(AIDS), AIDS,AIML,CSD)
Time: 3 hours Max. Marks: 70
Answer any FIVE Questions ONE Question from Each unit
All Questions Carry Equal Marks
*****
UNIT-I
1. a) List and explain the parameters to assess the performance of the algorithm. [7M]
b) Compute the Space complexity for the following code [7M]
int fun(int n)
{ int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count; }
(OR)
2. a) Compare the Little-Oh and Theta notations with examples. [7M]
b) Develop the randomised algorithm for primality testing. [7M]
UNIT-II
3. a) Develop the merge sort algorithm and trace it for an example. [7M]
b) Find out the strategy to reduce the complexity of matrix multiplication? Justify [7M]
your answer.
(OR)
4. a) Derive the time complexity for Insertion sort. [7M]
b) Develop an algorithm to find the Kth smallest number. [7M]
UNIT-III
5. a) Compute the shortest path for the following graph using dynamic [7M]
programming.
b) Illustrate the reliable system design using a dynamic programming approach in [7M]
detail.
(OR)
6. a) Explain all pairs of shortest path problems with an example. [7M]
b) Identify the possible binary search trees for the identifier set {do, while, if, [7M]
else}.
1 of 2
|''|''|||''|'''|||'|
Code No: R2032423
P2031051
R2031011
R2031351
R203135A
R203147A
R203147C
R203105O R20 SET
SET
RA--32
UNIT-IV
7. a) Explain graph coloring with examples. [7M]
b) Let w = {5,7,10,12,15,18,20}and m=35. Find all possible subsets of w that sum [7M]
to m. Do this using SumOfSub. Draw the portion of the state space tree that is
generated.
(OR)
8. a) Illustrate the 4-Queen problem-solving with suitable diagrams. [7M]
b) Develop the algorithm for recursive backtracking. [7M]
UNIT-V
9. a) Develop a non-deterministic clique pseudocode. [7M]
b) Explain the terms NP-hard and NP-complete. [7M]
(OR)
10. a) List and explain any two NP-complete problems. [7M]
b) Compare the features of deterministic and non-deterministic algorithms with [7M]
examples.
2 of 2
|''|''|||''|'''|||'|
Code No: R2032423
R2031011
R2031351
R203135A
R203147A
R203147C
R203105O
P2031051 R20 SET
SET
RA--42
III B. Tech II Semester Regular/Supplementary Examinations, May -2024
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE(AIML),CSE(AI),CSE(DS)CSE(AIDS), AIDS,AIML,CSD)
Time: 3 hours Max. Marks: 70
Answer any FIVE Questions ONE Question from Each unit
All Questions Carry Equal Marks
*****
UNIT-I
1. a) Illustrate step table representation for the Fibonacci series computation [7M]
algorithm.
b) Find the Time complexity of the following code [7M]
void fun(int n, int arr[])
{ int i = 0, j = 0;
for (; i < n; ++i)
while (j < n && arr[i] < arr[j])
j++;}
(OR)
2. a) Compare the Big-Oh and Omega notations with examples. [7M]
b) Given a 2-sided unbiased coin. Using this coin, how will you simulate an n- [7M]
sided coin
(i) When n is a power of 2?.
(ii) When n is not a power of 2?
UNIT-II
3. a) Develop an algorithm to Merge two sorted subarrays using auxiliary storage. [7M]
b) Develop Greedy method control abstraction for the subset paradigm. [7M]
(OR)
4. a) Find the feasible solutions for the following instance of the knapsack problem: [7M]
n = 3,m= 20,(p1,p2,p3) = (25,24,15), and (w1,w2,w3)= (18,15,10).
b) Develop the algorithm for Tree vertex splitting. [7M]
UNIT-III
5. a) Explain the solution to the travelling salesperson problem with a dynamic [7M]
programming approach.
b) Formulate the cost function for finding the shortest path in the k-stage graph [7M]
problem in dynamic programming.
(OR)
6. a) Explain flow shop scheduling with an example. [7M]
b) Explain the features of dynamic programming. [7M]
UNIT-IV
7. a) With m = 35, run SumOfSub on the data [7M]
(a) w = {5,7,10,12,15,18,20},
(b) w = {20,18,15,12,107,5}
(c) w = {15,7,20,5,18,10,12}.
Are there any differences in the computing times?
b) Develop the algorithm to solve the 8-queen problem. [7M]
(OR)
8. a) Develop an algorithm to solve the problem of the sum of subsets. [7M]
b) Explain the steps in recursive backtracking with an example. [7M]
1 of 2
|''|''|||''|'''|||'|
Code No: R2032423
R2031011
R2031351
R203135A
R203147A
R203147C
R203105O
P2031051 R20 SET
SET
RA--42
UNIT-V
9. a) Develop an algorithm for non-deterministic knapsack. [7M]
b) List and explain any two NP-complete problems. [7M]
(OR)
10. a) Compare the features of deterministic and non-deterministic algorithms with [7M]
examples.
b) Illustrate the Node cover decision problem with a neat sketch. [7M]
2 of 2
|''|''|||''|'''|||'|
