lOMoARcPSD|43337963

CS3401- Algorithms unit 1

Computer Science and Engineering (Anna University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Omprakash D (itmeom@gmail.com)
 lOMoARcPSD|43337963

DEPARTMENT OF CSE
II YEAR – IV SEMESTER

CS3401 ALGORITHMS

QUESTION BANK

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

CS 3401- ALGORITHMS

UNIT I
INTRODUCTION

Algorithm analysis: Time and space complexity - Asymptotic Notations and its properties
Best case, Worst case and average case analysis – Recurrence relation: substitution method -
Lower bounds – searching: linear search, binary search and Interpolation Search, Pattern
search: The naïve string- matching algorithm - Rabin-Karp algorithm - Knuth-Morris-Pratt
algorithm. Sorting: Insertion sort – heap sort

PART - A

1. What do you mean by algorithm? (Nov/Dec 2008) (May/June 2013) (Apr/May 17)
(U)
An algorithm is a sequence of unambiguous for solving a problem i.e., for obtaining a
required output for any legitimate input in a finite amount of time. In addition, all
algorithms must satisfy the following criteria:
1) Input
2) Output
3) Definiteness
4) Finiteness
5) Effectiveness.

2. What is performance measurement? (R)

Performance measurement is concerned with obtaining the space and the time
requirements of a particular algorithm.

3. Give the diagram representation of Notion of algorithm. (C)

PROBLEM

ALGORITHM

INPUT OUTPUT
COMPUTER

4. What are the types of algorithm efficiencies? (R)

The two types of algorithm efficiencies are
Time efficiency: indicates how fast the algorithm runs.
Space efficiency: indicates how much extra memory the algorithm needs.

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

5. What is space complexity? (Nov/Dec 2012) (R)

Space Complexity indicates how much extra memory the algorithm needs. Basicallyit has
three components. They are instruction space, data space and environment space.

6. What is time complexity? (Nov/Dec 2012) (R)

Time Complexity indicates how fast an algorithm runs. T (P) =Compile Time + Run
Time.(Tp) ,Where Tp is no of add, sub, mul...

7. What is an algorithm design technique? (R)

An algorithm design technique is a general approach to solving problems algorithmically
that is applicable to a variety of problems from different areas of computing.

8. What is pseudo code? (R)

A pseudo code is a mixture of a natural language and programming language constructs
to specify an algorithm. A pseudo code is more precise than a natural language and its
usage often yields more concise algorithm descriptions.

9. What are the types of algorithm efficiencies? (R)

The two types of algorithm efficiencies are
Time efficiency: indicates how fast the algorithm runs
Space efficiency: indicates how much extra memory the algorithm needs.

10. What do you mean by “worst-case efficiency” of and algorithm? (R) (Nov 17)
The worst case efficiency of an algorithm, its efficiency for the worst-case input of size n,
which is an input or inputs of size n for which the algorithm runs the longest among all
possible inputs of that size.

11. What is best-case efficiency? (R)

The best-case efficiency of an algorithm is its efficiency for the best-case input of size n,
which is an input or inputs for which the algorithm runs the fastest among all possible
inputs of that size.

12. What is average case efficiency? (May 2008) (R)

The average case efficiency of an algorithm is its efficiency for an averagecase input of
size n. It provides information about an algorithm behavior on a “typical” or “random”
input.

13. Define asymptotic notations. (R)

To choose best algorithm, we need to check efficiency of each algorithm the efficiency
can be measured by computing time complexity of each algorithm. Asymptotic notation
is shorthand way to represent the time complexity
The various notations are Big “Oh”, Big Omega, and Theta.

14. Define the asymptotic notation “Big oh” (0)(May 2008)(April/May 2012&2013) (R)
Let, f(n) and g(n) be two non-negative functions. Let, n0 and constant c are two integers
such that no denotes some value of input similarly c is constant such that c > 0. We can
write

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

F(n) <= c*g(n) For all n ≥ n0

A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by
some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c
and some non-negative integer n0 such that
T (n) < c g (n) for n > n0

15. Define the asymptotic notation “Omega” ( Ω). (R)

A function f(n) is said to be in Ω (g(n)) if f(n) is bounded below by some
positive constant multiple of g(n) such that
f(n) ≥ c * g(n) For all n ≥ n0

