SRM INSTITUTE OF SCIENCE AND TECHNOLOGY

Tircuchirappalli

FACULTY OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND

ENGINEERING

QUESTION BANK

DEGREE / BRANCH : B.Tech/CSE

YEAR / Semester : II/IV

SUBJECT Code/Title : 21CSC204J – Design and Analysis of Algorithms

Regulation : 2021
 Academic Year : 2023-2024

QUESTION BANK

SUBJECT : 18CSC204J – Design and Analysis of Algorithms

SEM/ YEAR : IV/ II
Course Outcomes

CO 1. Apply efficient algorithms to reduce space and time complexity of both recurrent and non-
recurrent relations
CO 2. Solve problems using divide and conquer approaches
CO 3. Apply greedy and dynamic programming types techniques to solve polynomial time
problems.
CO 4. Create exponential problems using backtracking and branch and bound approaches.
CO 5. Interpret various approximation algorithms and interpret solutions to evaluate P type, NP
Type, NPC, NP Hard problems

UNIT I

Introduction-Algorithm Design - Fundamentals of Algorithms- Correctness of algorithm - Time complexity

analysis - Insertion sort-Line count - Operation count - Algorithm Design paradigms - Designing an
algorithm and its analysis – Best- Worst- and Average case - Asymptotic notations Based on growth
functions – O – O – Ө – ω - Ω - Mathematical analysis - Induction, Recurrence relations -Solution of
recurrence relations - Substitution method - Solution of recurrence relations - Recursion tree - Solution of
recurrence relations - examples.

PART-A (Multiple Choice Questions)

Q. Questions Course Competence
Outcome BT Level
No

______is the first step in solving the problem

A. Understanding the Problem
B. Identify the Problem
1
C. Evaluate the Solution
D. Coding the Problem
CO 1 BT 1
Answer: - B

While solving the problem with computer the most difficult step is
______.
A. describing the problem
2
B. finding out the cost of the software
C. writing the computer instructions
CO 1 BT 1
D. testing the solution
Answer:- C

The correctness and appropriateness of ___________solution can be

checked very easily.
A. algorithmic solution
3
B. heuristic solution
C. random solution
CO 1 BT 1
D. Brute force Solution
Answer:- A

When determining the efficiency of algorithm, the space factor is

measured by
A. Counting the maximum memory needed by the algorithm
4
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
CO 1 BT 1
D. Counting the maximum disk space needed by the algorithm
Answer: - A

The hierarchy of operations is denoted as _____________.

I. +, - II. Power III. *, / IV. \, MOD
A. I, II, III, IV
5
B. II, IV, III, I
C. IV, I, III, II
CO 1 BT 1
D. II, III, IV, I
Answer:- B

Which of the following is not O(n2)?

A. (15) * n2
6 B. n1.98
C. n3/(sqrt(n))
D. (20) * n2 CO 1 BT 1
Answer: C
 Which of the following sorting algorithms does not have a worst case
running time O(n2)?
7 A. Insertion Sort
B. Merge Sort
C. Quick Sort CO 1 BT 1
D. Bubble Sort
Answer: B
Number of comparisons required to search an element X=18 in the list
A=[5,44,89,22,18,9,15,8] using linear search.
8 A. 3
B. 0
C. 4 CO 1 BT 1
D. 5
Answer:D
What is the time complexity for the following C module? Assume that
n>0;
9 int module(int n)
{
if( n== 1) CO 1 BT 1
return 1;
else
return (n+module(n-1));
}
A. O(n)
B. O(log n)
C. O(n2)
D. O(n!)
Answer: A
What is the time complexity of following code:
int a = 0, i = N;
while (i > 0)
10
{
a += i;
CO 1 BT 1
i /= 2;
}
A. O(N)
B. O(Sqrt(N))
C. O(N / 2)
D. O(log N)
ANSWER: D
Two main measures for the efficiency of an algorithm are
A. Processor and memory
B. Complexity and capacity
11
C. Time and space
D. Data and space
CO 1 BT 1
Answer: - C
 What does the algorithmic analysis count?
A. The number of arithmetic and the operations that are required to run the
program
12
B. The number of lines required by the program
C. The number of seconds required by the program to execute
CO 1 BT 1
D. None of these
Answer:- A

An algorithm that indicates the amount of temporary storage required

for running the algorithm, i.e., the amount of memory needed by the
algorithm to run to completion is termed as_____.
13
A. Big Theta θ (f)
B. Space complexity
CO 1 BT 1
C. Big Oh O (f)
D. Time Complexity
Answer:- B

