R.M.K.

ENGINEERING COLLEGE
(An Autonomous Institution)
RSM Nagar, Kavaraipettai– 601 206

Question Bank for the Units – I to V

SE00
4th Semester – B.E. / B.Tech.

Computer Science and Engineering / Artificial Intelligence and Data Science

BR00
/ Computer Science and Design

20CS402 – Design and Analysis of Algorithms

SU00

CO1# Analyse the efficiency of recursive and non-recursive algorithms mathematically

Analyse the efficiency of brute force, divide and conquer, decrease and conquer, Transform and conquer
CO2# algorithmic techniques

Implement and analyse the problems using dynamic programming and greedy technique algorithmic
CO3# techniques

CO4# Solve the problems using iterative improvement technique for optimization.

Compute the limitations of algorithmic power and solve the problems using backtracking and branch and
CO5# bound technique.

CO6#

Part-A (10 x 2 = 20 Marks) K S

Lev CO /
el A

1. Write Euclid’s algorithm to find the GCD of two numbers. K1 CO1 S

1. List out the different methods to represent the algorithm. K1 CO1 S

1. What are the two kinds of algorithm efficiency? K1 CO1 S

1. List out the characteristics of an algorithm. K1 CO1 S

1. Define algorithm K1 CO1 A

2. What is the basic operation? K1 CO1 S

2. What is recurrence relation? Give example. K1 CO1 A

2. What is the best, worst and average case time complexity of linear search K1 CO1 A
algorithm?
2. How to measure the efficiency of an algorithm? K1 CO1 S

2. Write the recurrence relation for the Towers of Hanoi K1 CO1 S

3. What is Brute Force approach? K1 CO2 A

3. State Master Theorem. K1 CO2 S

3. What is an exhaustive search? K1 CO2 A

3. Write down the general concept of Divide and Conquer K1 CO2 S

3. What is the time complexity of binary search algorithm? K1 CO2 A

4. What is the time complexity of multiplication of large integers? K1 CO2 A

4. Differentiate merge sort and quick sort. K2 CO2 S

4. Define decrease and conquer. K1 CO2 A

4. Define Josephus Problem. K1 CO2 S

4. Define transform and conquer. K1 CO2 S

5. Differentiate dynamic programming and greedy technique. K2 CO3 S

5. Define principle of optimality. K1 CO3 S

5. Define multi stage graph. K1 CO3 S

5. What is the use of memory functions? K1 CO3 S

5. Define minimum spanning tree. K1 CO3 S

6. What is 0/1 knapsack problem? K1 CO3 A

6. Define longest common subsequence problem. K1 CO3 S

6. Define Huffman tree. K1 CO3 A

6. Give the recurrence for matrix chain multiplication. K1 CO3 A

6. What is the difference between fixed length encoding and variable length K1 CO3 S
encoding?

7. State extreme point theorem. K1 CO4 S

7. Define pivot row, pivot column and pivot element. K1 CO4 A

7. Define flow network. K1 CO4 S

7. Write down the flow-conservation requirement. K1 CO4 S

7. What is capacity constraint? K1 CO4 S

8. Differentiate stable and unstable matching K2 CO4 S

8. What is maximum cardinality matching? K1 CO4 S

8. Define Bipartite graph. K1 CO4 A

8. Define 2-colorable graph. K1 CO4 A

8. Define blocking pair. K1 CO4 S

9. What is state space tree? K1 CO5 S

9. Differentiate promising and non-promising nodes. K2 CO5 A

9. What is Hamiltonian cycle? K1 CO5 S

9. Differentiate backtracking with branch and bound. K2 CO5 A

9. Define P, NP, NP-complete problems. K1 CO5 S

10. Define accuracy ratio. K1 CO5 A

10. Define halting problem. K1 CO5 S

10. What are deterministic and non-deterministic algorithms? K1 CO5 S

10. Define tractable and intractable problems. K1 CO5 S

10. State the reasons for terminating the search path at the current node K1 CO5 S

Part – B ( 5 x 13 = 65 Marks)

11.a. Explain in detail the fundamental procedure for algorithmic problem solving.
K2 CO1 A
(13)

11.a. Explain briefly Big oh Notation, Omega Notation and Theta Notations. Give
K2 CO1 S
examples. (13)

11.a. Write short note on the following with examples

(i) O notation (4)
K2 CO1 S
(ii) Ω notation (4)
(iii) Θ notation (5)

11.a. (i) Explain the basic asymptotic notations. (9)

(ii) Prove that “If t1(n) ε O(g1(n)) and t2(n) ε O(g2(n)) then t1(n)+t2(n) ε K2 CO1 S
O(max{g1(n), g2(n)})”. (4)

11.a. Explain about the algorithmic problem-solving steps. (13) K2 CO1 A