16. Define the asymptotic notation “theta” (θ) (R)

Let, f(n) and g(n) be two non negative functions. There are two positive constants namely
c1 and c2 such that c1 ≤ g(n) ≤ c2 g(n)
Then we can say that, f(n) ε Θ (g(n))

17. What is recursive algorithm? (R)

An algorithm is said to be recursive if the same algorithm is invoked in the body. An
algorithm that calls itself is direct recursive.

18. Define recurrence. (May2010) (R)

A recurrence is an equation or inequality that describes a function in terms of its value on
smaller inputs. The complexity of many interesting algorithms is easily expressed as a
recurrence, especially divide and conquer algorithms. The complexity of recursive
algorithms is readily expressed as a recurrence.
Example :(i)Linear search of a list

1
T (n)  for n 1
T(n -1) +1 otherwise
 search
(ii) Binary

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

1
T (n)  for n 1

T(n/2) +1 otherwise

19. Define Linear Search. (Nov/Dec 2011) (April/May 2010&2012) (R)

In computer science, linear search or sequential search is a method for finding aparticular
value in a list, which consists in checking every one of its elements, one at atime and in
sequence, until the desired one is found.

20. What are the Best, Worst and Average Case complexity of Linear Search? (R)
 Best Case – O(1)
 Average Case – O(N)
 Worst Case – O(N)

21. Difference between Best Case and Worst Case Complexities.(AN)

The best case complexity of an algorithm is its efficiency for the best case input
ofsize N, which is an input of size N for which the algorithm runs fastest among all
possible inputs of that size.
The worst case complexity of an algorithm is its efficiency for the worst case
inputof size N, which is an input of size N for which the algorithm runs longest among all
possible inputs of that size.

22. What is binary search? (R)

Binary search is a remarkably efficient algorithm for searching in a sorted
array. It works by comparing a search key K with the arrays middle element A[m]. if they
match the algorithm stops; otherwise the same operation is repeated recursively for the first
half of the array if K < A[m] and the second half if K > A[m].
a. A[0]………A[m-1] A[m] A[m+1]………A[n-1]

23. Give computing time for Binary search?(APRIL/MAY 2012) (E)

In conclusion we are now able completely describe the computing time of binary search by
giving formulas that describe the best, average and worst cases.
Successful searches
Best-(1) average-(logn) worst -(Logn)
unsuccessful searches best, average, worst-
(logn)

24. Write the algorithm for Iterative binary search? (A)

Algorithm BinSearch(a,n,x)
//Given an array a[1:n] of elements in nondecreasing
// order, n>0, determine whether x is present
{
low : = 1;
high : = n;
while (low < high) do
{
mid : = [(low+high)/2];
if(x a[mid]) then high:= mid-1;
else if (x a[mid]) then low:=mid + 1;

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

else return mid;

}
return 0;
}

25. Give the general plan for analyzing non recursive algorithm. (R)
 Decide a parameter indicating an Input’s Size.
 Identify the algorithms Basic Operation
 Check whether the number of times the basic operation is executed only on thesize of
an input. If it also depends on some additional property, the worst case, average case,
and if necessary, best case efficiencies have to be investigated separately.
 Using standard formulas and rules of sum manipulation either find a closedformula
for the count or, at the very least, establish its order of growth.

26. What is validation of algorithm? (Nov/Dec 2012) (R)

The process of measuring the effectiveness of an algorithm before it is coded to know the
algorithm is correct for every possible input. This process is called validation.

27. What are all the methods available for solving recurrence relations? (R)
 Forward Substitution
 Backward Substitution
 Smoothness Rule
 Master Theorem

28. Write down the problem types.(April/May 2008) (R)

 Sorting
 Searching
 String Processing
 Graph Problem
 Combinational Problem
 Geometric Problem
 Numerical Problem

29. What are the types of recurrence relations? (R)

 Homogeneous recurrence relation.
 Non homogeneous recurrence relation.

30. Define Substitution Method. (April /May 2010) (R)

Substitution method is a method of solving a system of equations wherein one of
theequations is solved for one variable in terms of the other variables.

31. Give the general plan for analyzing recursive algorithm. (R)
 Decide a parameter indicating an Input’s Size.
 Identify the algorithms Basic Operation

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

 Check whether the number of times the basic operation is executed only on thesize of an