Consider a linked list of n elements. What is the time taken to insert an

element after an element pointed by some pointer?
A. (1)
14
B. (n)
C. (log2 n)
CO 1 BT 1
D. (n log2 n)
Answer:- A

If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively
and each element occupies 2 bytes then the array has been stored in
order.
15
A. row major
B. column major
CO 1 BT 1
C. matrix major
D. none of these
Answer A

16 The time factor when determining the efficiency of algorithm is

measured by
A. Counting microseconds CO 1 BT 1
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
Answer:- B
 Time complexities of four algorithms are given. Which should execute
the slowest for large values of N?
A. (n log n)
17
B. O(n)
C. O(log n)
CO 1 BT 1
D. O(n2)
Answer:-B

Which one of the following is the tightest upper bound that represents
the number of swaps required to sort n number using selection sort?
A. (log n)
18
B. O(n)
C. (n log n)
CO 1 BT 1
D. O(n2)
Answer:-B

How many comparisons are needed for linear Search array when
elements are in order in best case?
A. 1
19
B. n
C. n+1
CO 1 BT 1
D. n-1
Answer A

The complexity of Bubble sort algorithm is__________

A. O(n)
B. O(log n)
20
C. O(n2)
D. O(n log n)
CO 1 BT 1
Answer : C

Which of the given options provides the increasing order of asymptotic

complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n
21
f2(n) = n^(3/2)
f3(n) = nLogn
CO 1 BT 1
f4(n) = n^(Logn)
A. f3, f2, f1, f4
B. f2, f3, f1, f4
C. f2, f3, f4, f1
D. f3, f2, f4, f1
Answer : D
 How much number of comparisons is required in insertion sort
to sort a file if the file is sorted in reverse order?
22 A. N2
B. N
C. N-1 CO 1 BT 1
D. N/2
Answer:A

The worst-case occur in linear search algorithm when …….

A. Item is somewhere in the middle of the array
B. Item is not in the array at all
23
C. Item is the last element in the array
D. Item is the last element in the array or item is not there at all
CO 1 BT 1
Answer D

What is the time complexity of fun()?

