Design and Analysis of Algorithm (CS3004-1)

Multiple Choice Questions

Unit-1
1` Main objective of analysing the algorithm is
a) To design algorithms b)To implement algorithms
c) To evaluate for efficiency d) To debug algorithms
2 Which of the following is NOT a characteristic of a good algorithm?
a) Clarity and simplicity b) Efficiency in terms of time and space
c) Correctness d) The use of complex data structures
3 What does "optimization" refer to in the context of algorithms?
a) The process of making an algorithm b) The process of improving an
more complex algorithm's efficiency
c) The process of making an algorithm run d) The process of making an algorithm
slower more clear
4 What is the purpose of pseudocode in algorithm development?
a) To provide a step-by-step b) To prevent others from understanding
implementation guide the
c) To hide the algorithm's logic d) To succinct the algorithm
5 Characteristics of an algorithm are
a) Input, output, definite, finite, b) input, output, definite, finite,
connective. effective.
c) input, output, reflective, finite, d) input, output, reflective, finite,
effective connective.
6 When an algorithm is written in the form of a programming language, it becomes a _
a) Flowchart b) Program
c) Pseudo code d) Syntax
7 Pseudocode is written using
a)Combination of Native & b) High level Programming language only
programming language
c) Natural language only d) Low level programming language
8 Which of the following is incorrect?
Algorithms can be represented:
a)as pseudo codes b)as syntax
c) as programs d) as flowcharts
9 What will be the output of the following pseudocode if the driver is fun(5)?
function fun(n)
if n == 1 return 1 else return n + fun(n-1)
a)120 b)24
c)6 d)15
10 What will be the output of the following pseudocode if the driver is fun(18,24)
function fun(a,b)
while(b!=0)
fun(b, a mod b)
 return a
a)18 b)24
c) 6 d)2
11` Given the following time complexities, which one is the slowest growing function as

a) ( ) b) ( )
c) ( ) d) ( )
12 Which of the following best describes the Big-Ω notation?
a) Describes the lower bound of the b) Describes the upper bound of the time
time complexity of an algorithm complexity of an algorithm
c) Describes the exact time complexity of d) Describes the average-case time
an algorithm complexity of an algorithm
13
What does the Big-O notation, O(f(n)), represent?
a) The average-case time complexity of b) The worst-case time complexity of an
an algorithm algorithm
c) The best-case time complexity of an d) The exact time taken by the algorithm
algorithm
14 The time complexity of an algorithm is ( )
Which of the following statements is correct about this algorithm?
a) The algorithm’s running time grows b) The algorithm’s running time grows
linearly with respect to the size of the quadratically with respect to the size of
input the input
c) The algorithm’s running time grows d) The algorithm’s running time is constant
logarithmically with respect to the size of irrespective of the input size
the input
15 If an algorithm’s time complexity is ( ), what can you infer about the algorithm?
a) The algorithm will be efficient for b) The algorithm’s time complexity grows
large inputs exponentially with the input size
c) The algorithm will run in constant time d) The algorithm's runtime will decrease as
for all inputs the input size increases
16 In asymptotic analysis, what does it mean if a function is said to be ( )?
a) The time complexity increases b) The algorithm’s runtime grows
exponentially as n increases linearly with the input size
c) The runtime of the algorithm is d) The algorithm’s runtime grows
independent of the input size logarithmically as n increases
17
If an algorithm has a worst-case time complexity of ( ), which of the following time
complexities would indicate a faster algorithm for large n?
a) ( ) b) ( )
c) ( ) d) ( )
18 Consider an algorithm with the following time complexities for different scenarios:
 Best Case: ( )
 Worst Case: ( )
 Average Case: ( )
 In which case will the algorithm perform the fastest?
