VEL TECH MULTI TECH DR RANGARAJAN DR SAKUNTHALA ENGINEERING COLLEGE

QUESTION BANK

DEPT: AI&DS/CSBS SUB CODE/TITLE:191AI521/DAA

YEAR/SEM: III/V

UNIT-I INTRODUCTION

S.NO PART-A(MCQ) CO COGNIT

IVE Level
1 __________is a sequence of ambiguous instructions for solving a problem. CO1.1 CL1
A. Algorithm
B. Big oh notation
C. Sorting algorithm
D. Mapping algorithm
Reference: Introduction to DAA –Third Edition –Anany Levitin–pgno-29)
2 ___________ is the initial step in the process of solving the problem. CO1.1 CL1
A. Understanding the Problem
B. Identifying the Problem
C. Evaluating the Solution
D. Coding the Problem
3 ______ solution requires reasoning built on knowledge and experience CO1.1 CL2
Which solution is required to build the reasoning based on knowledge and
experience?
A. Algorithmic Solution
B. Heuristic Solution
C. Random Solution
D. Brute force Solution
4 CO1.1 CL1
Choose the best one for which the correctness and appropriateness can be
checked very easily.
A. Algorithmic Solution
B. Heuristic Solution
C. Random Solution
D. Brute force Solution
5 CO1.1 CL1
There may exist______ algorithm(s) for solving the same problem.
A. Two
B. Three
C. Several
D. One
6 When determining the efficiency of algorithm, the space factor is measured CO1.2 CL1
by____
A. Counting the maximum memory needed by the algorithm
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
D. Counting the maximum disk space needed by the algorithm
7 Choose the correct order of algorithm design and analysis process. CO1.2 CL2
1.Understand the problem
2. Prove correctness
3. Design and algorithm
4. Analyze the algorithm
5. Code the algorithm
 A. 1,2,3,4,5
B. 1,3,2,4,5
C. 2,1,3,4,5
D. 3,1,2, 4,5
8 Random Access Machine (RAM) execute CO1.2 CL1
A. Sequential algorithms
B. Parallel algorithms
C. Both A and B
D. Concurrent algorithm
9 ________ + Data Structures = Programs CO1.2 CL1
A. Problem
B. Instructions
C. Algorithms
D. Software
10 Algorithms can be specified in CO1.2 CL1
A. Natural Language (in words)
B. Pseudo code
C. Flowchart
D. Programming language
11 Find out the term which does not matches with calculation of algorithm? CO1.2 CL2
A. Correctness
B. Efficiency
C. Complex
D. Generality
12 The time factor when determining the efficiency of algorithm is measured CO1.3 CL1
by_____
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
13 The convex-hull problem is related to_____ CO1.3 CL1
A. Graph problems
B. Geometric Problems
C. Numerical Problems
D. Combinatorial problems
14 Choose the best option regarding the algorithmic analysis count. CO1.4 CL1
A. The number of arithmetic and the operations that are required to run the
program
B. The number of lines required by the program
C. The number of seconds required by the program to execute
D. The number of characters executed
15 Two main measures for the efficiency of an algorithm are CO1.4 CL1
A. Processor and memory
B. Complexity and capacity
C. Time and space
D. Data and space
16 Which options provides the increasing order of asymptotic complexity CO1.5 CL2
of functions f1, f2, f3 and f4?f1(n)=2^n f2(n) =n^(3/2) f3(n) =nLogn
f4(n) =n^(Logn)
A. f3,f2,f1,f4
B. f2,f3,f1,f4
C. f2,f3,f4,f1
D. f3,f2,f4,f1
(Reference:GATECS-2011)
https://www.geeksforgeeks.org/gate-gate-cs-2011-question-37/
17 Consider the following three statements CO1.5 CL2
1.(n+k)m=Θ(nm),where k and m are constants
2.2n+1=O(2n)
3.22n+1=O(2n)
 Which of these statements are correct?
