22MCAI5
USN \ I
First es ter MCA Degree Examination, Jan./Feb. 2023
Design and Analysis of Algorithms
Time: 3 hrs. Max. Marks: 100
Note: l. Ansh'er any FIW full questions, choosing ONE full question from each module.
2. M : Marks, L: Bloom's level , C: Course outcomes.
Module -I M L C
Q.r a. Define algorithm. Illustrate the characteristics of an algorithm. 06 LI col
b. List and explain the different problem types ofan algorithm. 04 LI col
c Explain asymptotic notations, with a diagram and explain with an example. 10 L2 cor
OR
Q.2 1l Design a general plan for analyzing the non recursive algorithm. Design an l2 L3 c(J2
algorithm for element uniqueness in an array. Obtain its time complexity.
b List and explain the fundamental data structures with definition and 08 LI c()2
examples.
Module - 2
Q.3 a. Design a binary search algorithm and derive its time complexity and apply t2 L3 c02
the same to search an element '?2" from the given elements.
3, 14, 27, 31, 40, 42, 55, 66
b Sort the following elements using Quick Sort. Show only I partition. 08 L3 c(J2
50, 30, 10, 90, 60, 40,35, 62
OR
Q.4 a Define Topological Sorting. Obtain the topological ordering of elements l0 L3 co2
using DFS and Source Removal Method, for the following graph Fig.Q4(a):
Fig.Q4(a)
b Define Heap. Explain different types of heap. Sort the following elements 10 L3 col
using heap sort technique by creating bottom-up max heap tree
26, 14, 18,42, 6,9,38
Module - 3
Q.s a. Consider the following jobs with their profits and deadlines. Find the l0 L3 co2
executing job sequence using greedy to obtain max proht.
<Pf, P2, Pr, P4, Ps,Pe>: <23,45, 6' 18, 60, 5>
<dr, dz, dr, &, ds, do> = <3,2' 1' 4,2, 1>
1of3
22MCAI5
b. Apply Kruskal algorithm to find Minimum Spanning tree for the below l0 L3 c03
graph, Fig.Q5(b).
l+
uIt
, A
UBRARY
t 7
[Link](b)
OR
Q.6 A Find the shortest path from the vertex "d" to all other vertices for the below l0 1..1 co2
graph, Fig.Q6(a).
4
1 L
1 l+
F I s Q6( a )
h. Construct a Huflrnan code for the followin data l0 L-1 c()2
Character A B C D
Prob 0.35 0.1 0.2 0.2 0.15
Find: (i) Huffman tree (ii) Decode the string *1 00 I l0 I I 0 1 001 101 "
Module - 4
Q.7 il Apply Forward approach Multistage graph technique to find shortest path l0 t.3 co-l
from S to t.
3
t a
lo
Fig.Q7(a)
b Find all pair shortest path for the below graph, Fig.Q7(b). l0 L3 CO2
J$
3
Fig.Q7(b)
2 of3
22MCAI5
OR
Q.8 a Applying dynamic programming, find the optimal solution for the instance l0 L3 c03
given below, with kna sack it w:5
Item Weight Value
I 2 sl2
2 I $10
3 3 $20
4 2 $1s
b Why we need Bellman-Ford algorithm? Apply the same to find the shortest l0 L3 c03
path for the graph.
-l
6
3
5 3
t/8R4fiy
-l
Fie.Q8(b)
Module - 5
Q.e a Define Backtracking. Find the solution space tree for 4-queens pro blem. l0 L2 col
b Find the subset from the given set with d = 15, s: {3, 7, 5, 6} by r0 I,3 co2
constructing a state space tree.
OR
Q.l0 il Solve the assi blem using branch and bound technique. l0 L3 c03
dr dz d: dr
Pr 9 z 7 8
,7
D. 6 4 3
P: 5 8 I 8
4
t
P4 7 6 9
b Solve the foltowing travelling salesman problem using branch and bound l0 L3 co3
technique by using the constraint "Visit City "H' before "c"
t
9
I
Fie.Ql0(b)
3 of3