a) Best Case b) Worst Case
c)Average Case d) All cases will perform equally fast
19 Which of the following is the correct asymptotic notation for expressing the upper bound
of an algorithm's running time?
a) ( ) b) ( )
c) ( ) d) ( )
20
If an algorithm has a time complexity of ( ) which of the following functions
represents its growth rate?
a) Linear b) Cubic
c) Exponential d) Logarithmic
21` What is the first step in the general plan for analyzing the time efficiency of recursive
algorithms?
a) Identify the basic operation b)Decide on a parameter indicating input
size
c) Set up a recurrence relation d)Check whether the number of times the
basic operation is executed can vary on
different inputs
22 Which is the fundamental operation that is considered while analysing the algorithms?
a) Count of basic operation b) Arithmetic operation
c) Recurrence Equation d) Geometric operation
23 What is the goal of the Tower of Hanoi problem?
a) To move all the disks to the second b) To move all the disks to the first peg
peg
c) To move all the disks to the third d) To move all the disks to the fourth peg
peg
24 The time complexity of the solution tower of hanoi problem using recursion is
a) O(n2) b) O(2n)
c) O(n log n) d) O(n)
25 What is the typical time complexity of a non-recursive algorithm that processes
each element in an array of size n exactly once?
a) O(1) b) O(n log n)
c) O(n) d) O(n^2)
26 Which of the following statements about brute force algorithms is true?
a) They always provide the optimal b) They are the most efficient algorithms for
solution but are inefficient for large all types of problems
problem sizes.
c)They exhaustively search all d) They reduce the problem size in each
possibilities, making them simple but iteration, unlike recursive algorithms
often inefficient for large inputs
27 What is the primary characteristic of a brute force algorithm?
a) It uses a divide-and-conquer strategy b) It attempts to solve the problem by
to break problems into smaller checking all possible solutions until the
 subproblems. correct one is found.
c) It uses dynamic programming to d) It uses a greedy strategy to find an optimal
avoid redundant calculations solution.
28 What is the number of times the comparison operation is executed in the algorithm for
finding the largest element in a list of numbers?
a) C(n) = n b) C(n) = n – 2
c) C(n) = n + 1 d) C(n) = n - 1
29 What is considered as the basic operation in the algorithm for finding the largest element
in an array of integers?
a) The assignment operation b)The comparison operation
c) The addition operation d) The multiplication operation
30 Which of the following recursive algorithms has a time complexity of O(n)?
a) Fibonacci sequence using naive b) Merge sort.
recursion.
c) Binary search on a sorted array. d) Factorial computation using recursion.
31` The Selection Sort algorithm finds the lowest value to sort in ascending order in an array
and moves it to the ___ of the array.
a) end b) front
c) middle d) particular location
32 The Bubble Sort algorithm finds the lowest value to sort in descending order in an array
and moves it to the ___ of the array.
a) end b) front
c) middle d) particular location
33 Linear search algorithm, also known as____
a)Binary search b) simple search
c)sequential search d)Difficult search
34 Exhaustive Search algorithm checks every possible solution to find the ____ one
a) Worst b) Average
c) amortized d) Best
35 Exhaustive search falls under which algorithm technique
a) Brute force b) Decrease and Conquer
c) Divide and Conquer d) Greedy
36 A string-searching algorithm, sometimes called string-matching algorithm, is an
algorithm that searches a body of text for portions that match by____.
a) pattern b) word
c) index d) text
37 The time complexity of the naive string matching algorithm
a) O(nm) b)O(n+m)
c)O(n-m+1) d)O(n)
38 The time complexity of the linear Search algorithm
a) O(nm) b)O(n+m)
c)O(n-m+1) d)O(n)
39 The time complexity of the Bubble sort algorithm
a) O(nm) b)O(n2)
 c)O(n-m+1) d)O(n)
40 The time complexity of the Selection sort algorithm
a) O(nm) b)O(n2)
c)O(n-m+1) d)O(n)
41` What is the primary characteristic of the Divide and Conquer approach?
a) Solving problems by iteration b) Solving problems by dividing them into
overlapping sub problems
c) Dividing a problem into smaller d) Dividing a problem into smaller problems
independent subproblems, solving and linearly solving it.
them recursively, and combining their
results
42 In Quick Sort, what is the worst-case time complexity?
a) O(n2) b) O(n logn)
c) O(logn) d) O(n)
43 Binary Search works only on which type of arrays?
a) Unsorted arrays b) Sorted arrays
c) Arrays with distinct elements d) Arrays of integers
44 Which of the following algorithms is NOT based on the Divide and Conquer approach?
a) Merge Sort b) Quick Sort
c) Binary Search d) Selection sort
45 Which of the following is true about Merge Sort?
a) It is an in-place sorting algorithm b) It has a worst-case time complexity of
O(n2)
c) It uses additional memory for d) It always selects the first element as a
merging subarrays pivot
46 During the merging process of Merge Sort, what is the time complexity to merge two
sorted subarrays?
a) O(n) b) O(logn)
c) O(n2) d) O(nlogn)
47 What is the average-case time complexity of merge sort?
a) Ꝋ (logn) b) Ꝋ (n)
2
c) Ꝋ (n ) d) Ꝋ(nlogn)
48 How many sub arrays does the quick sort algorithm divide the entire array into?
a) one b) two
c) three d) four
49 What is the recurrence relation for merge sort algorithm?
a) C(n)=2C(n)+1 b) C(n)=2C(n/2)-1
c) C(n)=2C(n/2)+n d) C(n)=2C(n2/2)+n
50 What is the time complexity of Binary Search in the best case?
a) Ꝋ (n) b) Ꝋ (logn)
c) Ꝋ (nlogn) d) Ꝋ (1)