A.1and2
B.1and3
C.2and3
D.1,2,and3
(Reference:GATE2003)
GATE | GATE-CS-2003 | Question 20 - GeeksforGeeks
18 Calculate the time complexity of following code CO1.5 CL2
int a=0, i =N;
while(i>0)
{
a+= i; i /= 2;
}
A.O(N)
B.O(Sqrt(N))
C.O(N/ 2)
D.O(log N)
19 A function in which f(n) is Ω(g(n)),if there exist positive values k and c such CO1.6 CL1
A. Big Omega Ω(f)
B. Big Theta θ(f)
C. Big Oh O(f)
D. Big Alpha α(f)
20 What is the time complexity of fun()? CO1.6 CL2
Int fun(int n)
{
int count =0;
for (int i =0;i<n; i++)
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(n*Logn*Logn)
(Reference: Introduction to DAA –Third Edition –AnanyLevitin–pgno-83)
21 In the analysis of algorithms, which plays an important role? CO1.6 CL1
A. Text Analysis
B. Growth factor
C. Time
D. Space
22 Which one of the following correctly determines the solution of the recurrence CO1.7 CL2
relation given below with T (1) =1 and T(n) =2T (n/2)+ logn
A. θ (n)
B. θ(nlogn)
C. θ (n^2)
D. θ(logn)
(Reference:GATE-CS-2014-(set-2))
23 What is the time complexity of recursive function given below? CO1.7 CL2
T(n)=4T(n/2) +n^2
A.O(n^2)
B.O(n)
C.O(n^2log n)
D.O(n3)
24 The worst-case occur in linear search algorithm when....... CO1.8 CL1
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
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
(Reference: UGC-NET | UGC NET CS 2015 Jun – II)
https://www.geeksforgeeks.org/ugc-net-ugc-net-cs-2015-jun-ii-question-
24/)
25 The complexity of Bubble sort algorithm is CO1.8 CL1
A.O(n)
B.O(logn)
C.O(n^2)
D.O(nlogn)
26 Which one of the following is the tightest upper bound that represents the CO1.8 CL1
number of swaps required to sort n number using selection sort?
A.(logn)
B.O(n)
C.(nlog n)
D.O(n 2 )
27 The recursive versions of binary search use a structure. CO1.8 CL1
A. Branch and bound
B. Dynamic programming
C. Divide and conquer
D. Simple recursive
28 What is the first step in the general plan for analyzing the time efficiency of CO1.9 CL1
recursive algorithms?
Identify the basic operation
Decide on a parameter indicating a size
Set up a recurrence relation
Check whether the number of times the basic operation is executed can vary on
different inputs

29 In algorithm visualization of bubble sort algorithm the non-linear curve of the CO1.9 CL1
sorted elements is close to .
A.3n
B.n^3
C.2n
D.n^2
30 The upper bound on the time complexity of then on deterministic sorting CO1.9 CL1
algorithm is
A.O(n)
B.O(n logn)
C.O(n^2)
D.O(log n)
PART – B FOUR MARK QUESTIONS
1 Prove the equality gcd(m,n) =gcd(n, m mod n) for every pair of positive integers CO1.1 CL3
m and n using consecutive integer checking algorithm.
2 Understand the Euclid’s treatise, which uses subtractions rather than integer CO1.1 CL3
divisions. Write a pseudocode for this version of Euclid’s algorithm.
3 Describe the standard algorithm for finding the binary representation of a positive CO1.2 CL3
decimal integer.
a.in English.
b.in a pseudocode.
4 Consider matrix multiplication. Given two n × n matrices A and B, find the CO1.2 CL4
time efficiency of the definition-based algorithm for computing their product C =
AB. By definition, C is an n × n matrix whose elements are computed as the

scalar (dot) products of the rows of matrix A and the columns of matrix B.
where C[i, j ]= A[i, 0]B[0, j]+ . . . + A[i, k]B[k, j]+ . . . + A[i, n − 1]B[n − 1, j]
 for every pair of indices 0 ≤ i, j ≤ n − 1.

5 Consider the algorithm for the sorting problem that sorts an array by counting, CO1.3 CL3
for each of its elements, the number of smaller elements and then uses this
information to put the element in its appropriate position in the sorted array:

Algorithm Comparison CountingSort(A[0..n − 1], S[0..n − 1])

//Sorts an array by comparison counting
//Input: Array A[0..n − 1] of orderable values
//Output: Array S[0..n − 1] of A’s elements sorted in non decreasing order
for i ← 0 to n − 1 do
Count[i] ← 0
for i ← 0 to n − 2 do
for j ← i +1 to n − 1 do if A[i] < A[j]
Count[j] ← Count[j]+ 1
else Count[i] ← Count[i]+ 1
for i ← 0 to n − 1 do
S[Count[i]] ← A[i]
a. Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47.
6 Find the time complexity and space complexity of the following problems. CO1.3 CL3
Factorial using recursion and Compute n th Fibonacci number using Iterative
statements.
7 If you have to solve the searching problem for a list of n numbers, how can you CO1.4 CL2
take advantage of the fact that the list is known to be sorted? Give separate
answer for (i) List represented as arrays (ii) List represented as linked lists
Compare the time complexities involved in the analysis of both the algorithms..

