PKM Educational Trust ®

R.R. Institute of Technology

Affiliated to VTU Belgaum and Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka
Accredited by NAAC with ‘A+’, NBA
Raja Reddy Layout, Chikkabanavara, Bengaluru – 560 090
Department of Computer Science & Engineering

Question Bank_ MODULE 1

Subject Name: Design and Analysis of Algorithms Subject Code: BCS401

Course Learning Objectives: This course (BCS401) will enable students to:

✓ To learn the methods for analyzing algorithms and evaluating their performance.
✓ To demonstrate the efficiency of algorithms using asymptotic notations.
✓ To solve problems using various algorithm design methods, including brute force, greedy,
divide and conquer, decrease and conquer, transform and conquer, dynamic programming,
backtracking, and branch and bound.
✓ To learn the concepts of P and NP complexity classes.
Q. No Question COs

1 Define algorithm. Explain asymptotic notations Big Oh, Big Omega and Big Theta notations CO1

Explain the general plan for analyzing the efficiency of a recursive algorithm. Suggest a CO1
2
recursive algorithm to find factorial of number. Derive its efficiency
If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then show that t1(n) + t2(n) ∈ O(max{g1(n), CO1
3
g2(n)}).
CO1
4 With neat diagram explain different steps in designing and analyzing an algorithm

Explain the general plan for analyzing the efficiency of a non-recursive algorithm. Suggest a CO1
5 non-recursive algorithm to find maximum element in the list of n numbers. Derive its
efficiency
CO1
6 With the algorithm derive the worst-case efficiency for Bubble sort
Write the algorithm to find maximum element in the given array and explain the CO1
7
mathematical analysis of this non-recursive algorithm.
Write the algorithm to check whether all the elements in the given array are distinct and explain CO1
8 the mathematical analysis of this non- recursive algorithm. Derive its worst-case time
complexity.
Write the algorithm to perform matrix multiplication and explain the mathematical analysis CO1
9
of this non-recursive algorithm
Explain general plan of mathematical analysis of recursive algorithms CO1
10
with example
Illustrate mathematical analysis of recursive algorithm for Towers of Hanoi OR CO1
11 Give the recursive algorithm to solve Tower of Hanoi problem. Show that the efficiency of
this algorithm is exponential
Illustrate mathematical analysis of recursive algorithm to find the factorial of a given CO1
12
number.
Develop an algorithm to search an element in an array using sequential search. Calculate the CO1
13
best case, worst case and average case efficiency of this algorithm.
List the following functions according to their order of growth from lowest to highest. State CO1
proper reasons,
14
(n-2)!, 5 log (n+100)10, 22n , 0.001n4 +3n3+1, ln2 n, 3√n, 3n

Write an algorithm for Selection sort trace its working for the given elements and also CO1
analyze its efficiency.
15
Given array: [89, 45, 68, 90, 29, 34, 17]
Explain Brute Force String matching problem with an example Write an algorithm for same CO1
16 and analyze its efficiency.

Course Outcomes: Students will be able to

Apply asymptotic notational method to analyze the performance of the algorithms in terms of time
CO-1:
complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
CO-2:
computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given
CO-3:
real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational
CO-4:
problems.
CO-5: Analyse various classes (P,NP and NP Complete) of problems
CO-6: Illustrate backtracking, branch & bound and approximation methods.

Course In-Charge HOD

PKM Educational Trust ®

R.R. Institute of Technology

Affiliated to VTU Belgaum and Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka
Accredited by NAAC with ‘A+’, NBA
Raja Reddy Layout, Chikkabanavara, Bengaluru – 560 090
Department of Computer Science & Engineering

Question Bank_ MODULE 2

Subject Name: Design and Analysis of Algorithms Subject Code: BCS401

Course Learning Objectives: This course (BCS401) will enable students to:

✓ To learn the methods for analysing algorithms and evaluating their performance.
✓ To demonstrate the efficiency of algorithms using asymptotic notations.
✓ To solve problems using various algorithm design methods, including brute force, greedy,
divide and conquer, decrease and conquer, transform and conquer, dynamic programming,
backtracking, and branch and bound.
✓ To learn the concepts of P and NP complexity classes.
Q. No Question COs

Explain the concept of divide and conquer. Design an algorithm for merge sort and derive its CO2
1
time complexity
Design an insertion sort algorithm and obtain its time complexity. Apply insertion sort on CO2
2
these elements. 25,75,40,10,20,
CO2
3 Explain Strassen’s matrix multiplication and derive its time complexity
Design an algorithm for quick sort algorithm. Apply quick sort on these elements. CO2
4
25,75,40,10,20,05,15
5 Explain divide and conquer algorithm with its advantages and disadvantages CO2
Explain in detail about the Travelling Salesman Problem using exhaustive search CO2
6
Explain in detail about the Knapsack Problem using exhaustive search CO2
7
Write the algorithm to find maximum and minimum element in the given array and explain CO2
8
the mathematical analysis of the recursive algorithm
Design an insertion sort algorithm and obtain its time complexity. Apply insertion sort on CO2
9
these elements. 25,75,40,10,20,
Explain the concept of divide and conquer. Design an algorithm for merge sort and derive its CO2
10
time complexity
Explain Strassen’s matrix multiplication and derive its time complexity CO2
11
Design an algorithm for quick sort algorithm. Apply quick sort on these elements. CO2
12
25,75,40,10,20,05,15
Apply the quick sort algorithm to sort the list of characters :P,R,O,G,R,A,M,M,I,N,G.Draw CO2
13
the tree of recursive calls made while tracing
Define Topological Sorting .Illustrate the a) topological sorting for the following graph. CO2
b)DFS

