Scribd
Upload
21 views2 pages

Design and Analysis of Algorithms CSMCSD

This document is a question paper for the III B. Tech- I Semester Supplementary Examination in Design and Analysis of Algorithms at ACE Engineering College. It consists of two parts: Part A, which is compulsory and contains 10 questions worth 20 marks, and Part B, which includes 5 units with a choice of one question from each unit, totaling 50 marks. The questions cover various topics such as asymptotic notations, algorithms, and problem-solving techniques in computer science.

Uploaded by

naveenmittacodu0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

Design and Analysis of Algorithms CSMCSD

This document is a question paper for the III B. Tech- I Semester Supplementary Examination in Design and Analysis of Algorithms at ACE Engineering College. It consists of two parts: Part A, which is compulsory and contains 10 questions worth 20 marks, and Part B, which includes 5 units with a choice of one question from each unit, totaling 50 marks. The questions cover various topics such as asymptotic notations, algorithms, and problem-solving techniques in computer science.

Uploaded by

naveenmittacodu0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Page | 1

ACE
Engineering College
(An Autonomous Institution) ACE-R20

Question Paper Code: CM501PC

III B. Tech- I Semester Supplementary Examination - January-2025


DESIGN AND ANALYSIS OF ALGORITHMS
( CSM & CSD)
Time: 3 Hours Max. Marks: 70
H. T. No
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 20 marks. Answer all questions in Part A.
Part B consists of 5 Units. Answer any one full question from each unit. Each question carries
10 marks and may have a, b, c as sub questions

PART- A MARKS: 10*2=20

[Link]: 1 Question Marks

a) Define Asymptotic Notations. 2

b) Define space and Time Complexity. 2

c) Define Disjoint Set? Give an example. 2

d) State general steps of Backtracking. 2

e) Define General Principle of Dynamic Programming. 2

f) Define Optimal Binary Search Tree. 2

g) List the applications of Minimum Cost Spanning tree. 2

h) Define general Principle of Greedy method. 2

i) Compare FIFO and LC. 2

j) Define Satisfiability problem. 2


Page | 2

PART- B MARKS: 5*10=50

[Link] Question Description Marks

2. Consider the following recurrence T(n)=8T(n/2)+ n Obtain asymptotic bound 10


using substitution method
(OR)

3 Apply and explain merge sort to sort the following list: 8, 3, 2, 9, 7, 1, 5, 4. How 10
efficient is merge sort?

4 Discuss Union and Find algorithm with suitable examples. 10

(OR)

5. Give the solution to the 8-queens problem using backtracking. 10

6 Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, 10
read, while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1).
(OR)

7 With the help of suitable example explain the all pairs shortest path problem. 10

8 State the Job – Sequencing with deadlines problem. Find an optimal sequence to 10
the n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines
(d1, d2, d3, d4, d5) =(2, 2, 1, 3, 3)
(OR)

9 Define Greedy [Link] the optimal solution of the Knapsack instance 10


n=7,M=15,(p1,p2,p3,p4,p5,p6,p7)=(10,5,15,7,6,18,3) and
(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1).

10 Solve the Travelling Salesman Problem for the following graph using the Branch 10
and Bound Algorithm:

(OR)

11 a) Prove, If any NP-complete problem belongs to class P, then is P = NP? 5+5


b) Write a non deterministic algorithm of sorting the list of elements

You might also like