1-i

(i) ._ Printed Pages : .4 Roil NoI ........................... :.... .

(ii) Questions :9 Sub. Code.: I3 I 4 I 9 I 11
Exam. Code : I5 I O I 71
M.C.A. 3rd Semester
1124
M.C.A. SEMESTER SYSTEM
Paper-CS-67: Analysis and Design ofAlgorithm

.Time Allowed : Three Hours] [Maximum Marks : 80

Note:- Attempt five questions in all, including Q-9 in Part-E, which
is compulsory and taldng one each from Part-A to Part-D.

PART-A
I. (a) Give the significance of asymptotic growth order of a
function. Explain the notations used to represent the rate
of growth of rwming time of algorithm~.
(b) Write a recurrence relation T(N) that expresses the worst
case number of comparisons used in 3-way merge sort,
given an array of N elements as input. Assume that
T(l) =I. Also solve this recurrence relation. 8,8

2. (a) Write a non recursive algorit~ for binary search and

analyze its complexity.
(b) Explain, in detail, Best, Worst [Link] time compl~xity
of the following algorithms:
(i) Quick sort.
(n) Strassen's matrix multiplication 8,8

3491/BDF-24720 1 [Turn over

 _--,
I

PART-B , . ·_
3. - (a) Apply Dj ikstra,s algori~ to calculate th~ shortes1'ath,
from S to every other node in the graph shown below :-
..__·__,;9___...,. G
1
1 E .1. '
·s 6
----- 7
~---, F
·4
--
(b) Define a sp~jng tree in~ connected _graph. Find the
minimum spanning tree for the following graph using Prim's
algoritlnn .:
a

e 8,8

4. (a) . Write a pseudo-code of the· dynamic programming ·

algorithm for solving optitnal binary search tree and
detennine its time and space efficiencies.
(b) Oive an _algorith1n based on dynamic programmi_ng
· technique to solve the travelling salesman problem. · 8,8

3491/BDF-24720 2
 PART--C
5::. ~) What is Hamiltonian Cycle? Write an algorithm to find all
Hamiltonian cycles in a graph.
· (b) Explain backtracking technique..Discuss the 8-queen problem
withitsalgorithm. • 8,8

. 6. (a) Solve the Travelling Salesman problem having the following

cost matrix using branch and bolllld technique :
A B ·c D
A X 5 2: 3
B 4 X 2 3
C 4 2 X 3
D 7 6 8 X
(b) Explain how the knapsack .proble~ is solved ·with
branch-and-bound technique. · Discuss the efficiency
.
considerations in the implementation of branch and bound
_algorithm · 8;·8

PART----D
7. Distinguish among P, NP, NP-Complete and NP-Hard problems.
Explain ~y givin~ an example of [Link] these. In what se~se are
NP-complete problems considered to be the"hardest" problems
in NP? 16

8. on
(a) . Explain briefly lower bound theory. What are comparison
trees ? Explain the use of a comparison tree to derive lower
bound on comparison-based sorting.

3 [Turn over
3491/BDF-24720
 (b) Find lower bound for multiplying m x n matrix wi,.n ~-1
vector. · 8,8

PART-E (Compulsory Question)

' 9. (a) What are the qualities and capabilities ofany good algorithm?
(b) lfTl(N) = O(f(n)) and T2(N) = 0(f(n)), ·
then Tl(N)= O(T2(N)). (frue/False)
. .
(c). Dijkstra's algorithm for shortest path and Prim's minimwn
spanning tree algorithm have the same big-Oh worst case
nmning time. (frue/False)
(d) What is the worst case complexity of ~election sort?
(e) What is the dif_Ierence between divide-and-conquer and
dynamic programming?
(t) Define 0/1 knapsack problem.
(g) Wha~ is m-colorability graph problem?
(h) State Cook's theorem. 8x2=16
; .,. . -·
I• .

34 91 /BD F-24720 4 400

 [Link]: 13 I 4 l 9.I ti
' ..
(ii) Questions.·. : : 9

Exam. Code : I 5 I o·I.71

M.C.A. 3rd Semester
1125
M.C.A. SEMESTER SYSTEM
Paper-CS-67: Analysis and Design of Algorithm
Time Allowed : Three Hours] [Maximum Marks : 80

Note:- Attempt five questions in all, including Q--9 in Section E, Which is

compulsory and taking one question each from Section-A to
Section-D.

SECTION-A
1. (a) What is a recursive algorithm? Give an example of recursive
-algorithm. 6
(b) How to sort an array using Quick Sort? Discuss with the help
of an algorithm. Derive its best case and worst case
complexity. 10

2. (a) How to multiply two matrices using yolker Strassen's Matrix

Multiplication? Derive complexity ofthe method. 8

(b) What do you understand by time and space complexity of an

algorithm ? How to find these for an algorithm ? 8

3491/BHJ-32784 1 [Turn over

 . . .
.. .
SECTION~B·: ..:;: ·"·

. .. 3. (a): · Discuss Greedy Method with the help ofKnapsack problem: . .

. .
··· ·.· Prove that greedy meth0d generates optimal s&!ution for this
10
problem.
(b) How to find minimum cost spanning tree for a given graph •
using ;r<ruskal algorithm? Explain with the help ofan algorithm.
6

4. (a) How to solve Travelling Salesman Problem using Dynamic

Programming technique ? Write an algorithm and derive its
10
complexity.
(b) Solve the following Knapsack Problem using Dynamic
Programming technique : n = 3, WI = 3, w2 = 2, w3 = 3,
p = 2, p = 3, p = 5, m = 6 where n is number of items, wi is
1 2 3
weight of ith item , pi is profit of ith item and m capacity of

knapsack. 6

SECTION-C
,

5. (a) Howtosolve Graph-coloring problem using Backtracking?

Write algorithm and discuss its complexity. 8

(b) Discuss the method ofbacktracking with the help ofan iterative
algorithm. 8

3491/BHJ-32784 2
 -· ··,§i::·· .(a) :· .· What is_a dynamic state space tree_? .lJow to so,l~~ trave_lling
Salesman problem using Least Cost Branch and ~ound with
: - .
the help of dynamic state space tree? Explain with the help of
..
anexample. 10

· (b) Discuss 15 puzzle problem. How to solve it using Least Cost

Branch and Bound? 6

SECTION-D

7. (a) What is comparison tree ? How comparison tree is used to

I

derive lower bound on ordered searching? 8

(b) Differentiate between Deterministic and Non-Deterministic

algorithms with the help of example algorithms. 8

8. (a) What is Halting Problem? Prove that Halting Problem is Nr

hard. 8
(b) Discuss lower bound for the problem ofpolynomial evaluation.

SECTION-E
9. (a) What are recurrence relations ? Give example. 2
(b) What is Break Even Point? 2
(c) What is Selection Problem? 2

3491/BHJ-32784 3 [Turn over

 (d) · ·. -Diffeientiate between a feasi b1e so 1uti on a~d -~ bptir, ~l -·-
solution. 2
(e) What do you understand by Principle of Optimality? 2

(f) What is Parallel Comparison Tree (PCT) ? Give example.

2

(g) Differentiate between implicit and explicit constraints with the

help of an example. 2

(h) Differentiate between FIFOBB and LIFOBB. 2

3491/BHJ-32784 4 400
 Exam. Code: 0507
• Sub. Code: 3893
. 1126
Master of Computer Applications
Third Semester
CS-67: Analysis and Design of Algorithms
Max. Marks: 80
Time allowed: 3 Hours
NOTE: Atlempt Jng_ questions in all, including Question No. 9 (Section-£) which is compulsory
and selecting one question each from Section A -D.
x-x-x
SECTION-A
QI. al What do you understand by best. average nnd worst case cornpkxi1y nl' ;111 ~lgori1l1111'.
Discuss ,,·ith the help ol'an algorithm. · 161
h) l·lo\\ to search an element in a list using divide and conquer technique'! Write a recursive
algurith111 lur the same and derive its best and worst rnsc complexity. ( llli
Q2) a) Soh•e 1<.1llowing recurrence relation using substitution method : t6l
T(n) ·" f1 n :::4
+C 11>4
bj Sort the liilluwing ekmcnts using quick sort technique :
15 . 3. 17. 10. 6. 20. 11. 23. 19
Di srnss the ,vorst case ol' quick sort and its complexity. ( Ji) I

SECTION-13
(.)3) a) State .lob Sequencing Problem with deadlines. llow 10 snln: this prnhkm using ~r,:•.:<!y
method. 1::-;plain with the help ofan example. (_(11 .
b) Write an algorithm to solve Travelling Salesman Problem using dYna111ic progra1nminr•
technique . Derive complexity or the nlgorithm. ( I il I
Q4) a) Solve l'ollm, ing inst,incc or Oil Km1ps11ck problem using dynamic programming technique
(onle1'L'd set [Link]): n •= 3. (pl.p2.p~) '" (10. 20. 30), (\\l.w2.w3) ,., (5. 8. 7). 111 · ll
. i (, I
b) Write mid c:-;plain !'rim's /\lgorilhm to find minimum cost spanning tree . D<.: ri,e its
1.:u111plcxit). ( J 1))
SECTION-C
(JS) a) I low lo soh·..: 4-queens problem using backlrncking. rind all the possible sollllinns. (8l
bJ \Vlrnt is Graph Coloring problem'l Write an algorithm tn lind :ill the solution, ll' w;1pli
cull>ring problem using backtracking icehnique. ( X)
(.)6) a) 1::-..plain [Link] Cost llranch and 13ound technique. I-lo\\ to solve 15-pun.k problem u,in~:
Lc:1st Cost 13ram;h ,111d Bound lechniquc'l (:~,
b) What is Dynamic State Space Tree') Solve Travelling Salesman Problem using Le.1st Cu, 1
llranch and Bound Tcdrniquc with clyna1nic stat-: space tree for the following CPSl 111111 ,·i,
(K)

