No.

of Printed Pages : 5 MCS-211

om
MASTER IN COMPUTER APPLICATIONS
(MCA-NEW)

Term-End Examination

.c
December, 2021

u ru
MCS-211 : DESIGN AND ANALYSIS OF

tG
ALGORITHMS

Time : 3 hours Maximum Marks : 100

en
(Weightage : 70%)
m
Note : Question no. 1 is compulsory. Attempt any three
questions from the rest.
ign

1. (a) Write a mathematical definition of

ss

O (big oh). Assume that the function

f(n) = 2n2 + 3n + 1. Show that f(n) = O(n2). 5
UA

(b) Define a recurrence relation of QuickSort

algorithm and solve it using a recurrence
tree. 10
NO

(c) What are the key features of combinatorial

problems ? Describe and formulate three
IG

combinatorial problems. 10

MCS-211 1 P.T.O.
 (d) Describe a task scheduling problem as an
optimization problem. Apply the

om
scheduling algorithm with deadlines to
maximize the total profit to the following
problem : 10

.c
Jobs Deadlines Profits

ru
1 2 60

u
2 3 50

tG
3 4 70
4 en 5 80
5 4 75

6 3 55
m
7 2 40
ign

(e) List all the different orders in which we

can multiply five matrices M1, M2, M3,
M4, M5. 5
ss

2. (a) Explain the naïve string matching

UA

algorithm and derive its worst case

complexity. What is its drawback ? What
will be the maximum valid shifts of a
NO

pattern in the text in the following

example ? 10
Text : a b c x y z d e f g h
IG

Pattern : f g h

MCS-211 2
 (b) What is the similarity between Dijkstra’s
single source shortest path and Prim’s

om
minimum cost spanning tree algorithms ?
Apply Dijkstra’s algorithm to find the
shortest path from v1 to all other vertices of

.c
the following graph : 10

u ru
tG
en
3. (a) Apply Horner’s method for evaluating a
m
polynomial expression
p(x) = 6x6 + 5x5 + 4x4 – 3x3 + 8x – 7
ign

at x = 3.
Calculate : 10
ss

(i) How many times will the loop execute ?

(ii) What will be the total number of
UA

multiplication and addition

operations ?
NO

(b) Define a fractional knapsack problem as an

optimization problem. Write a greedy
method to find an optimal solution to the
problem. Show the complexity of the
IG

algorithm. 10

MCS-211 3 P.T.O.
 4. (a) Apply the DFS algorithm to the following
graph with the starting vertex v1. List the

om
order in which vertices will be visited.

.c
u ru
tG
en
Show the complexity analysis if a graph is
represented through
(i) Adjacency list, and
m

(ii) Adjacency matrix. 10

ign

(b) Explain P, NP and NP-complete class of

problems with appropriate examples of
each class. 10
ss

5. (a) Apply Floyd Warshall’s algorithm and show

the matrix D2 of the following graph : 10
UA
NO
IG

MCS-211 4
 (b) Explain the use of master method. Write
and interpret all the three cases of the

om
master method to solve recurrence relation
problem. 10

.c
u ru
tG
en
m
ign
ss
UA
NO
IG

MCS-211 5 P.T.O.
 o m
. c
uru
t G
en
n m
s i g
A s
O U
N
IG
 o m
. c
uru
t G
en
n m
s i g
A s
O U
N
IG
 o m
. c
uru
t G
en
n m
s i g
A s
O U
N
IG
 No. of Printed Pages : 4 MCS-211

om
MASTER IN COMPUTER APPLICATIONS
(MCA-NEW)
Term-End Examination

.c
December, 2022

ru
MCS-211 : DESIGN AND ANALYSIS OF

u
ALGORITHMS

tG
Time : 3 hours Maximum Marks : 100
(Weightage : 70%)
en
Note : Question no. 1 is compulsory. Attempt any
three questions from the rest.
m
ign

1. (a) Write a mathematical definition of big

omega (). For the functions defined by
f(n) = 3n3 + 2n2 + 1 and g(n) = 2n2 + 3,
ss

verify that f(n) =  (g(n)). 6

(b) Explain the principle of optimality in
UA

dynamic programming, with the help of an

example. 6
(c) Apply a master method to give the tight
NO

asymptotic bounds of the following

recurrences : 8
(i) T(n) = 4T (n/2) + n2
IG

(ii) T(n) = 9T (n/3) + n

MCS-211 1 P.T.O.
 (d) Run the Prim’s algorithm on the following

om
graph. Assume that the root vertex is a .

.c
u ru
Derive the complexity of the algorithm. 10

tG
(e) Apply Huffman’s algorithm to construct a
en
Huffman’s tree and optimal binary prefix
code for the letters and its frequencies as
m
given in the following table : 10

Letter Frequency
ign

