DR.
BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE
Supplementary Winter-2023
Course: B. Tech. Branch : Computer & Allied Engineering Semester :IV
Subject Code & Name: BTCOC401 Design & Analysis of Algorithms
Max Marks: 60 Date:16-01-24 Duration: 3 Hr.
Instructions to the Students:
1. All the questions are compulsory.
2. The level of question/expected answer as per OBE or the Course Outcome (CO)
on which the question is based is mentioned in front of the question.
3. Use of non-programmable scientific calculators is allowed.
4. Assume suitable data wherever necessary and mention it clearly.
(Level/CO) Marks
Q. 1 Solve Any Two of the following. 12
A) What is Algorithm? Explain criteria of Algorithms. Remember 6
B) What is Asymptotic Notations? Explain any three Asymptotic Notations. Remember 6
C) Define Max and Min Heap and write algorithm to insert into a heap. Analysis 6
Q.2 Solve Any Two of the following. 12
A) Write algorithm for Binary Search and calculate its time complexity. Application 6
B) Explain Quick Sort algorithm with its performance analysis. Analysis 6
C) Explain Strassen’s Matrix Multiplication. Remember 6
Q. 3 Solve Any Two of the following. 12
A) Draw a state space tree for finding Four Queens problems solution. Application 6
B) Describe Graph Coloring Problem with suitable example Analysis 6
C) Explain Branch and Bound with suitable example. Remember 6
Q.4 Solve Any Two of the following. 12
A) Find an optimal solution to the knapsack instance n = 7, m = 15, (P1 ,P2, P3 Application 6
,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).
B) What is Minimum Cost Spanning Tree? Explain with suitable example. Remember 6
C) Explain Job Sequencing with Deadlines. Remember 6
Q. 5 Solve Any Two of the following. 12
A) Analyze Floyd Warshals algorithm for Dynamic Programming. Analysis 6
B) Explain complexity class P and complexity class NP. Remember 6
C) Differentiate between Dynamic Programming and Greedy Algorithm. Analysis 6