8 Use the informal definition of O, Θ, and Ω to determine whether the following CO1.5 CL4
assertions are true or false.
a. n(n+1)/2∈O(n3) b. n(n+1)/2∈O(n2) c. n(n+1)/2∈Θ(n3)
d. n(n+1)/2∈Ω(n)
9 Could you describe the methodology or approach used within each component of CO1.6 CL2
the framework?
10 Consider the following well-known sorting algorithm (we shall study it more CO1.7 CL3
closely later in the book) with a counter inserted to count the number of key
comparisons.
Algorithm SortAnalysis(A[0..n−1])
//Input: An arrayA[0..n −1]of n or durable elements
//Output: The total number of key comparisons made
count←0
fori←1ton−1do
v← A[i]j←i−1
while j≥ 0 and A[j] > v do count←count+ 1
A[j+1]←A[j]
j←j−1
A[j+1]←v
Is the comparison counter inserted in the right place? If you believe It is, prove it;
if you believe it is not, make an appropriate correction.
11 Consider the element uniqueness problem; check whether all the elements in a CO1.8 CL3
given array of n elements are distinct using straight forward algorithm.
12 Compute the factorial function F(n)=n! for an arbitrary non negative integer n. CO1.8 CL4
Since n!=1….(n-1)*n=(n-1)!*n for n>=1 and 0!=1, using recursive algorithm.
13 Give an algorithm to check whether all the Elements in a given array of n CO1.9 CL2
elements are distinct. Find the worst case complexity of the same
PART – C

1 a. Among all inputs with 1=m, n=10, how many divisions did the Euclid CO1.1
algorithm make in the shortest amount of steps? CL3
b. Estimate how many times faster it will be to find gcd(31415, 14142) by
Euclid’s algorithm compared with the algorithm based on checking consecutive
integers from min{m, n} down to gcd(m, n).
2 Write a pseudocode for an algorithm for finding real roots of equation ax2 + bx + CO1.2
c = 0 for arbitrary real coefficients a, b, and c. (You may assume the availability CL4
of the square root function sqrt(x).)
3 (i) Explain how analysis of linear search is done with a suitable CO1.3 CL4
illustration.
(ii) Define recurrence equation and explain how solving recurrence
equations are done.
4 For each of the following algorithms, indicate CO1.4 CL4
(i)a natural size metric for its inputs;
(ii)its basic operation;
(iii)whether the basic operation count can be different for inputs of the same
size;
a) Computing the sum of n numbers
b) Computing n!
c) Finding the large set of n numbers
d) Euclid’s algorithm
e) Sieve of Eratosthenes
f) Pen-and-pencil algorithm for multiplying two n-digit decimal integers
5 Use the most appropriate notation among Big-Oh, Theta, Big-Omega to indicate CO1.5
the time efficiency class of sequential search CL2
a) in the worst case(4m)
b) in the best case(4m)
c) in the average case(4m)
6 (i) Briefly explain the mathematical analysis of recursive and non- CO1.6
recursive algorithm.
(ii) Give the general plan for analyzing the time efficiency of recursive algorithm
and use recurrence to find number of moves Towers of Hanoi problem.
7 Consider the problem of finding the value of the largest element in a list of n CO1.8
numbers. CL3
a)Write an algorithm
b)List out the general plan for analyzing the time efficiency of non recursive
algorithm.
8 CO1.8
Give the recursive algorithm which finds the number of binary digits in the CL2
binary representation of a positive decimal integer. Find the recurrence relation
and complexity.
 UNIT II
BRUTE FORCE AND DIVIDE-AND-CONQUER

Brute Force − Computing an − String Matching − Closest-Pair and Convex-Hull Problems −

Exhaustive Search − Travelling Salesman Problem − Knapsack Problem − Assignment problem. Divide
and Conquer Methodology − Binary Search − Merge sort − Quick sort − Multiplication of Large
Integers − Closest-Pair and Convex- Hull Problems.

S.NO PART – A(MCQ) CO COGNITIVE