A 15
B 6
ss

C 7
D 5
UA

E 12
I 13
Z 2
NO

2. (a) Explain Cook-Levin’s theorem on

CNF-Safisfiability problem, with the help of
IG

an example. 10

MCS-211 2
 (b) (i) Apply Dijkstra’s single source
shortest path algorithm to the

om
following graph with a as starting
vertex. Show all the intermediate
steps. 7

.c
u ru
(ii)
tG
What is the significant feature of
en
Bellman-Ford’s algorithm which is not
supported in Dijkstra’s algorithm ? 3
m
3. (a) Write and explain pseudocode for
Ford-Fulkerson’s algorithm for maximum
ign

bipartite matching. 10

(b) Apply the partition procedure of Quicksort

algorithm to the following array :
ss

[35, 10, 40, 5, 60, 25, 45, 15]

Show all the intermediate steps. 10

UA

4. (a) Apply DFS to the complete graph on four

vertices. List the vertices in the order they
NO

would be visited. 7
(b) How many comparisons are needed for a
binary search in a set of 512 elements ? 3
IG

MCS-211 3 P.T.O.
 (c) Apply Floyd-Warshall’s algorithm to the
following graph and show D2. 10

.c om
u ru
5. (a) Describe the task scheduling algorithm as

tG
an optimization problem and calculate its
complexity. Consider the following jobs and
its service times and apply the task
en
scheduling algorithm to minimize the total
amount of time spent in the system. 10
m
Job Service time
1 10
ign

2 15
3 8
ss

4 12
5 6
UA

(b) Describe the basic principle of KMP

algorithm for string matching. What is its
advantage compared to Naive and
NO

Rabin-Karp’s algorithm for string

matching ? Calculate the time complexity of
KMP algorithm. 10
IG

MCS-211 4
 No. of Printed Pages : 4 MCS-211

om
MASTER OF COMPUTER

u.c
APPLICATIONS
(MCA-NEW)

ur
Term-End Examination
June, 2023

tG
MCS-211 : DESIGN AND ANALYSIS OF
ALGORITHMS
en
Time : 3 Hours Maximum Marks : 100
(Weightage : 70%)
m

Note : Question No. 1 is compulsory and carries

40 marks. Attempt any three questions from
ign

the rest.

1. (a) What is an algorithm ? What are its

ss

desirable characteristics ? 5
UA

(b) What are asymptotic notations ? Explain

any two asymptotic notations with suitable
example for each. 5
NO

(c) Solve the following recurrence relation

using substitution method : 5
n
T  n   2T    n
IG

2

P. T. O.
 [2] MCS-211

(d) Write and explain binary search algorithm

with an suitable example. 5

om
(e) Explain Depth First Search (DFS)
algorithm with an suitable example. 5

u.c
(f) What is Dynamic Programming approach
of problem solving ? Write the steps
involved in dynamic programming. 6

ur
(g) What are Optimization and Decision
problems ? Give an example of each. 5

tG
(h) Design a state space tree for the given
subset sum problem. S = {4, 6, 7, 8}, W = 8.
en
4
2. (a) Explain all the three cases of Master’s
m

Theorem. Apply Master’s theorem to solve

the given recurrence relation : 8
ign

n
T  n   9T  
3
ss

(b) Evaluate :
p  x   3x 4  2x 3  5x  7 at x  2
UA

using Horner’s rule. Show stepwise

iterations. 6
NO

(c) Prove that for all non-negative integers

‘n’ : 6
20  21  22  .......2n  2n 1  1.
IG
 [3] MCS-211

3. (a) What is Huffman coding ? Write the steps

for building the Huffman tree with an

om
example. 6
(b) Explain Quick sort algorithm using divide
and conquer approach. 6

u.c
(c) What are strongly connected components ?
Explain how adjacency matrix and

ur
adjacency list are created for a connected
graph with the help of a suitable diagram.

tG
2+3+3
4. (a) Show the step by step execution of
en
Kruskal’s algorithm for the following
graph : 6
m
ign
ss

(b) What is Matrix chain multiplication

problem ? Find an optimal parenthesiza-
UA

tion of a martix-chain product whose

sequence of dimensions are as follows : 2+6
Matrix Dimension
NO

A1 30 × 35
A2 35 × 15
IG

A3 15 × 5

P. T. O.
 [4] MCS-211

(c) Explain Rabin Karp Algorithm for string

matching with suitable example. 6

om
5. Write short notes on any four of the following :
4×5=20

u.c
(i) Deterministic vs. Non-deterministic
algorithms
(ii) CLIQUE and vertex cover problem

ur
(iii) Backtracking problem with example

tG
(iv) Bellman-Ford algorithm
(v) Fractional Knapsack problem
en
m
ign
ss
UA
NO
IG

MCS–211