input. If it also depends on some additional property, the worst case,average case, and if
necessary, best case efficiencies have to be investigatedseparately.
 Set up a recurrence relation, with an appropriate initial condition, for thenumber of times
basic operation is executed.

32. Define Recurrence Relation. (APRIL/MAY 2010) (Nov/Dec 2016) (R)

The equation defines M (N) not explicitly, ie.., is a function of n, but implicitly as
afunction of its value at another point, namely N-1. Such equations are calledrecurrence
relation.

33. Give the General Plan for the Empirical Analysis of Algorithm Time Efficiency? (C)
1. Understand the experiment’s purpose.
2. Decide on the efficiency metric M to be measured and the measurement unit (an
operation count vs. a time unit).
3. Decide on characteristics of the input sample (its range, size, and so on).
4. Prepare a program implementing the algorithm (or algorithms) for the experimentation.
5. Generate a sample of inputs.
6. Run the algorithm (or algorithms) on the sample’s inputs and record the data observed.
7. Analyze the data obtained.

34. Write down the properties of asymptotic notations?(MAY 2015) (R)

If t1(n)Ɛ O(g1(n)) and t2(n)Ɛ O(g2(n)), then
t1(n)+t2(n)Ɛ O(max{g1(n),g2(n)})

35. Give the Euclid algorithm for computing gcd(m, n) (MAY/JUN 2016) (Apr/May 17)
(APR 17) (C)
ALGORITHM Euclid_gcd(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n
m←n
n←r
return m
Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

36. Design an algorithm for computing area and circumference of the

circle. (NOV/DEC 2016) (C)
//Computes area and circumference of the circle
//Input: One non-negative integer radius
//Output: Area and Circumference of the circle

Area = PI * rad * rad;

Ci = 2 * PI * rad;
return area, ci

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

37. How to measure an algorithm running time? (NOV/DEC 2017) (R)

One possible approach is to count the number of times each of the algorithm’s operation
is executed. The thing to do is identify the most important operation of the algorithm
called as basic operation and compute the number of times the basic operation is
executed.
T(n)  Cop C(n)

38. What is a basic operation? (APR/MAY 2018) (R)

The process of identify the most important operation of the algorithm called as basic
operation

39. Define best,worst,average case time complexity. (NOV/DEC 2018)

Best case: In the best case analysis, we calculate lower bound on running time of an
algorithm. We must know the case that causes minimum number of operations to be
executed.
Worst case: In the worst case analysis, we calculate upper bound on running time of an
algorithm. We must know the case that causes maximum number of operations to be
executed.
Averge case: In average case analysis, we take all possible inputs and calculate
computing time for all of the inputs. Sum all the calculated values and divide the sum by
total number of inputs.

40. How do you measure the efficiency of an algorithm. (APR/MAY 2019)

Time efficiency - a measure of amount of time for an algorithm to execute.
Space efficiency - a measure of the amount of memory needed for an algorithm to
execute.

41. Prove that the if f(n)=O(g(n)) and g(n)=O(f(n)),then f(n)= θg (n) (APR/MAY 2019)

42. What do you mean bt interpolation search?

Interpolation search finds a particular item by computing the probe position. Initially, the
probe position is the position of the middle most item of the collection.

If a match occurs, then the index of the item is returned. To split the list into two parts,
we use the following method −
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

A[n] = Value stored at index n in the list

43. Define naïve string matching alogorithm.

The naïve approach tests all the possible placement of Pattern P [1.......m] relative to text
T [1......n]. We try shift s = 0, 1.......n-m, successively and for each shift s. Compare T
[s+1.......s+m] to P [1.....m].

The naïve algorithm finds all valid shifts using a loop that checks the condition P
[1.......m] = T [s+1.......s+m] for each of the n - m +1 possible value of s.

NAIVE-STRING-MATCHER (T, P)
1. n ← length [T]
2. m ← length [P]
3. for s ← 0 to n -m
4. do if P [1.....m] = T [s + 1....s + m]
5. then print "Pattern occurs with shift" s

44. Define Rabin-Karp algorithm.

The Rabin-Karp string matching algorithm calculates a hash value for the pattern, as well as
for each M-character subsequences of text to be compared. If the hash values are unequal,
the algorithm will determine the hash value for next M-character sequence. If the hash
values are equal, the algorithm will analyze the pattern and the M-character sequence. In
this way, there is only one comparison per text subsequence, and character matching is only
required when the hash values match.

RABIN-KARP-MATCHER (T, P, d, q)
1. n ← length [T]
2. m ← length [P]
3. h ← dm-1 mod q
4. p ← 0
5. t0 ← 0
6. for i ← 1 to m
7. do p ← (dp + P[i]) mod q
8. t0 ← (dt0+T [i]) mod q
9. for s ← 0 to n-m
10. do if p = ts
11. then if P [1.....m] = T [s+1... .s + m]
12. then "Pattern occurs with shift" s
13. If s < n-m
14. then ts+1 ← (d (ts-T [s+1]h)+T [s+m+1])mod q

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

45. Define Knuth-Morris-Pratt algorithm.

Knuth-Morris and Pratt introduce a linear time algorithm for the string matching
problem. A matching time of O (n) is achieved by avoiding comparison with an element
of 'S' that have previously been involved in comparison with some element of the pattern
'p' to be matched. i.e., backtracking on the string 'S' never occurs

46. Write the advantage of insertion sort? (NOV/DEC 2017)

1.Simple implementation
2.Efficient for small data sets
3.Adaptive
4. More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms
such as Selection sort or bubble sort; the best case (nearly sorted input) is O(n)
5. Stable - does not change the relative order of elements with equal keys

47. Define Heap sort?

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-
case running time. Heap sort involves building a Heap data structure from the given
array and then utilizing the Heap to sort the array.

48. What are the properties of heap structure?

The special heap properties given below:

Shape Property: Heap data structure is always a Complete Binary Tree, which means all

levels of the tree are fully filled.

Heap Property: All nodes are either greater than or equal to or less than or equal to
each of its children. If the parent nodes are greater than their child nodes, heap is called a
Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-
Heap.

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

49. What are the two basic parts of Heap sort ?

 Creating a Heap of the unsorted list/array.
 Then a sorted array is created by repeatedly removing the largest/smallest
element from the heap, and inserting it into the array. The heap is reconstructed
after each removal.

50. What is the Complexity Analysis of Heap Sort?

Worst Case Time Complexity: O(n*log n)
Best Case Time Complexity: O(n*log n)
Average Time Complexity: O(n*log n)
Space Complexity : O(1)

51. What are the advantages of Heap sort ?

Heap sort is not a Stable sort, and requires a constant space for sorting a list.
Heap Sort is very fast and is widely used for sorting

PART B

1. Define the asymptotic notations used for best case average case and worst case analysis?
(APIRL/MAY2009) (APRIL/MAY-2008)(R) (Apr 18)
2. How do you evaluate the performance of the algorithms? (E)
3. Explain properties of BIG (oh) Notation.(8) (MAY 2016) (R) (Nov 17)
4. What is meant by recurrence? Give one example to solve recurrence equations.
(APRIL/MAY 2012) (r)
5. (i) Distinguish between Big Oh, Theta and Omega natation. (NOV/DEC 2012) (AN)
(ii) Analyze the best, worst and average case analysis for linear search.

6. Find complexity of algorithm C (n) of the algorithm for the best, worst, average case,
(evaluate average case complexity of n=3 n mean number of inputs.) (E)
7. (i) Define Asymptotic notations. Distinguish between Asymptotic notation and
Conditional asymptotic notation. (10)(APRIL/MAY 2010)(APRIL/MAY 2011)
(Apr/May 17)
ii) Explain how the removing condition is done from the conditional asymptotic
notation with an example. (6)(NOV/DEC 2011) (R)