SECTION~D .
Q7) a) Differentiate between Deterministic ·and Non-Dctcnninistic algorithms . Wrilc a . 1rn11-
dcterministic algorithm for sorting nn array and derive its complexity. lg l
h) Wlrnt arc NP Hard problems? Prove that I lalting Problem is NI' Hard. 18 1
Q8) a) What is Parallel Comparison Tree ( PCf)'? Derive lower hound 011 avcrngc c.i~c: sonin~i
using n-pl'()ccssor system. 181
bl Derive lll\\'t'I' hound on number. or 111ultiplicn1ions und additi<111s/s uhti-actio11s in 1:,1st "i.
pol"nomial evaluation. 181
SECTION-E
Q9) a) What is the use of Big O Asymptotic nota\ion? (2)
b) Deline Selection Problem. (2)
\ c) State Principle of Optimality? (2)

\
\
d) What is a live node and a dead node?
e) Discuss the concept of upper (upper cost u) in Branch and 13ound.
f) Differentiate between D Search and DFS.
g) Differentiate between Explicit and Implicit constraints with the help of an example.
(2)
(2)
(3)
(3l
)(--1<'..->i<.
 Ex [Link]
'· ' . Code: 3893
: ~_;, /
Master of c,.,mputer Applicntions
HJrd Semester
CS-67: Analysis and Design of Algorithms
Time allowed: 3 Hour~ Max. Marks: 80
NOTE:· Attempt .ill!£ questions in all, ir,c.'udbig Question No. 9 (Unit-VJ 1Fhich is compulsory
and selecting one question each from Unit 1-- JV. All questions carry equal marks.
x-x-x
UNIT- I
I. (a) Write and explain the algoriihm for the following prnblc111 using both ilcrntion :incl recursion. Alsll 111cntio11
the best, average and worst case comple1:ilics
· Obtain the location ot'a spcdlic tlcmcnf x in 1111 army 01'11 clements.
(b) Derive the COllljJ\c xity ofStrassen's i1,n;;·ix 11mltiplicatio11 '.1si11gdivide and rn111pkx s1ratcg)'.
2. (a) Solve the following recurrence relHtion a11d obt,!in the cu111plcxily in terms or 11.
T(11) = 2TU1/2) -:- n whw 11> I u•1d T( l ) = I.
(b) Compare and co:1trast 111crge sort anci quick ~ort methods using divide and t.:<.JIIL]IICr strategy.
Also compare tile best, Hild ll'ursl case Cl1111plc.,ilics:

