Future Vision BIE Future Vision BIE


ONE STOP FOR ALL STUDY MATERIALS & LAB PROGRAMS


E MENU Whatsapp Share Join Telegram, to get Instant Updates
× NOTE! Click on MENU to Browse between Subjects...

Advertisement

DESIGN AND ANALYSIS OF ALGORITHMS

[As per Choice Based Credit System (CBCS) scheme]

(Effective from the academic year 2017 - 2018)

SEMESTER - VI

Subject Code 18CS42

IA Marks 40

Number of Lecture Hours/Week 4

Exam Marks 60



18CS42 - DESIGN AND ANALYSIS OF ALGORITHMS

Important Questions - MODULE - 3



Advertisement

These Questions are being framed for helping the students in the "FINAL Exams" Only (Remember for Internals the Question Paper is set by your respective teachers). Questions may be repeated, just to show students how VTU can frame Questions.

- ADMIN





18CS42 - DESIGN AND ANALYSIS OF ALGORITHMS

Questions Bank - MODULE - 3



Advertisement

1. Find the optimal solution to the knap sack instant n= 7, m= 15 using greedy method. (10 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

Object

1

2

3

4

5

6

7

Weight

02

03

05

07

01

04

01

Profit

10

05

15

07

06

18

03

2. Find the minimum Spanning tree using Kruskal's algorithm. (10 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

Loading Image

Advertisement
3. Construct a Huffman code for the following 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) (Dec.2019/Jan.2020 | 17 Scheme)

4. Calculate the shortest distance and shortest path from vertex 5 to vertex 0 using Dijkstra's. (10 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

Loading Image

5. Write an algorithm to solve knapsack problem using Greedy technique. Find the optimal solution to the knapsack instance n= 7, m= 15

Advertisement

(P1, P2, ……….., P7) =(10, 5, 15, 7, 6, 18, 3)

(W1, W2, ……….., W7 ) = (2, 3, 5, 7, 1, 4, 1) (10 Marks) (June/July 2019 | 17 Scheme)

6. Apply Prim's algorithm and Kruskal's method to find the minimum cost spanning tree to the graph shown in Below Diagram. (08 Marks) (June/July 2019 | 17 Scheme)

Loading Image

7. Write an algorithm to solve single source shortest path problem. Apply the algorithm to the graph shown in Below Diagram by considering 'a' as source. (10 Marks) (June/July 2019 | 17 Scheme)

Loading Image

8. Define heap. Write bottom-up heap construction algorithm. Construct heap for the list 1, 8. 6, 5, 3, 7, 4 using bottom-up algorithm and successive key insertion method, (10 Marks) (June/July 2019 | 17 Scheme)

Advertisement

9. Recall the concept of Greedy technique. (03 Marks) (June/July 2019 | 15 Scheme)

10. In the weighted diagraph given below Figure, determine the shortest paths from vertex '0' to all other vertices. (07 Marks) (June/July 2019 | 15 Scheme)

Loading Image

11. How would you solve the following instance of knapsack problem, using greedy algorithm.

Item

1

2

3

4

Weight

4

7

5

3

Profit

40

42

25

12

Knapsack capacity M = 10. (08 Marks) (June/July 2019 | 15 Scheme)

12. State job sequencing with deadline. Explain algorithm for job sequencing with dead line. (08 Marks) (June/July 2019 | 15 Scheme)

Advertisement

13. Obtain minimum cost spanning tree for the graph given below in Figure, using Prim's algorithm. (08 Marks) (June/July 2019 | 15 Scheme)

Loading Image

14. Explain the concept of greedy technique for Prim's algorithm. Obtain a minimum cost spanning tree for the graph shown in Figure. (08 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

Loading Image

15. Solve the below instance of the single source shortest path problem with vertex 6 as the source. With the help of a suitable algorithm. (08 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

Loading Image

16. What are Huffman trees? Explain. Construct a Huffman code for the following data:

Character

A

B

C

D

E

_

Probability

0.5

0.35

0.5

0.1

0.4

0.2

Encode DAD_CBE using Huffman encoding. (08 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

17. Explain transform and conquer technique. Sort the below list using Heapsort: 3, 2, 4, 1, 6, 5. (08 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

Advertisement

18. Apply greedy method to obtain an optimal solution to the knapsack problem given M = 60, (W1, W2, W3, W4, W5) = (5, 10, 20, 30, 40) (p1, p2, p3, p4, p5) = (30, 20, 100, 90, 160). Find the total profit earned. (04 Marks) (June/July 2018 | 15 Scheme)

19. Explain Huffman algorithm. With an example show the construction of Huffman tree and generate the Huffman code using this tree. (06 Marks) (June/July 2018 | 15 Scheme)

20. Apply Prim's algorithm to obtain a minimum spanning tree for the given weighted connected graph in the Below Figure. (06 Marks) (June/July 2018 | 15 Scheme)

Loading Image

21. Explain the bottom up heap construction algorithm with an example. Give the worst case efficiency of this algorithm. (08 Marks) (June/July 2018 | 15 Scheme)

22. Apply single source shortest path problem assuming vertex a as source. In the Below Figure. (08 Marks) (June/July 2018 | 15 Scheme)

Loading Image

23. Solve the greedy knapsack problem where m= 10, n= 4, P = (40, 42, 25, 12), W = (4, 7, 5, 3). (06 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

24. What is job sequencing with deadlines problem? Let n = 5, profits [10, 3, 33, 11, 40] and deadlines [3, 1, 1, 2, 2] respectively. Find the optimal solution using greedy algorithm. (05 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

Advertisement

25. Define minimum cost spanning tree (MST). Write Prim's algorithm to construct minimum cost spanning tree. (05 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

26. Design Dijkstra's algorithm and apply the same to find the single source shortest path for graph taking vertex 'a' as source of Figure (08 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

Loading Image

27. Construct a Huffman code for the following data:

Character

A

B

C

D

-

Probability

0.4

0.1

0.2

0.15

0.15

Encode the text ABACABAD and decode the text 100010111001010, using the above code. (04 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

28. Construct the heap for the list 2, 9, 7, 6, 5, 8 by the bottom-up algorithm. (04 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

Advertisement

29. Explain Greedy criterion. Write a Prim's algorithm to find minimum cost spanning tree. (08 Marks) (June/July 2017 | 15 Scheme)

30. Sort the given list of numbers using heapsort: 2, 9, 7, 6, 5, 8. (08 Marks) (June/July 2017 | 15 Scheme)

31. Write an algorithm to find single source shortest path. (08 Marks) (June/July 2017 | 15 Scheme)

32. Construct a Huffman tree and resulting code word for the following:

Character

A

B

C

D

-

Probability

0.35

0.1

0.2

0.2

0.15

Encode the word DAD and ADD. (08 Marks) (June/July 2017 | 15 Scheme)

Advertisement

× Note Do You have any Queries, Doubts? Reach us via Mail Or Follow us on Instagram : futurevisionbie

-ADMIN

lIKE THE CONTENT? FOLLOW US ON INSTAGRAM: @futurevisionbie
Get Notified on Instagram Also

ANSWER SCRIP FOR THESE QUESTIONS WILL BE UPLOADED "AS SOON AS POSSIBLE"

Visit: https://hemanthrajhemu.github.io/AnswerScript/

For immediate Notification Join the Telegram Channel





× Note Please Share the website link with Your Friends and known Students...

-ADMIN

× Note Page Number is specified to navigate between Pages...
T = Text book
QB = Question Bank
AS = Amswer Script


-ADMIN

Advertisement