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)

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)

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

(P₁, P₂, ……….., P₇) =(10, 5, 15, 7, 6, 18, 3)

(W₁, W₂, ……….., W₇ ) = (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)

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)

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)

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)

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)

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

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)

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)

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)

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)

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)

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)

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)

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)

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)