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
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
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)
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
(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)
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)
-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
-ADMIN
T = Text book
QB = Question Bank
AS = Amswer Script
-ADMIN