UNIT - If
3.(a) Write the steps in l<.ruskal's al[1(Jrilhm for ol:,laining minimum cost spanning tree . Using the :ilgoritl1111,
obtain the 111in in1u111 cost spanning tree fur the following grnph.
12 r,'\
---\!..A
. ~ I
"0
25

cg·J
22 R' / '·, / ' c,

II 7 ',
,o .1<,,
J
_,,
---(0~
(b) How optimal binary scarclrtrees can be constructed using cly1w111it.: l'rogra111111ing approach?
Construct nptimal binary se,,rcl1 t1 ee for the following.
11=4 and (al ,a2,~J,a4)= (do, if, int, while), p(l :4)=(3,3,1,1) and q(OA)= (2,3 ,1,1 I).
4.(a) Prove tha, K:·uskai's algorithm generates minimum cost spanning tree .
(b) Describe lww travelling Sales ri<)rson problem can be solved using dyna11tic programming.

fJNIT- III
5. (a) What are explicit and in1plicit constraints in graph colnring problem? Draw and expl,1in the state
space tree fc r graph cvloring problem with J node:; and 3 cv\ors.
(b) Write the general mclhod to solve a prublc1:1 u~i11g leust cost branch and bt11111cl technique.
6.(a) Explain brieny the dyna mic stule space l1..-e ·Jrg:1nizati,111 111etliod lo solve lravc l!i11g salesptrso1·, 1w,bkn1.
(b) Define n-queens prublcm. Write the alg,t,rit\1111 with ,q;propriatc co1n111cnts.