8. (i) Explain how analysis of linear search is done with a suitable illustration. (10)
(ii) Define recurrence equation and explain how solving recurrence equations are
done.(6) (NOV/DEC 2011) (R)

9. Explain how Time Complexity is calculated. Give an example. (APRIL/MAY 2010) (E)

10. Discuss all the asymptotic notations in detail. (APRIL/MAY 2012)(R)

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

11. Write an algorithm for finding maximum element of an array, perform best, worst and
average case complexity with appropriate order notations. (APRIL/MAY 2008) (R)

12. Write an algorithm to find mean and variance of an array perform best, worst and average
case complexity, defining the notations used for each type of analysis. (APRIL/MAY
2008) (AN)

13. (i)Briefly explain the time complexity, space complexity estimation.(6) (MAY/JUNE
2013)
(ii) Write the linear search algorithm and analyze its time complexity.(10) (Nov/Dec 2016)

14. (i)Find the time complexity and space complexity of the following problems. Factorial
using recursion and Compute nth Fibonacci number using Iterative statements. (C)

(ii) Solve the following recurrence relations: (NOV/DEC 2012) (A)

1).T(n) = n
2T ( ) + 3n > 2
2 2
n=2
𝗅
n
2T ( ) + cn n > 1
2)T(n) = { 2 Where a and c are constants.
a n=1
15. Solve the following inequalities are correct (MAY/JUNE 2013) (A)

(i)5n2 − 6n = ∅(n2)
(ii) n!=O(nn)
(iii)n3 + 10n2 = 𝜃(n3)
(iv)2n22n + nlogn = 𝜃(n22n)

16. If you have to solve the searching problem for a list of n numbers, how can you 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.(MAY
2015) (AN)

17. (i) Derive the worst case analysis of merge sort using suitable illustrations.(8)(MAY
2015)
(ii) Derive a loose bound on the following equation (8) (A)
F(x) =35x8 -22x7 +14x5 – 2x4-4x2+x-15

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

18. Give an algorithm to check whether all the Elements in a given array of n elements are
distinct. Find the worst case complexity of the same.(8) (MAY / JUNE 2016) (A)

19. Give the recursive algorithm which finds the number of binary digits in the binary
representation of a positive decimal integer. Find the recurrence relation and complexity.
(MAY / JUNE 2016) (A)

20. State the general plan for analyzing the time efficiency of non-recursive algorithm and
explain with an example. (8) (Nov/Dec 2016) (AN)

21. Solve the following recurrence relation. (A)

 x(n)=x(n-1)+5 for n>1 x(1)=0
 x(n)=3x(n-1) for n>1 x(1)=4
 x(n)=x(n-1)+n for n>1 x(0)=0
 x(n)=x(n/2)+n for n>1 x(1)=1 (solve for n=2k)
 x(n)=x(n/3)+1 for n>1 x(1)=1 (solve for n=3k) (16) (Nov/Dec 2016)

22. Briefly explain the mathematical analysis of recursive and non-recursive algorithm. (8)
(Apr/May 2017) (R)
23. Discuss the steps in mathematical analysis for recursive algorithms. Do the same for
finding the factorial of the number. (NOV/DEC 2017)
24. Give the general plan for analyzing the time efficiency of recursive algorithm and use
recurrence to find number of moves Towers of Hanoi problem. (APR/MAY 18)
25. Consider the problem of finding the smallest and largest elements in an array of n
numbers. (APR/MAY 18)
(i) Design a presorting- based algorithm for solving this problem and determine its
efficiency class. (7)

(ii) Compare the efficiency of the three algorithms: (8)

(A) the brute force algorithm (B) this presorting based algorithm (C) the divide and conquer
algorithm.
26. (i)Prove that if g(n) is Ω(f(n)) then f(n) is O(g(n)). (5) (NOV/DEC 2018)
(ii) Discuss vrious methods used for mathematical analysis of recursive algorithms.(8)
(NOV/DEC 2018)

27. Write the asymptotic notations used for best case,average case and worst case analysi of
lgorithms. Writa an algorithm for finding maximum elements in an array. Give best,worst
and average case complexities. (NOV/DEC 2018)

28. Solve the following recurrence relation: (APR/MAY 2019)

(1) T(n)=T(n/2)+1, where n=2k for all k> 0 (4)

(2) T(n)=T(n/3)+T(2n/3)+cn, where ‘c’ is a constant and ‘n’ is the input size.

29. Explains the steps involved in problem solving. (APR/MAY 2019)

30. What do you mean bt interpolation search?

Downloaded by Omprakash D (itmeom@gmail.com)

 lOMoARcPSD|43337963

31. Explain in detail about naïve string matching alogorithm.

32. Explain in detail about Rabin-Karp algorithm.
33. Explain in detail about Knuth-Morris-Pratt algorithm.
34. Explain in detail about insertion sort? (NOV/DEC 2017)

Downloaded by Omprakash D (itmeom@gmail.com)