int fun(int n)
{
24
int count = 0;
for (int i = 0; i < n; i++)
CO 1 BT 1
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
A. Theta (n)
B. Theta (n^2)
C. Theta (n*Logn)
D. Theta (nLognLogn)
Answer : B

The time complexity of the following C function is (assume n > 0 )

int recursive (int n)
{
25
if (n == 1)
return (1);
CO 1 BT 1
else

return (recursive (n-1) + recursive (n-1));

}
A. O(n)
B. O(nlogn)
C. O(n2)
D. O(2n)
Answer:D
 A function in which f(n) is Ω(g(n)), if there exist positive values k and c
such that f(n)>=c*g(n), for all n>=k. This notation defines a lower
bound for a function f(n):
26
A. Big Omega Ω (f)
B. Big Theta θ (f)
CO 1 BT 1
C. Big Oh O (f)
D. Big Alpha α (f)
Answer A
The concept of order Big O is important because_______
A. It can be used to decide the best algorithm that solves a given problem
B. It determines the maximum size of a problem that can be solved in a
27
given
amount of time
CO 1 BT 1
C. It is the lower bound of the growth rate of algorithm
D. Both A and B
Answer A
The upper bound on the time complexity of the nondeterministic
sorting algorithm is
A. O(n)
28
B. O(n log n)
C. O(1)
CO 1 BT 1
D. O( log n)
Answer: A

In the analysis of algorithms, what plays an important role?

A. Text Analysis
B. Growth factor
29
C. Time
D. Space
CO 1 BT 1
Answer: B

Which one of the following correctly determines the solution of the

recurrence relation given below with T(1) = 1 and T(n)= 2T(n/4) + n1/2
A. O(n )
2

30
B. O(n)
C. O(n log n)
1/2

CO 1 BT 1
D. O(log n)
Answer C

What is the time complexity of recursive function given below:

T(n)= 4T(n/2) + n2
A. O(n2)
31
B. O(n)
C. O(n2 log n)
CO 1 BT 1
D. O(n log n)
Answer C

PART B (4 Marks)
1 Explain Analysis Framework of algorithm with Suitable Example. CO1 BT 2

CO1 BT 2

2 Discuss in detail about all the asymptotic notations with Example.

CO1 BT 3

3 Explain the Recursive algorithm for Computing Tower of Hanoi and

analyse its Time Complexity using Backward Substitution method.

Solve the following recurrence relations. CO1 BT 3

4
X(n)=x(n-1) + 5 for n>1, x(1) = 0

CO1 BT 3

5 Write the algorithm for finding element uniqueness and analyse its
efficiency.

Solve by Mathematical Induction. CO1 BT 3

Find the Time complexity of the following function. CO1 BT 2

Void Function(int n)
{
7
int count = 0;
for (int i=n/2; i< =n; i++)
for (int j=1; j<=n; j=2*j)
for(int k=1; k<=n; k=k*2)
count++;
}
CO1 BT 3

8 Solve T(n)=T(n/4)+T(n/2)+n2 using recurrence tree method.

 Give the non-recursive algorithm for finding the value of the largest CO1 BT 2
element in a list of n numbers and analyse its efficiency
9

Solve the following recurrence relations. CO1 BT 3

I. x(n)=x(n-1)+5 for n>1, x(1)=0
II. x(n)=3x(n-1)for n>1, x(1)=4
10
III. x(n)=x(n/2)+n for n>1, x(1)=1 (solve for n=2k)

PART C (12 Marks)

What is algorithm? Define the characteristics of the algorithm. CO1 BT 2

Differentiate pseudocode and algorithm.
1

Illustrate insertion sort algorithm and discuss its time complexity.

CO1 BT 2

2 Write the algorithm for matrix multiplication and analyse its efficiency.

Solve the recurrence relation T(n)=7T(n/2)+18n 2 and find the time CO1 BT 3
complexity.
3

Design a recursive algorithm to compute the factorial function F(n) =n! for CO1 BT 2
an arbitrary non negative integer n and set up a recurrence equation for the
number of multiplication made by the algorithm.
4

CO1 BT 2

5 Write a recursive algorithm to find the number of binary digits in the

binary representation of a positive decimal integer and analyze its
efficiency
 UNIT II

Introduction-Divide and Conquer - Maximum Subarray Problem - Binary Search - Complexity of binary search Merge
sort - Time complexity analysis -Quick sort and its Time complexity analysis Best case- Worst case- Average case
analysis - Strassen's Matrix multiplication and its recurrence relation - Time complexity analysis of Merge sort -
Largest sub-array sum - Time complexity analysis of Largest subarray sum - Master Theorem Proof - Master theorem
examples - Finding Maximum and Minimum in an array - Time complexity analysis-Examples - Algorithm for finding
closest pair problem – Convex Hull problem

PART-A (Multiple Choice Questions)

Q. Questions Course Competence

Outcome BT Level
No

Partition and exchange sort is____________

A. quick sort
B. tree sort
1
C. heap sort
D. bubble sort CO 2 BT 1
ANSWER: A

Which of the following is not the required condition for binary search
algorithm?
A. The list must be sorted
2
B. There should be the direct access to the middle element in any sub list
C. There must be mechanism to delete and/or insert elements in list. CO 2 BT 1
D. Number values should only be present
ANSWER: C
Which of the following sorting algorithm is of divide and conquer
type?
A. Bubble sort
3
B. Insertion sort
C. Merge sort CO 2 BT 1
D. Selection sort
ANSWER: C
 ____________order is the best possible for array sorting algorithm
which sorts n item.
A. O (n logn)
4
B. O (n2)
C. O (n+logn) CO 2 BT 1
D. O (logn)
ANSWER: C
The complexity of merge sort algorithm is __________
A. O (n)
B. O (logn)
5
C. O (n2)
D. O (n logn)
CO 2 BT 1
ANSWER: D

Binary search algorithm cannot be applied to ________

A. sorted linked list
B. sorted binary trees
6
C. sorted linear array
D. pointer array
CO 2 BT 1
ANSWER: A

Which of the following is not a limitation of binary search algorithm?

A. must use a sorted array
B. requirement of sorted array is expensive when a lot of insertion and
7
deletions are needed
C. there must be a mechanism to access middle element directly
CO 2 BT 1
D. binary search algorithm is not efficient when the data elements more
than 1500.
ANSWER: D
Which of the following is an external sorting?
A. Insertion Sort
B. Bubble Sort
8
C. Merge Sort
D. Tree Sort
CO 2 BT 1
ANSWER: B

Merging k sorted tables into a single sorted table is called _______

A. k way merging
B. k th merge
9
C. k+1 merge
D. k-1 merge
CO 2 BT 1
ANSWER: A

The operation that combines the element is of A and B in a single

sorted list C with n=r+s element is called ________
A. Inserting
10
B. Mixing
C. Merging
CO 2 BT 1
D. Sharing
ANSWER: C
11 What is the worst case time complexity of a quick sort
algorithm?
a) O(N) CO 2 BT 1
b) O(N log N)
c) O(N2)
d) O(log N)
ANSWER: C