UNIT-IV
7.(a) Compare the lower bounds for sorting and searching problem with II items with n11d without parallel Ctli:1putul:01!.
(b) Defin~ NP hard and l\P co111plcte prob\e,11s. G;ve an example problem lhal is NP hard but not NP ~om;;lete and
justify.
8.(a) Elaborate (i) Lower uou11cl litcory and (ii) LJwer bounds for poly1101:1iul evaluation
(b)What arc simplifi',d Nf' hard problems? tv1e1:tit'n a:1y t\\'O NI' [Link] problems and corresponJi11g simplified NP
hard problems.
UNIT· V
9. Compulsory questio11. i\ 1Lc1npt all of the lo\lr,wi11g.
(i) Write a rccu1:sive al gorithm to compute the GCD of'two given integers.
(ii) Write the high lcv~I algorithm for divide :lllJ conquer slrntcgy.
(iii) St~te job scqucnci11g. witli deadlines prnbl,:111.
(iv) What is principle or op:iniality? .
(v) What do yot! 111ea11 by Ha111iltonia11 [Link]?
(vi) Whut arc bounding. funcli-:ms in backtracki•1g? What is their significance?
(vii) Define comparison tree.
(viii) What arc deterministic and 11011 delen11i11islic al;;orithms 9

_j
 [Link]
· Sub. Code: 3893
1058
Master of Computer Application
Third Semester
CS-67: Analysis and Design of Algorithms
Time allowed: 3 Hours Max. Marks: 80
NOTE: Attempt fij.g. questions _in all, including Question No. 9 (Section-£) which is compulsor
and selecting one questwn each from Section A-D. Y
x-x-x
SECTION A

1. (a) What do understand by asymptotic notation? Define and discuss 0, Q and

0 asymptotic notations with examples. 8

(b) What do you understand by best, average and worst .case performance of
algorithms. Discuss with examples. Discuss instances when best and worst
case complexity becomes same. 8

2. (a) What do you under~tand by Divide and Conquer algorithm design

strategy? Discuss Binary Search algorithm t1sing clivide and conquer.
Discuss complexity of this algorithm also. 8

(b) Discuss the meaning and use of selection problem. Discuss and track the ·
!t
algorithm of selection problem for following elements.
65, 70, 75,80,85,60,55,50,45 8

SECTIONB
3. (a) What do you understand by greedy method? Discuss algorithm for Job
Sequencing with Deadlines using greedy method. Discuss the complexity
of algorithm also. 12
(b) What is difference between Prim's and Kruskal's algorithms for finding
4
minimum spanning tree?

