Subject Name : Analysis and Design of Algorithm
Subject Code :BCS401
Semester:IV Question Bank: 4
Faculty Name :Prof. SUSHMA M
Academic Year 2024-25 (Even)
Q.No Question bank - Module 4
1
What is greedy method? Give its control abstraction along with its application and characteristics
Solve the following instance of knapsack problem, using greedy algorithm for M=15
2 Item 1 2 3 4 5 6 7
Weight 2 3 5 7 1 4 1
Profit 10 5 15 7 6 18 3
Using greedy algorithm , solve the following instance of knapsack problem, for M=20
3 Item 1 2 3
Weight 30 21 18
Profit 18 15 10
Elaborate the concept of greedy technique for prim’s algorithm. Obtain the minimum cost spanning tree for the graph
below using the same.
Find the minimum spanning tree using Prim’s algorithm for the given graph along with the Algorithm.
Construct the minimum spanning tree using Prim’s algorithm for the given graph along with the Algorithm.
7 Discuss the concept of greedy technique for prim’s algorithm. Obtain the minimum cost spanning tree for the graph
below using the same.
1
Apply kruskal’s algorithm to find the minimum cost spanning tree for the below graph along with the
Algorithm.
Develop the minimum cost spanning tree for the below graph using kruskal’s algorithm along with the
Algorithm.
Using kruskal’s algorithm find the minimum cost spanning tree for the below graph along with the Algorithm.
10
11 Write algorithms for (i) Single sourse shortest path -Dijikstra’s algorithm (ii) Prim’s algorithm (iii) kruskal’s
algorithm
12 Trace the following graph to get the shortest path from vertex a to all other vertices using greedy method
and also write its algorithm
2
In the weighted digraph given below, determine the shortest paths from vertex 6 to all other vertices
13
Solve the below instance of the single source shortest path with vertex a as the source with the help of Dijikstra’s
algorithm.
14
What is Huffman tree? Construct a Huffman tree and resulting code word for the following and Encode the
15 words DAD and ADD
Character A B C D -
Probability 0.35 0.1 0.2 0.2 0.15
Construct a Huffman tree and resulting code word for the following and Encode the words DAD-CBE
16 Character A B C D E -
Probability 0.5 0.35 0.5 0.1 0.4 0.2
3
19 What is the optimal Huffman code for the following set of frequencies based on first 8 Fibonacci numbers:
a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21
Dynamic Programming
1 Elaborate the concept of Dynamic Programming with example
2 Explain the a)Coin row problem b)Change making problem c)Coin collection problem with respective
algorithms.
3 Define Transitive closure. Write Warshall‟s algorithm to compute transitive closure. Find its efficiency.
4 Explain Warshall’s algorithm with its time complexity
Apply Warshall’s Algorithm to find transitive closure of graph defined by the following adjacency matrix.
Using Warshall‟s algorithm to find transitive closure of a digraph
7 Explain all Pair Shortest Path Floyd’s Algorithm with its time complexity
Relate Floyd‟s algorithm to compute all pairs shortest paths for the following graph.
9 Using dynamic programming, solve the following knapsack instance, n=4, m=5 (w1,w2,w3,w4)=(2,1,3,2)
and (v1,v2,v3,v4)=(12,10,20,15)
10 Solve the knapsack instance n=3, (w1,w2,w3)=(1,2,2) and (p1,p2,p3)=(18,16,6) and M=4 by dynamic
programming
4
With the use of bottom up dynamic programming algorithm to the following knapsack problem, knapsack
capacity W=10
11
With the use of bottom up dynamic programming algorithm to the following knapsack problem, knapsack
capacity W=4
12