12 What is the average running time of a quick sort algorithm?

a) O(N2)
b) O(N) CO 2 BT 1
c) O(N log N)
d) O(log N)
ANSWER: C

13 How many sub arrays does the quick sort algorithm divide the
entire array into?
a) one CO 2 BT 1
b) two
c) three
d) four
ANSWER: B

14 Quick sort is a __________

a) greedy algorithm
b) divide and conquer algorithm CO 2 BT 1
c) dynamic programming algorithm
d) backtracking algorithm
ANSWER: B

15 Which one of the following sorting algorithm is best suited to

sort an array of 1 million elements?
 a) Bubble sort CO 2 BT 1
b) Insertion sort
c) Merge sort
d) Quick sort
ANSWER: D

16 Strassen’s algorithm is a/an_____________ algorithm.

a) Non- recursive
CO 2 BT 1
b) Recursive
c) Approximation
d) Accurate
ANSWER: B

17 What is the running time of naïve matrix multiplication

algorithm?
CO 2 BT 1
a) O(n2.81)
b) O(n4)
c) O(n)
d) O(n3)
ANSWER: D

18 ___________ is a method of constructing a smallest polygon out

of n given points.
CO 2 BT 1
a) closest pair problem
b) quick hull problem
c) path compression
d) union-by-rank
ANSWER: B

19 What is the other name for quick hull problem?

a) convex hull
CO 2 BT 1
 b) concave hull
c) closest pair
d) path compression
ANSWER: A

20 Master’s theorem is used for?

a) solving recurrences
CO 2 BT 1
b) solving iterative relations
c) analysing loops
d) calculating the time complexity of any code
ANSWER: A

21 What is the result of the recurrences which fall under first case
of Master’s theorem (let the recurrence be given by
CO 2 BT 1
T(n)=aT(n/b)+f(n) and f(n)=nc?
a) T(n) = O(n^logba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)
ANSWER: A

22 Under what case of Master’s theorem will the recurrence

relation of merge sort fall?
CO 2 BT 1
a) 1
b) 2
c) 3
d) It cannot be solved using master’s theorem
ANSWER: B

23 Find the maximum sub-array sum for the given elements.

{2, -1, 3, -4, 1, -2, -1, 5, -4}
CO 2 BT 1
 a) 3
b) 5
c) 8
d) 6
ANSWER: B

24 What is the time complexity of the divide and conquer

algorithm used to find the maximum sub-array sum?
CO 2 BT 1
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)
ANSWER: C

25 What is the advantage of recursive approach than an iterative

approach?
CO 2 BT 1
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) More code has to be written
ANSWER: B

PART B (4 Marks)

1 Formulate the Binary Search Algorithm and analyze its worst, best and CO2 BT 3
average case time complexity.

CO2 BT 3

2 Consider that there were two list of sorted array. Propose the algorithm for
 combining the elements of two arrays into single array in sorted order.

Solve the maximum sub array sum in a pictorial way by drawing tree. CO2 BT 3

CO2 BT 3

4 Write an algorithm for finding maximum sub array sum and analyse its
efficiency.

CO2 BT 2

5 Describe the control abstraction for Divide and Conquer strategy.

Devise an algorithm for generating n’ terms of Fibonacci series and CO2 BT 2

analyse its efficiency.
6

CO2 BT 2

7 Write short notes on Master theorem usage in the time complexity analysis.

CO2 BT 3

8 Develop the algorithmic steps to find the maximum and minimum element
in the given list and analyse its efficiency.

PART C (12 Marks)

CO2 BT 2

1 Consider example of your choice and find the Closest pair among the
 considered number. Devise an algorithm and analyze its efficiency.

CO2 BT 2

2 Explain the Convex Hull problem and analyze the time complexity of the
algorithm.

Write an algorithm for binary search and analyse its time complexity with CO2 BT 2
suitable examples.
3

Write an algorithm for quick sort and analyse its time complexity with CO2 BT 2
suitable examples.
4

Write an algorithm for merge sort and analyse its time complexity with CO2 BT 3
suitable examples 6 5 12 10 9 1 8 6
5

CO2 BT 3

6 Solve the given matric multiplication with Strassen’s matrix multiplication

and analyse its time complexities.

A= .

B=

Note:
 1. BT Level – Blooms Taxonomy Level

2. CO – Course Outcomes

BT1 – Remember BT2 – Understand BT3 – Apply BT4 – Analyze BT5 – Evaluate BT6 – Create