Download JNTUA MCA 2019 May Reg-Supply 4th Sem 17F00402 Design and Analysis of Algorithms Question Paper

Download JNTU Anantapur (JNTU Anantapur) Master of Computer Applications (MCA) 2019 May Reg-Supply 4th Sem 17F00402 Design and Analysis of Algorithms Previous Question Paper

Code: 17F00402

MCA IV Semester Regular Examinations May 2019
DESIGN & ANALYSIS OF ALGORITHMS
(For 2017 admitted batches only)

Time: 3 hours Max. Marks: 60

Answer all the questions

*****
1 (a) Apply Strassen?s algorithm to compute matrix multiplication, using 2 X 2 matrices, exiting
the recursion when n = 2.
?
1
4
0
5

0
1
1
0

2
1
3
2

1
0
0
1
? ? ?
0
2
2
1

1
1
0
3

0
0
1
5

1
4
1
0
?
(b) Explain the concept of divide and conquer.
OR
2 (a) Illustrate the tracing of Quick Sort algorithm for the following set of numbers:
18, 25, 18, 40, 11, 37, 32, 9
(b) Explain best case, average case and worst case efficiencies for quick sort with specific
examples.

3 (a) Write an algorithm to find single source shortest paths.
(b) Obtain the optimal solution for the job sequencing problem with deadline where n = 4 Profit
(P1, P2, P3, P4) = {100, 10, 15, 17} and deadlines = {2, 1, 2, 1}.
OR
4 (a) Write an algorithm, to find the minimum cost spanning tree using Kruskal?s method. Apply
the algorithm on the graph shown below.

(b) Write a note on travelling sales person problem.

5 (a) What is graph traversal? Explain depth first traversal and breadth first traversals, with an
example.
(b) What is a Hamilton cycle? Give an example.
OR
6 (a) Explain back tracking concept and apply it to solve subset sum problem for S = {6, 5, 3, 7}
and d = 15.
(b) Explain Bi-connected components of a graph with a suitable example.
Contd. in page 2








Page 1 of 2
b a
c d
e
5
2
3
2 4
4
FirstRanker.com - FirstRanker's Choice
Code: 17F00402

MCA IV Semester Regular Examinations May 2019
DESIGN & ANALYSIS OF ALGORITHMS
(For 2017 admitted batches only)

Time: 3 hours Max. Marks: 60

Answer all the questions

*****
1 (a) Apply Strassen?s algorithm to compute matrix multiplication, using 2 X 2 matrices, exiting
the recursion when n = 2.
?
1
4
0
5

0
1
1
0

2
1
3
2

1
0
0
1
? ? ?
0
2
2
1

1
1
0
3

0
0
1
5

1
4
1
0
?
(b) Explain the concept of divide and conquer.
OR
2 (a) Illustrate the tracing of Quick Sort algorithm for the following set of numbers:
18, 25, 18, 40, 11, 37, 32, 9
(b) Explain best case, average case and worst case efficiencies for quick sort with specific
examples.

3 (a) Write an algorithm to find single source shortest paths.
(b) Obtain the optimal solution for the job sequencing problem with deadline where n = 4 Profit
(P1, P2, P3, P4) = {100, 10, 15, 17} and deadlines = {2, 1, 2, 1}.
OR
4 (a) Write an algorithm, to find the minimum cost spanning tree using Kruskal?s method. Apply
the algorithm on the graph shown below.

(b) Write a note on travelling sales person problem.

5 (a) What is graph traversal? Explain depth first traversal and breadth first traversals, with an
example.
(b) What is a Hamilton cycle? Give an example.
OR
6 (a) Explain back tracking concept and apply it to solve subset sum problem for S = {6, 5, 3, 7}
and d = 15.
(b) Explain Bi-connected components of a graph with a suitable example.
Contd. in page 2








Page 1 of 2
b a
c d
e
5
2
3
2 4
4
Code: 17F00402


7 Explain how branch and bound is different from backtracking. Solve the following instance of
the 0/1 knapsack problem by Branch and bound algorithm (W = 16).
Item Weight Value
1 10 $100
2 7 $63
3 8 $56
4 4 $12

OR
8 (a) What is a comparison tree? Draw the comparison tree for sorting three elements.
(b) Show how to invert a lower triangular matrix using lower bound theory.

9 Give and explain the relationship between P, NP, NP-complete and NP hard problems.
OR
10 Write short notes on the following NP-complete problems:
(a) Node cover.
(b) Hamilton circuit problem.
(c) Graph coloring problem.

*****


































Page 2 of 2
FirstRanker.com - FirstRanker's Choice