LEVEL
1 ________ approach is being followed in Convex hull problem. CO2.1 CL1
a) Greedy technique b)Dynamic programming c)linear d)Brute force.
2 ________ approach is based on computing the distance between each pair CO2.1 CL1
of distinct points and finding a pair with the smallest distance.
a)Brute force b)Exhaustive search c)Divide and conquer d)Branch and
bound
3 _______ is the basic operation of closest pair algorithm using brute force CO2.1 CL2
technique.
a)Euclidean distance b)Radius c)Area d)Manhattan distance
4 What is the worst case complexity of selection sort? CO2.1 CL1
a)O(nlogn) b)O(logn) c)O(n) d)O(n2)
5 What is the runtime efficiency of using brute force technique for the closest CO2.1 CL2
pair problem?
a) O(N) b) O(N log N) c) O(N2) d) O(N3 log N)
6 Given input string = “ABCDABCATRYCARCABCSRT” and pattern CO2.2 CL3
string = “CAT”. Find the first index of the pattern match using quick search
algorithm.
a)2 b)6 c)11 d)14
7 Given a pattern of length – 5 window, find the valid match in the given text CO2.2 CL3
Pattern: 2 1 9 3 6
Modulus: 21
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21
Text: 9 2 7 2 1 8 3 0 5 7 1 2 1 2 1 9 3 6 2
3 9 7

a)11 – 16 b) 3 – 8 c)13 – 18 d)15-20

8 Given a pattern of length – 5 window, find the spurious hit in the given text CO2.2 CL3
string
Pattern: 3 1 4 1 5
Modulus: 13
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20
Text: 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
3 9

a) 6-10 b) 12-16 c) 3-7 d) 13-17

9 Which approach is based on computing the distance between each pair of CO2.3 CL1
distinct points and finding a pair with the smallest distance?
a) Brute force b) Exhaustive search c) Divide and conquer d) Branch
and bound
10 What is the basic operation of closest pair algorithm using brute force CO2.3 CL1
technique?
a) Euclidean distance b) Radius c) Area d) Manhattan distance
11 What is the optimal time required for solving the closest pair problem using CO2.3 CL2
divide and conquer approach?
a) O(N) b) O(log N) c) O(N log N) d) O(N2)
12 Consider a complete graph G with 4 vertices. The graph G has ____ CO2.4 CL2
spanning trees.
a) 15 b) 8 c) 16 d) 13
13 Consider the graph M with 3 vertices. Its adjacency matrix is shown below. CO2.4 CL2
Which of the following is true?

a) Graph M has no minimum spanning tree

b) Graph M has a unique minimum spanning trees of cost 2
c) Graph M has 3 distinct minimum spanning trees, each of cost 2
d) Graph M has 3 spanning trees of different costs
14 The travelling salesman problem can be solved using _________ CO2.4 CL2
a) A spanning tree b) A minimum spanning tree
c) Bellman – Ford algorithm d) DFS traversal
15 If we have materials of different values per unit volume and maximum CO2.5 CL1
amounts, the knapsack problem finds the most valuable mix of materials
that fit in a knapsack of fixed volume.
a)Bounded b)Binary c)0-1 d)Fractional
16 What is the objective of the knapsack problem? CO2.5 CL1
a)To get maximum weight in the knapsack
b)To get minimum total value in the knapsack
c)To get maximum total value in the knapsack
d)To get minimum weight in the knapsack
17 Binary Search method uses input as CO2.6 CL2
(a)Unsorted Array (b) Linear Linked List (c) Sorted Array (d) Hash Table
18 Merge sort uses which of the following technique to implement sorting? CO2.6 CL2
a)Backtracking b)Greedy algorithm
c)Divide and conquer d)Dynamic programming
19 Which of the following algorithm design technique is used in the quick sort CO2.6 CL1
algorithm?
(a)Dynamic programming (b)Backtracking
(c)Divide and conquer (d)Greedy method
20 Heap sort is an implementation of ____________ using a descending CO2.6 CL1
priority queue.
a) insertion sort b) selection sort
c) bubble sort d) merge sort
21 The running time of Strassen’s algorithm for matrix multiplication is CO2.6 CL1
(a)ϴ (n) (b) ϴ (n3) (c) ϴ (n2) (d)ϴ (n2.81)
22 Strassen’s matrix multiplication algorithm follows ___________ technique. CO2.7 CL2
a) Greedy technique b) Dynamic Programming
c) Divide and Conquer d) Backtracking
23 What is the optimal time required for solving the closest pair problem using CO2.7 CL2
divide and conquer approach?
a)O(N) b)O(logN) c)O(NlogN) d)O(N2)
24 Which of the points are closer to each other? CO2.7 CL2
 a) p1 andp11 b)p3andp8 c)p2andp3 d)p9andp10
