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

(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

This post was last modified on 02 March 2020