11.b. (i) Sketch an algorithm for multiplying two matrices and find its time complexity.
(7) K4 CO1 S
(ii)Write the general plan for analysing non-recursive algorithms (6)
11.b. Discuss the steps in mathematical analysis for recursive algorithms. Design and
K2 CO1 S
analyse the algorithm for finding factorial of a number. (13)

11.b. Examine the steps in detail to mathematically analyze recursive algorithms to find
the number digits in n’s binary representation, where n is a positive decimal
K4 CO1 S
integer. Find the recurrence relation and time complexity.
(13)

11.b. Sketch the general plan for analysing the time efficiency of recursive algorithms
and solve the recurrence relation to find the number of moves in Towers of Hanoi K3 CO1 S
problem. (13)

11.b. Sketch the general plan to mathematically analyze any non-recursive algorithms.
Analyze the algorithm to check whether all the elements in an array are distinct. K3 CO1 S
(13)

12.a. Describe the knapsack problem and find the optimal solution to the knapsack
problem with the given data W=5 (13)
Items Weight Value
1 2 12
K2 CO2 A
2 1 10
3 3 20
4 2 15

12.a. Write and analyse the algorithm for convex hull by applying brute force technique.
K2 CO2 A
(13)

12.a. Discuss Travelling Salesman Problem. Suggest an optimal tour for a salesman
using exhaustive search. (13)

4
2
3
5
K2 CO2 A
7
1 3 6

8
2 4
5 3

12.a. Solve the following assignment problem by exhaustive search. There are 4
people who need to be assigned to execute 4 jobs (one person per job) and the
problem is to find an assignment with the minimum total cost. The assignment
costs are given below:
Job1 Job2 Job3 Job4 K3 CO2 A
Person1 9 2 7 8
Person2 6 4 3 7
Person3 5 8 1 8
 Person4 7 6 9 4 (13)

12.a. Sketch an algorithm using brute force approach for string pattern matching and
K3 CO2 A
analyse it. (13)

12.b. Explain the working of Merge Sort algorithm for the following example
K2 CO2 S
8,3,2,9,7,1,5,4. (13)

12.b. (i) Sketch the merge sort algorithm. (7)

(ii) Sort the following set of elements using merge sort: 12, 24, 8, 71, 4, 23, 6, 89, K3 CO2 S
56. (6)

12.b. Discuss the basic principle behind Quick sort. Use the technique to solve the
following numbers in an increasing order. 89, 45, 68, 90, 29, 34,17, 57. K2 CO2 S
(13)

12.b. Compute the time efficiency of binary search algorithm in divide and conquer
K3 CO2 S
approach. Illustrate with an example. (13)

12.b. Sketch heapsort algorithm and apply to the following input to sort.
K3 CO2 S
84, 42, 61, 92, 28, 34,19. (13)

13.a. Apply the bottom-up dynamic programming algorithm to the following instance
of the knapsack problem: (13)

Item weight value

1 4 $10 K3 CO3 S
3 3 $20
3 2 $15
4 5 $25
Capacity W = 5

13.a. Solve the all-pairs shortest path problem for the digraph (13)

K3 CO3 S

13.a. Write the backward approach algorithm and solve the graph using backward
K3 CO3 S
approach. (13)
13.a. Write the forward approach algorithm and solve the graph using forward
approach (13)

K3 CO3 S

13.a. Apply the bottom-up dynamic programming algorithm to the following instance
of the knapsack problem: (13)
Item weight value
1 3 $25
K3 CO3 S
2 2 $20
3 1 $15
4 4 $40
5 5 $50 capacity W = 6.

13.b. Discuss about the algorithm and pseudo code to find the Minimum Spanning
Tree using Prim’s Algorithm. Find the Minimum Spanning Tree for the graph
shown below. Discuss about the efficiency of the algorithm. (13)

K2 CO3 A

13.b. Construct a Huffman tree K6 CO3 S

 (a) Encode the characters DAD
(b) Decode the bitstring 1001101
(c) Find the Compression ratio (13)

13.b. Construct a Huffman tree and find the Huffman codes for the given characters.
Determine the compression ratio. (13)
Character Frequency
A 5
B 9 K6 CO3 S
C 12
D 13
E 16
F 45

13.b. Write and apply Kruskal’s Algorithm to find the minimum spanning tree (13)

K2 CO3 A

13.b. Construct a Huffman tree and find the Huffman codes for the given characters.
Determine the compression ratio. (13)
K6 CO3 S

14.a. Apply shortest augmenting path method to the network to find the max flow and
min cut. (13)

K3 CO4 S

14.a. Apply Ford-Fulkerson method to the network to find the max flow and min cut
K3 CO4 S
(13)
14.a. Apply the first-labelled-first scanned algorithm to find the maximum flow in the
given graph and write down the shortest augmenting path algorithm. (13)

K3 CO4 S

14.a. Apply the first-labelled-first-scanned algorithm to find the maximum flow in the
given graph and write down the shortest augmenting path algorithm (13)

K3 CO4 S