14

Design an algorithm for DFS and BFS traversal methods. Comment on its efficiency. Apply CO2
the same for the given graph

15

Define Topological Sorting. Illustrate the a) topological sorting for the following graph. CO2

16

Write the recursive algorithm to perform the binary search on the list of elements. CO2
17
Explain Strassen’s matrix multiplication and derive its time complexity CO2
18
What is a Quick Sort Algorithm? Apply a quick sort algorithm to sort the list E, X, A, M, P, CO2
19
L, E in alphabetical order. Draw the tree of recursive calls made
Design merge sort algorithm. Write a descriptive note on its best case, average case, and CO2
20
worst-case time efficiency
Distinguish Between decrease and conquer and divide and conguer algorithm design CO2
21
technique with block diagram
Define Topological sorting. List the two approaches of topological sorting and illustrate with CO2
22
examples

Course Outcomes: Students will be able to

Apply asymptotic notational method to analyze the performance of the algorithms in terms of time
CO-1:
complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
CO-2:
computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given
CO-3:
real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational
CO-4:
problems.
CO-5: Analyse various classes (P,NP and NP Complete) of problems
CO-6: Illustrate backtracking, branch & bound and approximation methods.

Course In-Charge HOD

PKM Educational Trust ®

R.R. Institute of Technology

Affiliated to VTU Belgaum and Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka
Accredited by NAAC with ‘A+’, NBA
Raja Reddy Layout, Chikkabanavara, Bengaluru – 560 090
Department of Computer Science & Engineering

Question Bank_ MODULE 3

Subject Name: Design and Analysis of Algorithms Subject Code: BCS401

Course Learning Objectives: This course (BCS401) will enable students to:

✓ To learn the methods for analyzing algorithms and evaluating their performance.
✓ To demonstrate the efficiency of algorithms using asymptotic notations.
✓ To solve problems using various algorithm design methods, including brute force, greedy,
divide and conquer, decrease and conquer, transform and conquer, dynamic programming,
backtracking, and branch and bound.
✓ To learn the concepts of P and NP complexity classes.
Q. No Question COs

1 Define AVL Trees. Explain its four rotation types CO3

CO3
2 Construct bottom-up heap for the list 2,9,7,6,5,8. Obtain its time complexity
CO3
3 Define heap. Explain the properties of heap along with its representation.
Design Horspools algorithm for string matching. Apply Horspools algorithm to find the CO2
4
pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP

Course Outcomes: Students will be able to

Apply asymptotic notational method to analyze the performance of the algorithms in terms of time
CO-1:
complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
CO-2:
computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given
CO-3:
real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational
CO-4:
problems.
CO-5: Analyse various classes (P,NP and NP Complete) of problems
CO-6: Illustrate backtracking, branch & bound and approximation methods.

Course In-Charge HOD

PKM Educational Trust ®

R.R. Institute of Technology

Affiliated to VTU Belgaum and Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka
Accredited by NAAC with ‘A+’, NBA
Raja Reddy Layout, Chikkabanavara, Bengaluru – 560 090
Department of Computer Science & Engineering

Question Bank_ MODULE 4

Q. No Question COs

Construct minimum cost spanning tree using Kruskals algorithm for the following graph.

1 CO2

CO2
What are Huffman Trees? Construct the Huffman tree for the following data.
2
Character A B C D E -
Probability 0.5 0.35 0.5 0.1 0.4 0.2
CO2
Apply Dijkstra’s algorithm to find single source shortest path for the given graph by
considering S as the source vertex

CO2
Define transitive closure of a graph. Apply Warshalls algorithm to compute transitive closure
of a directed graph

4
Course Outcomes: Students will be able to
Apply asymptotic notational method to analyze the performance of the algorithms in terms of time
CO-1:
complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
CO-2:
computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given
CO-3:
real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational
CO-4:
problems.
CO-5: Analyse various classes (P,NP and NP Complete) of problems
CO-6: Illustrate backtracking, branch & bound and approximation methods.

Course In-Charge HOD

PKM Educational Trust ®

R.R. Institute of Technology

Affiliated to VTU Belgaum and Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka
Accredited by NAAC with ‘A+’, NBA
Raja Reddy Layout, Chikkabanavara, Bengaluru – 560 090
Department of Computer Science & Engineering

Question Bank_ MODULE 5

Q. No Question COs

Explain the following with examples

i) P problem
1 ii) NP Problem CO2
iii) NP- Complete problem
iv) NP – Hard Problems
CO2
What is backtracking? Apply backtracking to solve the below instance of sum of subset
2
problem S={5,10,12,13,15,18} d=30
CO2
3 Illustrate N queen’s problem using backtracking to solve 4-Queens problem
Using Branch and Bound technique solve the below instance of knapsack problem. CO2
Item Weight Value
1 2 12
2 1 10
4 3 3 20
4 2 5

Capacity 5

Course Outcomes: Students will be able to

Apply asymptotic notational method to analyze the performance of the algorithms in terms of time
CO-1:
complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve
CO-2:
computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given
CO-3:
real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational
CO-4:
problems.
CO-5: Analyse various classes (P,NP and NP Complete) of problems
CO-6: Illustrate backtracking, branch & bound and approximation methods.

Course In-Charge HOD