Unit 1
Father of Algorithm, What is Algorithm, Need of an algorithm, Algorithm Vs Program, Good Algorithm, Analysis of Algorithm, Comparison of running time, Asymptotic notation, Recurrence relation, Substitution method, Iterative method, Recurrence Tree Method, Master Theorem, Extended Master Theorem.
Q1 – Which of the following shows the correct relationship among complexities?
O(√n) < O(logn) < O(n) < O(nlogn) < O(n3) < O(2n)
O(logn) < O(√n) < O(n) < O(nlogn) < O(2n) < O(n3)
O(logn) < O(√n) < O(n) < O(nlogn) < O(n3) < O(2n)
O(logn) < O(n) < O(nlogn) < O(√n) < O(n3) < O(2n)
Ans – (3)
Explanation – Let n = 64
Q2 – An algorithm is made up of 2 modulus M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order of the algorithm is
max(f(n), g(n))
min(f(n), g(n))
f(n) + g(n)
f(n)*g(n)
Ans – (1)
Explanation – This is because when we analyze the time complexity of an algorithm, we are interested in the most significant term in the expression that describes the running time as a function of the input size n. In this case, since the two modules are independent and executed in sequence, the running time of the overall algorithm would be dictated by the module that takes longer to run.
Q3 – Consider the following three claims:
(i) (n + k)m = Ɵ(nm), where k and m are constant
(ii) 2n+1 = O(2n)
(iii) 22n+1 = O(2n)
Which of the following claim is correct?
i and iii
i and ii
ii and iii
i, ii and iii
Ans – (2)
Explanation – Claim (i) is true. To see this, let k=1 and m=2
Claim (ii) is true. To see this, note that 2^(n+1) = 2 * 2^n, and so 2^(n+1) is always at most a constant multiple (namely, 2) of 2^n. Thus, we have 2^(n+1) = O(2^n).
Claim (iii) is not true. To see this, note that 2^(2n+1) = 2 * 2^(2n) = 2 * (2^n)^2. Thus, 2^(2n+1) grows faster than any constant multiple of 2^n, and so it is not in O(2^n).
Q4 – Let T(n) be defined by T(1) = 7 and T(n+1) = 3n + T(n) for all integers n ≥ 1. Which of the following represents the order of growth of T(n) as a function of ‘n’? (RPSC-2021)
Ɵ(n)
Ɵ(nlogn)
Ɵ(n2)
Ɵ(2n)
Ans – (3)
Explanation –
Let’s use recursion:
T(n+1) = 3n + T(n)
T(n) = 3(n-1) + T(n-1) = 3(n-1) + 3(n-2) + T(n-2) = 3(n-1) + 3(n-2) + … + 3(1) + T(1)
= 3(1 + 2 + … + (n-1)) + 7
= 3(n-1)(n)/2 + 7
= 3/2 n^2 – 3/2 n + 7
Therefore, the order of growth of T(n) is Ɵ(n^2), since the highest order term is n^2.
Q5 – The recurrence relation an+1 – 7an = 0 with a0 = 7, n ≥ 0 is equivalent to
an =7n-1 n ≥ 0
an =7n+1 n ≥ 0
an =7n-1 n ≥ 1
an =7n+1 n ≥ 1
Ans – (2)
Explanation –
Given a0 = 7n-1
Then, a1 = 49 = 72
Also, a2 = 243 = 73
Q6 – if T(C) = C for some constant,
otherwise, T(n) = 5/2T(2n/3) + na
The result of the above question is T(n) = Ɵ(n3) then find the value of a?
1.5
2.5
3
4
Ans – (3)
Explanation –
We use master method. In our case, we have a = 5/2, b = 3/2, and f(n) = n^a. We can compute logb(a) as follows:
Logb(a) = log(5/2)(3/2) ≈ 1.378
The result is n^3, So f(n) wins and a = 3.
Q7 – What is an algorithm?
A mathematical problem solution
The set of instructions applied on the input to get the output
Well defined set of output
A step-by-step procedure for solving a specific type of problem
Ans – (4)
Explanation –
It is not a mathematical solution or a set. The definition of the set is “collection of elements” and the definition of an element is “any one of the distinct objects that belong to that set.” The algorithm has several steps, and there are many duplicates of the same step.
An algorithm is a systematic approach to problem-solving that can be executed by either a human or a computer.
Q8 – Who is the father of algorithm?
Muhammad ibn Musa al-Khwarizmi
David Erwin Knuth
Hamiltonian
Euler
Ans – (1)
Explanation –
Muhammad ibn Musa al-Khwarizmi was a Persian mathematician and scholar who lived during the Islamic Golden Age in the 9th century. Al-Khwarizmi was a pioneer in the field of algorithm development, particularly in his work on the Hindu-Arabic numeral system and the development of algorithms for arithmetic operations using these numerals. While al-Khwarizmi is often credited with the development of algorithms, the concept of an algorithm existed long before his time, and the term “algorithm” itself is derived from the Latinized form of his name, Algoritmi.
Al-Khwarizmi is often referred to as the “father of algebra” for his contributions to the development of algebraic concepts.
https://compgeek.co.in/father-of-algorithm/ to know more
Q9 – Who is the father of ‘Analysis of Algorithm’?
Muhammad ibn Musa al-Khwarizmi
David Erwin Knuth
Hamiltonian
Euler
Ans – (2)
Explanation –
Donald Ervin Knuth was born on January 10, 1938, and is a computer scientist, mathematician, and professor emeritus at Stanford University. Knuth is known as the “father of algorithmic analysis.”
https://compgeek.co.in/what-is-algorithm/ to know more
Q10 – Characteristics of an algorithm by Donald Ervin Knuth are
Input, output, definite, finite, connective.
input, output, definite, finite, effective.
input, output, reflective, finite, effective.
input, output, reflective, finite, connective.
Ans – (2)
Explanation –
Input – There can be zero or more inputs such that there is no input in the program of hello world.
Output – At least one output must come.
Definiteness – Every instruction should be very clear and unambiguous. There should be no doubt or misunderstanding in the instruction.
Effectiveness – Every instruction should be very basic and possible and result-giving.
Finiteness – The algorithmic instruction must end after a finite number and also number of operations are finite. That is why we write the ‘End’ after the algorithm is over.
https://compgeek.co.in/what-is-algorithm/ to know more
Q11 – ‘The Art of Programming’ is written by
Hamiltonian
Kruskal
Donald Erwin Knuth
Donald L. Shell
Ans – (3)
Q12 – “Suppose computer were infinitely fast and computer memory was free”. Would you have any reason to study algorithm?
No, life is so easy
Yes, to demonstrate the algorithm was correct.
Yes, to demonstrate that the algorithm will stop after a finite instructions.
Both 3 & 4.
Ans – (4)
Q13 – If an Algorithm A1 has time complexity O(n) and space complexity O(n) and an algorithm A2 has time complexity O(nlogn) and space complexity O(1) for a problem, then which one would you choose?
A1
A2
Any one
No one
Ans – (1)
Explanation – We have a limited memory and time, but A1 has less time complexity than A2, so you should choose A1. Space is important, but time is more important.
Q 14 – When an algorithm is written in the form of a programming language, it becomes a _________
Flowchart
Program
Pseudo code
Syntax
Ans – (2)
Explanation – When an algorithm is completely written in the form of a programming language, it becomes a program.
Q15 – Define pseudocode?
Definite and terminates after a number of steps
Combination of Native & programming language
Every sentence is effective
None of these
Ans – (2)
Explanation –
Pseudocode is written only in a combination of native language and programming language.
Every other option 1 and 3 are related to algorithm.
Q16 – Arrange the following complexity of the algorithm in ascending order. (DSSSB PGT 2021)
O(2n), O(n), O(log2n), O(nlog2n), O(n2)
O(n), O(log2n), O(nlog2n), O(n2), O(2n)
O(n), O(n2), O(log2n), O(nlog2n), O(2n)
O(log2n), O(n), O(nlog2n), O(n2), O(2n)
O(log2n), O(nlog2n), O(n), O(n2), O(2n)
Ans – (3)
Explanation – if n = 8, then you will get the ascending order. Write and calculate.
Q17 – What is the time complexity of selection sort algorithms? (DSSSB PGT 2021)
O(2n)
O(nlog2n)
O(n)
O(n2)
Ans – (4)
Explanation –
When we keep the value of index 1 at a minimum, then the number of operations or comparisons will be n-1.
keep index 2 minimum, then comparisons will be n-2.
keep index 3 as minimum then comparisons will be n-3.
Similarly, there are number of operations or comparisons in the entire selection sort.
= (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1
= n(n-1)/2 = O(n2).
https://compgeek.co.in/selection-sort/ to know more.
Q18 – Two-way merge sort algorithm is used to sort the following elements in ascending order.
200, 470, 150, 80, 90, 40, 400, 300, 120, 70.
What is the order of these elements after second pass of the merge sort algorithm? (DSSSB PGT 2021)
40, 70, 80, 90, 120, 150, 200, 300, 400, 470
80, 150, 200, 470, 40, 90, 300, 400, 70, 120
40, 80, 90, 150, 200, 300, 400, 470, 70, 120
200, 470, 80, 150, 40, 90, 300, 400, 70, 120
Ans – (2)
Explanation –
Individual elements
200, 470, 150, 80, 90, 40, 400, 300, 120, 70
1st pass – Array contains 2 elements sorted
200, 470, 80, 150, 40, 90, 300, 400, 70, 120
2nd pass – Array contains 4 elements sorted
80, 150, 200, 470, 40, 90, 300, 400, 70, 120
Q19 – What is the complexity of the following code?
Sum = 0;
for(i =1; i <= n; i*=2)
for(j = 1; j <= n; j++)
sum++:
Which of the following is not a valid string? (ISRO Scientist 2020)
O(n2)
O(nlogn)
O(n)
O(nlognlogn)
Ans – (Please read explanation)
Explanation –
This question was not included to result as this question have an ambiguity.
Before going to another question, I will help you out with the problem it has. The inner loop executes n times and the outer loop executes logn times. So, total complexity for this code will be O(nlogn).
But it says “not a valid string” it means 1, 3 and 4 will be the answer because it contains extra space.
If the question says “What is the time complexity of this code” then the answer will be O(nlogn).
Q20 – Consider product of three matrices M1, M2 and M3 having w rows and x columns, x rows and y columns, and y rows and z columns. Under what condition will it take less time to compute the product as (M1M2)M3 than to compute M1(M2M3)? (ISRO Scientist 2020)
Always take the same time
(1/x + 1/z) < (1/w + 1/y)
x > y
(w+x) > (y+z)
Ans – (2)
Explanation –
This question is related to dynamic programming of matrix multiplication.
M1 = w*x
M2 = x*y
M3 = y*z
M1M2 = w*x*y
(M1M2)M3 = w*y*z
Time taken = w*x*y + w*y*z
M2M3 = x*y*z
M1(M2M3) = w*x*z
Time taken = x*y*z + w*x*z
Under what condition will it take less time to compute the product as (M1M2)M3 than to compute M1(M2M3)
=> w*x*y + w*y*z < x*y*z + w*x*z
Dividing whole equation by wxyz
=> (1/z + 1/x) < (1/w + 1/y)