What are differences between dynamic programming and divide and

4. (a)
conquer. Also discuss how dynamic programming is a bottom-up
approach? 6
(b) Discuss how the problem of finding Optimal Binary Search Trees is
solved using Dynar~1ic Programming? Discuss algorithm with an example.
Also mention ti1e complexity of the algorithm. 10

SECTIONC

(a) "Backtracking is a modifi~d depth-first search of a tree". Comment and

5.
discuss this [Link] discuss how backtracking helps to reduce state
6
space search.

P·1·o.
 -k
(b) What are Hamiltonian cycles? Discuss an algorithm to find Hamiltonian
cycle in a graph using backtnicking algorithm. Discus algorithm with an
example. Also discuss its complexity. I0

6. What is branch and bound algorithm design technique? Discuss Travelling

Salesman Problem using branch and bound technique with an example. What is
time complexity of this algorithm. 16

SECTIOND
7. What are comparison trees? Discuss the lower bound of sorting and searching
using comparison trees. 16

8 (a) What are differences between deterministic and non deterministic

algorithms? Discus non deterministic algorithm for sorting an an·ay and
also discuss its .complexity. 8
(b) What are P, NP, NP Complete and NP Hard Problems? Give examples of
each. Also discuss what is satisfiability problem? &·

Section E (Compulsory Question)

9. Discuss the followings in short:
(a) Define space and time complexity.
(b) Why Strassen's matrix multiplication is fast?
(c) Differentiate Knapsack problem and 0/1 knapsack problem.
(d) What is time complexity of Travelling Salesman problem using Dynamic
. programming?
(e) Define graph coloring problem with example.
(f) Discuss Breadth First Search is better or Best First Search is better to solve 0/_I
knapsack problem using branch and bound technique.
(g) What do you mean by parallel computation?
(h) State Cook's theorem.
8 X 2=16
 [Link]
Sub. Code: 3893
1129
Master of Computer Applications
Third Semester
CS-67: Analysis and Design of Algorithms
Time allowed: 3 Hours Max. Marks: 80
NOTE: Attempt~ questions in all, including Question No. IX (Unit-VJ which is compulsory
and selecting one question each from Unit I - IV.
x-x-x

UNIT-I
I. a) How best, average and worst cases are computed of an algorithm? Discuss with
examples.

b) Define recurrence equation and explain how solving recurrence equations are done.
(2x8)
II. a) Discuss binary search and Strassen matrix multiplication with examples.
b) Write following in ascending order using merge sort and discuss its complexities:
(55, 35, 80, 77, 50, 95, 70, 60, 82, 72, 79, 66) (2x8)
UNIT-II

III. a) Discuss Knapsack problem and its complexity with example.

b) Discuss the algorithm for minimum cost binary search tree and explain with help
of suitable example. (2x8)

IV. a) Discuss single source shortest path and its complexity? Is it possible to achieve its
complexity less than 0(n\

b) Write short note on job sequencing with deadlines. (2x8)

UNIT-III

V. a) Write short notes on: 8-queen and graph colouring.

b) Discuss efficiency considerations. How it is related to number of computational
resources? (2x8)

VI. a) Investigate branch-and-bound for travelling salesperson problem. Discuss its worst
case complexity as O"'Z"). Can we make it better?

b) Explain the algorithm using backtracking technique to solve Hamiltonian problem.

(2x8)
P.T.O.
 Sub. Code: 3893
(2)

UNIT-IV

VII. a) Write short note using example for techniques for algebraic problems.
a) Differentiate between NP-hard and NP-complete problem. (2x8)

VIII. a) What is Stirling approximation? Discuss lower bound on selection. Can we use
Stirling approximation in lower bound on selection?

b) Justify travelling salesman problem is NP-complete. (2x8)

UNIT-V

IX. Attempt the following:-

a) Write best, average and worst complexities of selection sort, quick sort, heap sort
and merge sort for n elements.
b) Are Greedy methods based on heuristic? Explain.
c) How backtracking methods are linked to recursive working? Discuss with an
example.

d) An NP-hard problem can be solved in deterministic polynomial time/ if yes/ how?

(4x4)

x-x-x