25 Is a method of constructing a smallest polygon out of n CO2.7 CL2
given points.
a) Closest pair problem b) Quick hull problem c) Path compression d)
Union-by-ran
26 Find the pivot element from the given input using median-of-three CO2.7 CL2
partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
a) 8 b) 7 c)9 d)6
27 Consider the tree shown below; the node 24 violates the max-heap CO2.8 CL2
property. Once heap procedure is applied to it, which position will it be in?

a) 4 b) 5 c)8 d) 9
28 In what time can a binary heap be built? CO2.8 CL2
a)O(N) b)O(Nlog N) c)O(logN) d)O(N2)
29 What does the following diagram depict? CO2.9 CL2

a)Closest pair b)Convex hull c)Concave hull d)Path compression

30 Which of the following statement is not related to quick hull algorithm? CO2.9 CL2
a) Finding points with minimum and maximum coordinates
b) Dividing the subset of points by a line
c) Eliminating points within a formed triangle
d) Finding the shortest distance between two points
PART – B

1 Sort the list E, X, A, M, P, L, E in alphabetical order by selection sort. CO 2.1 CL2

2 Design a brute-force algorithm for computing the value of a polynomial CO 2.1 CL2
p(x) = anxn + an-1 xn-1 + ... +a1x + a0 at a given point x0 and determine its
worst-case efficiency class.
3 Find the number of comparisons made by the sentinel version of sequential CO 2.1 CL2
search a. in the worst case. b. in the average case if the probability of a
successful search is p (0 ≤ p ≤ 1).
4 Find the pattern NOT in the following string NOBODY NOTICED HIM by CO2.2 CL3
using brute force string matching algorithm
5 Examine a brute force algorithm for string matching problem. CO2.2 CL3
Pattern: abaa;
Searched String: ababbaabaaab
6 Is it possible to compute the distance between the two closest points using CO2.3 CL1
brute force approach? Justify your answer with pseudocode.
7 Assuming that each tour can be generated in constant time, what will be the CO2.4 CL2
 efficiency class of the exhaustive search algorithm outlined in the text for
the travelling salesman problem?
8 Generate the actions of shortest paths for the given graph from vertex1 to CO2.5 CL4
all remaining vertices using Brute force approach.
1->2=20, 2->1=2, 1->3=15, 2->5=10, 2->6=30, 3->6=10, 3->4=4, 5-
>4=15, 6->4=4, 6->5=10.
9 Find the shortest distance between the vertices using travelling salesman CO2.6 CL4
problem.

10 State the brute force Knapsack. Find an optimal solution to the Knapsack CO2.7 CL3
instance n=4, m=16, (v1,v2,v3,v4) =(20,30,50,10) and (W1,W2,W3,W4)=
(2,5,10,5).
11 Apply merge sort for the following elements 8, 3, 2, 9, 7, 1, 5, 4. CO2.8 CL3

12 Multiply the numbers 54 and 45. Evaluate by using multiplication CO2.9 CL3
of Large integer concepts.
PART – C

1 Sort the array value 89,45,68,90,29,34,17 using bubble sort and analyze its CO2.1 CL2
time complexity.
2 Derive an algorithm to find the key element of 39 in an array CO2.2 CL2
13,9,21,15,39,19,27 using sequential search and find out the time
complexity for best, worst and average cases.
3 Consider the following example of an unsorted array that we will sort CO2.3 CL3
with the help of the selection sort using brute force approach. And
compute the time complexity A[]=(7,4,3,6,5).
4 Evaluate the shortest path using travelling salesman problem in CO2.4 CL3
brute force approach.

5 Find and analyze the optimal solution for the assignment problem C02.6 CL4
using brute force for the given below

Job/person J1 J2 J3 J4
P1 9 2 7 8
P2 6 4 3 7
P3 5 8 1 8
P4 7 6 9 4
6 Perform binary search on list of elements 5,7,9,13,32,33,42,54,56,88 and CO2.7 CL2
find the key element is 33 using divide and conquer, and also estimate the
time complexity.
7 Design an algorithm for finding pivot element in quick sort algorithm using CO2.8 CL3
the elements 5, 3, 1, 9, 8,2, 47 and analyze its time complexity.
8 Multiply the following two matrices by Strassen’s matrix multiplication CO2.9 CL3
algorithm.
A= 1 0 2 1 B= 0 1 0 1
4 1 1 0 2 1 0 4
0 1 3 0 2 0 1 1
5 0 2 1 1 3 5 0