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

Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2017 Scheme 2020 January Previous Question Paper 4th Sem 17CS43 Design and Analysis of Algorithms

Important Note
(10 Marks)
1 of 2
b. Find the minimum spanning tree using Kruskal's algorithm.
6 1 4
7
USN
...
" < CTSG77\
tt%H
,
M5% ,-7 A
(
,?R I'

?
CHIKO'i *

, Il
i
17CS43
.- - 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.
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
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)
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.
b. What is topological sorting? Apply DFS for below graph to solve topological
(10 Marks)
sorting.
(10 Marks)
Fig.Q.4(b)
Module-3

5 a. Find the optimal solutio
Object 1 2 3 4 5 6 7
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
(10 Marks)
1 of 2
b. Find the minimum spanning tree using Kruskal's algorithm.
6 1 4
7
USN
...
" < CTSG77\
tt%H
,
M5% ,-7 A
(
,?R I'

?
CHIKO'i *

, Il
i
17CS43
.- - 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.
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
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)
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.
b. What is topological sorting? Apply DFS for below graph to solve topological
(10 Marks)
sorting.
(10 Marks)
Fig.Q.4(b)
Module-3

5 a. Find the optimal solutio
Object 1 2 3 4 5 6 7
Weight 02 03 05 07 01 04 01
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 -
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)
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
(10 Marks)
OR
8 a. Design Floyd's algorithm to fmd shortest distances from all nodes to all other nodes.
(10 Marks)
b.
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
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
graph below.
Fig.Q.10(a)
(10 Marks)
b. Obtain the optimal solution assignmenproblem given:
J1
J3 J4
a 9 2 7 8
b 6 4 3
c 5 8 1
d 7 6 9 4\
* * * * *
2 of 2
(10 Marks)
FirstRanker.com - FirstRanker's Choice