14.a. Apply the Ford-Fulkerson algorithm to find the maximum flow in the given
graph and write down the shortest augmenting path algorithm. (13)

K3 CO4 S
14.b. Use the maximum matching algorithm to the following Bipartite graph and find
the maximum matching (13)

K3 CO4 A

14.b. Find a stable marriage matching for the instance defined by the following
ranking matrix (13)

K2 CO4 S

14.b. Apply the Gale Shapley algorithm and find a stable marriage matching for the
instance defined by the following ranking matrix (13)

Preferences of α, β, γ and δ

1 2 3 4
α A B C D
β A D C B
γ B A C D
δ D B C A
K3 CO4 S
Preferences of A, B, C and D

1 2 3 4
A δ γ α β
B β δ α γ
C δ α γ β
D γ β α δ
14.b. Apply maximum matching algorithm to find the maximum matching in the
following graph. (13)

K3 CO4 S

14.b. Write the ranking matrix from the given preference list. Use the stable marriage
algorithm to find the stable matching. (13)

K3 CO4 S

15.a. Explain the N Queens problem with n=4. Draw the state space tree (13) K2 CO5 S

15.a. Explain the N Queens problem with n=8. Draw the state space tree (13) K2 CO5 S

15.a. Solve the following sum of subset problem and draw the neat state space tree
K3 CO5 S
S={1,2,3,5,6,8} and d=9 (13)

15.a. Discuss the Hamiltonian circuit problem using backtracking technique and find
the Hamiltonian circuit in the following graph (13)

K2 CO5 S

15.a. Solve the following sum of subset problem and draw the neat state space tree
K3 CO5 S
S = {3,4,7,8} and d=15 (13)

15.b. Find the optimal solution for the assignment problem given below using branch
K2 CO5 S
and bound technique. (13)
 Job1 Job2 Job 3 Job 4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4

15.b. Apply branch and bound algorithm and find the minimum cost tour in the
following graph (13)

K2 CO5 S

15.b. Apply branch and bound algorithm and find the minimum cost tour in the
following graph (13)

K2 CO5 S

15.b. Find the optimal solution for the assignment problem given below using branch
and bound (13)
Job1 Job2 Job 3 Job 4
Person1 4 3 8 6
K2 CO5 S
Person2 5 7 2 4
Person3 16 9 3 1
Person4 2 5 3 7

15.b. Explain the following approximation algorithms for traveling salesman problem
with suitable examples
(i) Nearest neighbour algorithm (3) K2 CO5 S
(ii) Multi Fragment Heuristic algorithm (5)
(iii) Twice Around the tree algorithm (5)
 Part – C ( 1 x 15 = 15 Marks)

16.a. Explain the method used for performing multiplication of two large integers and
Multiply 1130 * 2403 using divide and conquer. (15) K2 CO2 A

16.a. Apply the algorithm OptimalBST to construct the optimal binary search tree for
the given data (15)
K3 CO3 S
Key else if int while
Prob 0.1 0.2 0.4 0.3

16.a. Solve using Simplex method (15)

Maximize Z = 3 x1 + 5 x2
Subject to x1 + x2 ≤ 8, K3 CO4 S
x1 + 3 x2 ≤12
x1, x2 ≥ 0.

16.a. Solve using simplex method (15)

Maximize 3x + 4y
subject to x + 3y ≤ 30 K3 CO4 S
2x + y ≤ 20
x,y≥0

16.a. Solve using Simplex method (15)

Maximize Z = 6x1 + 8 x2
Subject to 5 x1 +10 x2 ≤ 60, K3 CO4 S
4 x1 + 4 x2 ≤40
x1, x2 ≥ 0.

16.b. Solve the given instance of the Knapsack problem using branch and bound
technique (15)
n=4
Item weight value
K3 CO5 S
1 10 100
2 7 63
3 6 56 W=16
4 3 12

16.b. (i) Given two strings X = BACDB and Y = BDCB to find the longest common
subsequence using Dynamic Programming. (7)
K3 CO3 S
(ii) Consider the chain A1, A2, A3, A4 of 4 matrices. Explain the Possible ways of
Matrix Chain Multiplication.
A1 = 3x2, A2 = 2x4, A3 = 4x2, A4= 2x5 (8)

16.b. Solve the following recurrence relations

(i). x(n) = x(n − 1) + n for n > 0, x(0) = 0 (5)
K3 CO1 S
(ii). x(n) = x(n/2) + n, for n > 1, x(1) = 1 (solve for n = 2k) (5)

(iii). x(n) = x(n/3) + 1, for n > 1, x(1) = 1 (solve for n = 3k) (5)
16.b. Solve the given instance of the Knapsack problem using branch and bound
technique (15)
n=4
Item weight value
K3 CO5 S
1 4 40
2 7 42
3 5 25 W=10
4 3 12

16.b. Solve the following Travelling Salesman Problem using dynamic programming
to find the minimum cost path. (15)

1 2 3 4
K3 CO3 S
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0