Scribd
Upload
41 views3 pages

ADA Model QP

This document is a model question paper for the Fourth Semester B.E Degree Examination in Analysis and Design of Algorithms. It includes various questions covering topics such as asymptotic notation, sorting algorithms, tree construction, minimum spanning trees, and dynamic programming. The paper consists of multiple sections with questions that require both theoretical explanations and practical algorithm implementations.

Uploaded by

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

ADA Model QP

This document is a model question paper for the Fourth Semester B.E Degree Examination in Analysis and Design of Algorithms. It includes various questions covering topics such as asymptotic notation, sorting algorithms, tree construction, minimum spanning trees, and dynamic programming. The paper consists of multiple sections with questions that require both theoretical explanations and practical algorithm implementations.

Uploaded by

pradeepshettar50
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

MODEL QUESTION PAPER

Fourth Semester B.E Degree Examination

BCS401 ANALYSIS and Design of Algorithms

Time: 3 Hrs Max. Marks: 100


Note: Answer all the questions.

Q. No. Cognt. COs Questions Marks


Level
1a) L2 CO1 Describe the Big-omega and Big-theta Asymptotic notation with 8
suitable examples.

1b) L1 CO1 Write the pseudo code of selection sort and also analyse its worst- 7
case time complexity.
1c) L2 CO1 Compare the order of growth of n! and 2n. 5

OR
1d) L2 CO1 Compute the recurrence relation for tower of Hanoi puzzle using 6
backward substitution method.
1e) L1 CO1 Write short notes on the following 8
i)Space complexity ii) comparing order of growth
1f) L2 CO1 Do the Mathematical Analysis to determine the value of the largest 6
element in a given array.

2a) L2 CO2 Explain master theorem and apply the same for the expression 5
T(n)=2A(n/2) +1.
2b) L3 CO2 Illustrate, the merge sort process for the given set of integers 8
8,3,2,9,7,1,5,4.

2c) L1 CO2 Write the algorithm for sequential search using brute force 7
approach
OR
2.d) L1 CO2 Write the pseudo code for quick sort algorithm. Derive the best-case 10
time complexity for the same.
2.e) L2 CO2 Given A= 1 2 and B = 5 6 using Strassen’s matrix multiplication, 10
34 78
compute the value of matrix C?

3a) Construct an AVL tree for the given set of data 10


40,20,10,25,30,22,50. Also define Transform and conquer technique

3b) Write a pseudocode for Comparison counting sort algorithm. And 10


also trace for the input 62,31,84,96,19

4.a) L2 CO3 Device an algorithm to find the minimum spanning tree by using
Kruskal’s method.
4.b) L2 CO3 Compute the single-source shortest path for the vertex a, for the 10
below graph using Dijkstra’s algorithm. Derive the time complexity
considering the basic operation.

OR
4. c) L2 CO3 Derive minimum spanning tree for the given weighted connected 10
graph using Prims algorithm.

4.d) L2 CO3 Illustrate the use of dynamic programming to solve 0/1 knapsack 10
problem. Given capacity=8.find the maximum profit along with the
selected list of items
Item Weight Value
1 3 2
2 4 3
3 6 1
4 5 4

5.a) L3 CO5 Illustrate the state space tree for a 4-queen problem using 4*4 chess 10
board, and write the possible valid solutions for the same.
5. b) L1, L2 CO5 Explain the following with suitable examples 10
i) Branch and Bound vs. Backtracking
ii) NP-Hard Vs NP-Complete

---***---

You might also like