Download VTU BE 2020 Jan CSE Question Paper 17 Scheme 4th Sem 17CS43 Design and Analysis of Algorithms

--- Content provided by⁠ FirstRanker.com ---

7
USN
...
" < CTSG77\
tt%H

--- Content provided by‍ FirstRanker.com ---

,
M5% ,-7 A
(
,?R I'

--- Content provided by FirstRanker.com ---

?
CHIKO'i *

, Il
i

--- Content provided by‌ FirstRanker.com ---

17CS43
.- - 1 . r. ? , , '' ' '
Fourth Semester B.E. Degree Examination, Dee.2019/Jan.2020
Design and Analysis of Algorithms
Time: 3 hrs. Max. Marks: 100

--- Content provided by‌ FirstRanker.com ---

Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
1 a. Explain Asymptotic notations in detail with example. (12 Marks)
b. Outline an algorithm to find maximum of n elements and obtain its time complexity.
(08 Marks)

--- Content provided by‍ FirstRanker.com ---

OR
2 a. Design algorithm for tower of Hanoi problem and obtain time complexity. (10 Marks)
b. Prove the theorem
if fi(n) e 0 (g, (n)) and f2(n) E0 (g2 (n)) Then fi(n) + f2(n) e 0 (max {gi(n),
g2(n))).

--- Content provided by‌ FirstRanker.com ---

(10 Marks)
Module-2
3 a. Design a recursive algorithm for binary search and calculate time complexity. (10 Marks)
b. Write the algorithm for merge sort and Trace 60, 50, 25, 10, 35, 25, 75. 30. (10 Marks)
OR

--- Content provided by⁠ FirstRanker.com ---

4 a. Develop an algorithm for Quick sort and derive its time complexity.
b. What is topological sorting? Apply DFS for below graph to solve topological
(10 Marks)
sorting.
(10 Marks)

--- Content provided by⁠ FirstRanker.com ---

Fig.Q.4(b)
Module-3

5 a. Find the optimal solutio
Object 1 2 3 4 5 6 7

--- Content provided by⁠ FirstRanker.com ---

Weight 02 03 05 07 01 04 01
Profit 10 05 15 07 06 18 03
(10 Marks)
FirstRanker.com - FirstRanker's Choice
Important Note

--- Content provided by⁠ FirstRanker.com ---

(10 Marks)
1 of 2
b. Find the minimum spanning tree using Kruskal's algorithm.
6 1 4
7

--- Content provided by‌ FirstRanker.com ---

USN
...
" < CTSG77\
tt%H
,

--- Content provided by⁠ FirstRanker.com ---

M5% ,-7 A
(
,?R I'

?

--- Content provided by‌ FirstRanker.com ---

CHIKO'i *

, Il
i
17CS43

--- Content provided by FirstRanker.com ---

.- - 1 . r. ? , , '' ' '
Fourth Semester B.E. Degree Examination, Dee.2019/Jan.2020
Design and Analysis of Algorithms
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.

--- Content provided by​ FirstRanker.com ---

Module-1
1 a. Explain Asymptotic notations in detail with example. (12 Marks)
b. Outline an algorithm to find maximum of n elements and obtain its time complexity.
(08 Marks)
OR

--- Content provided by⁠ FirstRanker.com ---

2 a. Design algorithm for tower of Hanoi problem and obtain time complexity. (10 Marks)
b. Prove the theorem
if fi(n) e 0 (g, (n)) and f2(n) E0 (g2 (n)) Then fi(n) + f2(n) e 0 (max {gi(n),
g2(n))).
(10 Marks)

--- Content provided by FirstRanker.com ---

Module-2
3 a. Design a recursive algorithm for binary search and calculate time complexity. (10 Marks)
b. Write the algorithm for merge sort and Trace 60, 50, 25, 10, 35, 25, 75. 30. (10 Marks)
OR
4 a. Develop an algorithm for Quick sort and derive its time complexity.

--- Content provided by⁠ FirstRanker.com ---

b. What is topological sorting? Apply DFS for below graph to solve topological
(10 Marks)
sorting.
(10 Marks)
Fig.Q.4(b)

--- Content provided by‍ FirstRanker.com ---

Module-3

5 a. Find the optimal solutio
Object 1 2 3 4 5 6 7
Weight 02 03 05 07 01 04 01

--- Content provided by‌ FirstRanker.com ---

Profit 10 05 15 07 06 18 03
(10 Marks)
OR
6 a. Construct a Huffman code for the followin data:
Characters A B C D -

--- Content provided by‍ FirstRanker.com ---

Probability 0.4 0.1 0.2 0.15 0.15
Encode the text ABACABAD and decode 100010111001010 (10 Marks)
b.
Calculate the shortest distance and shortest path from vertex 5 to vertex 0 using Dijkstra's.
(10 Marks)

--- Content provided by‍ FirstRanker.com ---

Fig.Q.6(b)
Module-4
7 a. Explain the general procedure to solve a multistage graph problem using backward approach
with an example. (10 Marks)
b. construct an optimal binar

--- Content provided by‌ FirstRanker.com ---

(10 Marks)
OR
8 a. Design Floyd's algorithm to fmd shortest distances from all nodes to all other nodes.
(10 Marks)
b.

--- Content provided by​ FirstRanker.com ---

Apply Warshall's algorithm to compute transitive closure for the graph below. (10 Marks)
Items : A B C D
Probabilities : 0.1 0.2 0.4 0.3
Fig.Q.8(b)
Module-5

--- Content provided by FirstRanker.com ---

9 a. What is Hamiltonian circuit problem? What is the procedure to find Hamiltonian circuit of a
graph? (10 Marks)
b. Explain the classes of NP-Hard and NP-complete. (10 Marks)
OR
10 a. Apply the branch and bound algorithm to solve the travelling salesman problem for the

--- Content provided by​ FirstRanker.com ---

graph below.
Fig.Q.10(a)
(10 Marks)
b. Obtain the optimal solution assignmenproblem given:
J1

--- Content provided by‍ FirstRanker.com ---

J3 J4
a 9 2 7 8
b 6 4 3
c 5 8 1
d 7 6 9 4\

--- Content provided by​ FirstRanker.com ---

* * * * *
2 of 2
(10 Marks)
FirstRanker.com - FirstRanker's Choice