Total No. of Questions : 10] SEAT No.

P3394 [Total No. of Pages : 3

[5353] - 598

2
7:2
T.E. (Information Technology) (Semester - II)

3:5
DESIGN AND ANALYSIS OF ALGORITHMS

81
91
(2015 Pattern)

01
30
5/2
Time : 2½ Hours] [Max. Marks : 70
.19 01
Instructions to the candidates:1/0
P
1) Answer Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8, Q.9 or Q.10.
72
3.1 G

2) Neat diagrams must be drawn wherever necessary.

CE

3) Figures to the right side indicate full marks.

14

4) Assume suitable data if necessary.

:22
7.3

Q1) a) Write an algorithm to solve 8 queen’s problem using Brute force method.

:57
15

[5]

3
81
5/2 1
b) Let n = 3 and (11, 12, 13) = (5, 10, 3) find the optimal ordering on tapes
9
01
using Greedy method. [5]
7 2 30
.19 01
1/0

OR
P

Q2) a) Prove by mathematical induction that for each positive number n

3.1 G

1+2+3+.......+n=n(n+1)/2. [5]
7.3 CE
14

b) Write an algorithm for finding the maximum and minimum element using
divide and conquer and verify its complexity. [5]
2
7:2
15

3:5

Q3) a) Find the solution of following travelling salesman problem using dynamic
81
5/2 1

programming. [8]
9
01
7 2 30
1
1/0
G P0.19
CE
14
3.1

b) Define greedy method. [2]

7.3
15

P.T.O.
 OR
Q4) Find the minimum cost path from source (s) to sink (t) of the following
multistage graph. [10]

2
7:2
3:5
81
91
01
30
5/2
.19 01
1/0
P
72
3.1 G
CE
14

:22
7.3

:57
15

3
81
5/2 1
9
01
7 2 30

Q5) a) Write a recursive and Iterative algorithm of backtracking method. [8]

.19 01

b) Let W = {5, 10, 12, 13, 15, 18} and M = 30. Find all possible subsets of
1/0

W that sum to M. Draw the portion of state space tree. [8]

3.1 G
P

OR
7.3 CE

Q6) a) Write an algorithm for backtracking solution to the 0/1 knapsack problem.
14

[8]
b) Explain the following terms :
2 [8]
7:2

i) State space tree.

15

3:5

ii) Live node.

81
5/2 1
9

iii) E-node.
01
7 2 30

iv) Dead node.

1
1/0
P0

Q7) a) Solve the following instance of 0/1 knapsack problem by LC branch and
G

bound approach [10]

.19
CE

N = 4, (p1, p2, p3, p4) = (10, 10, 12, 18)

14

(w1, w2, w3, w4) = (2, 4, 6, 9) and M = 15

3.1

b) Write an algorithm for FIFO branch and bound. [8]

7.3
15

[5353]-598 2
 OR
Q8) a) What is travelling salesman problem? Find the solution of the following
travelling salesman problem using branch and bound method. [12]

2
7:2
3:5
81
91
01
30
5/2
.19 01
1/0
P
72
3.1 G

b) Explain the following terms: [6]

CE
14

i) Branch and bound.

ii) LC search.

:22
7.3

iii) Bounding Function.

:57
15

3
81
5/2 1
Q9) a) What is Nondeterministic algorithm? Write the Nondeterministic algorithm
9
01
7 2 30

for sorting the element of an array. [8]

.19 01

b) Explain complexity classes P and NP. And differentiate between NP

1/0

complete and NP Hard. [8]

3.1 G
P

OR
7.3 CE

Q10) a) Prove that Clique Decision problem is NP complete. [8]

14

b) Explain the Flynn’s classification for Parallel Computing. [8]

2
7:2
15

ZZZ
3:5
81
5/2 1
9
01
7 2 30
1
1/0
G P0.19
CE
14
3.1
7.3
15

[5353]-598 3
 15 CE
7.3
3.1 G
14 P
.19 01
72 30
1/0 91
15 5/2
7.3 CE 01
3.1 G 81
14 P
.19 01
3:5
7:2
7 2 30 2
1/0 9
5/2 1
15
7.3 CE 01
3.1 G 81
3
14 P0 :57
.19 1
7 2 30 :22
1/0 9
5/2 1
01
81
3:5
7:2
2