||JAI SRI GURUDEV||

Sri AdichunchanagiriShikshana Trust ®

SJB INSTITUTE OF TECHNOLOGY

(Affiliated to VTU, Approved by AICTE - New Delhi, Accredited by NAAC with “A” Grade)
No. 67, BGS Health & Education City, Dr. Vishnuvardhan Road, Kengeri, Bengaluru - 560 060

Department of Computer Science &Engineering

Module 3
Question Bank

Course Name : Design and Analysis of Algorithms

Course Code : 23CST402
Faculty Name : Dr. Krishna A N, Prof. & Head.
Dr. Arun Kumar D R, Asst. Prof
Mrs. Anusha M, Asst.Prof
 Design and Analysis of Algorithm

MODULE 3
1. State job sequencing with deadline problem. Find the solution generated by job sequencing
problem for
a. A. 7 jobs given profits 3, 5, 20, 18, 1, 6, 30 and deadlines 1, 3, 4, 3, 2, 1, 2
respectively.[Aug/Sept 2020]
b. Jobs n=5, profits= [10,3,3,11, 40] and deadlines = [3,1, 1, 2, 2] respectively.
[Jan/Feb 2021, Feb/Mar 2022]
c. n=5, profits=[10, 30, 60,40] and deadlines=[2, 3, 1, 3] [July/Aug 2022]
2. Explain the concept of Greedy technique for prim’s algorithm. Obtain a minimum cost
spanning tree for the graph below: [Aug/Sept 2020, Jan/Feb 2021]
1 3 60
a b V2 V4 1 2
2 1 2
3 5 5 10
V1 6 20
c 4 d V5 70
2 5 4 3 40
7 8 3
1 4
e V3 V6 50
2 30
(a) (b) 6 5
30
(c)

3. Sort the given list of number using Heap sort.

a. 2, 7, 1, 6, 5, 4, 3. [Aug/Sept 2020]
b. 1, 8, 6, 5, 3, 7, 4. [June/July 2019]
c. 9,7,1,8,3,6,2,4,10,5 [July/Aug 2022]
4. Explain Greedy criterion. Apply greedy methods for the following instance of knapsack
problem. Capacity of knapsack (M)=5.[Aug/Sept 2020, July/Aug 2022]
Item Weight Value Item Weight Profit
1 2 $12 1 1 5
2 1 $10 2 3 9
3 3 $20 3 2 4
4 2 $15 4 2 8

5. Construct a Huffman code for the following data and encode the test BADEC,
ABACABAD and decode 100010111001010.[Dec 2019/Jan 2020, Aug/Sept 2020,
Jan/Feb 2023, Dec 2023/Jan 2024]
Character A B C D E
Probability 0.4 0.1 0.2 0.15 0.15

Dept. of CSE, SJBIT Page 1

 Design and Analysis of Algorithm

6. Write an algorithm to solve knapsack problem using Greedy technique. Find the optimal
solution to the knapsack instance
a. n=7, m=15, (P1,P2,….P7)=(10, 5, 15, 7, 6, 18, 3) (W1,W2, ……,W7)=(2, 3, 5, 7,
1, 4, 1)[June/July 2019, Dec 2019/Jan 2020, July/ August 2022, Jan/Feb 2023,
Dec 2023/Jan 2024]
b. n=5, m=6,(P1,P2,….P5)=(25, 20, 15, 40, 50) (W1,W2, ……,W5)=(3, 2, 1, 4,
5)[Feb/Mar 2022]
c. n=3, m=20, w1,w2,w3=(18,15,10), v1,v2,v3=(30,21,18)[June/July 2023]
7. Solve the below instance of single source shortest path problem with vertex a as the
source.[June/July 2019, Aug/Sept 2020, Jan/Feb 2021, July/ August 2022]
4 4
b 6 c b c
6 3 6
5
6 2
a 5 2 6
a d e
6 7 4
7 (b)
d 4 e
(a)
6
8. Apply Prim’s algorithm and Kruskal’s method to find the minimum cost spanning tree to the graph
shown below: [June/July 2019, July/August 2022, June/July 2023]

5
a b
2 3
7 e 6
4 5

c 4 d

(a)

9. Find the minimum spanning tree using Kruskal’s algorithm.[Dec 2019/Jan 2020, Jan/Feb
2023]
16 14
8 1 2 3
4
0 22 8 28 4
8

16 14 12
7 2 6 4 5

(a)

10. Define heap. Write bottom up heap construction algorithm.

Dept. of CSE, SJBIT Page 2

 Design and Analysis of Algorithm

(a) Construct heap for the list 2, 6, 9, 8, 3, 7, 4 using bottom up algorithm. [Jan/Feb 2021,
July/ August 2022,Feb/Mar 2022]
(b) Apply both bottom up and top down methodnto construct the max heap for the data: 12,
23, 45, 28, 55, 15, 67, 33. [Dec 2023/Jan 2024]
11. A message consisting of the characters given in the table below has to be trans network in a
secured manner.
Character A M R -
Probability 0.4 0.2 0.3 0.1
(a) Construct Huffman tree for the given characters (Branch label: left (0), right(1))
(b) Device Huffman codes for the given character.
(c) Encode the text RAMA RAMAR using Huffman codes.
(d) Decode the text whose encoding is 1000101
(e) Compute the effectiveness of Huffman codes. [Feb/Mar 2022]
12. Construct the Huffman tree and resulting code word for the following set of values
Character A B C D -
probability 0.35 0.1 0,2 0.2 0.15
Encode the word DAD & ADD. [Jan/Feb 2021]
13. Differentiate between Prim’s and Kruskal’s algorithm. [Feb/Mar 2022]
14. Explain coin change problem with example. [Jan/Feb 2023]
15. Write an algorithm for minimum spanning tree using Prim’s. [Jan/Feb 2023]
16. A document contains the letter “A” through “E” with frequencies is follows:
A:22, B:13, C:18, D:16, E:31
Construct the Huffman tree and codes and
Encode: CAB, ADD, BAD, ACE
Decode: 110011 and 1000110001 [July/Aug 2022]
17. Calculate the shortest distance and shortest path from
(a) vertex 5 to vertex 0 using Dijkstra’s.[Dec 2019/Jan 2020][
(b) source node is G. Feb/Mar 2022]

45 3 2
A B C
15 20
0 1 4 4 2 3
3 1
30 D E F
20 10 15
10
35 3 5 3
2 4
20 4 G H I
2 3 5

(a) (b)

Dept. of CSE, SJBIT Page 3