Explore topic-wise InterviewSolutions in .

The correct answer is (a) EULER’s PHI function

The BEST explanation: Euler’s phi function is an arithmetic function that calculates the TOTAL number of positive integers less than or equal to some number n, that are relatively PRIME to n. The inclusion-exclusion principle is used to obtain a formula for Euler’s phi function.

The correct choice is (c) 26

Easiest explanation - Consider sample space S={1,…100}. Consider three subsets A, B, C that have ELEMENTS that are DIVISIBLE by 2, 3, 5 respectively. Find integers that are divisible by A and B, B and C, A and C. Then find the integers that are divisible by A, B, C. Applying the inclusion-exclusion principle, 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

The correct option is (a) true

For explanation: The APPLICATION of counting intersections can be fulfiled if and only if it is COMBINED with DE MORGAN laws to count the cardinality of intersection of sets.

The correct answer is (c) EXCLUDING cardinalities of triple-wise intersections

To EXPLAIN: According to inclusion-exclusion principle, an intersection is included if the intersecting ELEMENTS are odd and EXCLUDED, if the intersecting elements are even. HENCE triple-wise intersections should be included.

Right answer is (a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C|

Best explanation: The formula for COMPUTING the union of three SETS using inclusion-exclusion principle is|A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C|where |A,B|, |B,C|, |A,C|, |A,B,C| represents the intersection of the sets A and B, B and C, A and C, A, B and C respectively.

The CORRECT option is (B) False

The best explanation: According to inclusion-exclusion PRINCIPLE, a N-tuple wise intersection is included if n is odd and excluded if n is even.

The CORRECT answer is (a) Abraham de Moivre

Best explanation: The concept of inclusion- exclusion principle was INITIALLY INVENTED by Abraham de Moivre in 1718 but it was published first by Daniel Silva in his PAPER in 1854.

The correct option is (d) Maximum flow PROBLEM

The best I can explain: Counting intersections, Graph COLORING and Matching of bipartite graphs are all EXAMPLES of inclusion-exclusion principle whereas maximum flow problem is SOLVED USING Ford-Fulkerson algorithm.

Correct option is (a) Inclusion-exclusion principle

Explanation: Inclusion-exclusion principle SERVES as one of the most useful PRINCIPLES of enumeration in combinationatorics and discrete probability because it provides SIMPLE FORMULA for generalizing RESULTS.

The correct option is (a) |A U B|=|A|+|B|-|A,B|

Explanation: The FORMULA for computing the union of two sets according to inclusion-exclusion principle is |A U B|=|A|+|B|-|A,B| where |A,B| REPRESENTS the INTERSECTION of the sets A and B.

The correct option is (d) Combinatorial problems

Easiest explanation - Inclusion-Exclusion principle is a kind of combinatorial problem. It is a COUNTING technique to obtain the NUMBER of elements present in SETS( two, THREE , etc.,).

Correct choice is (a) AA

Easy EXPLANATION - If a CODE is able to HANDLE duplicates then the two A’s are not CONSIDERED to be different elements DUE to which only one permutation will be formed. So the output will be AA only.

Correct OPTION is (b) false

Easy explanation - HEAP’s algorithm does not require any extra ARRAY for generating PERMUTATIONS. Thus it is ABLE to keep its space requirement to a very low level. This makes it preferable algorithm for generating permutations.

Right OPTION is (d) O(N!)

The explanation is: The recurrence RELATION for the HEAP’s algorithm is given by the expression T(n)=n * T(n-1). It is CALCULATED by using substitution method. It is found to be equal to O(n!).

Correct OPTION is (c) 6

The best I can explain: No.of PERMUTATIONS for an ARRAY of size n will be GIVEN by the formula nPn. So for the given problem, we have 3P3=6 or 3!=6.

The correct option is (c) {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}

Explanation: The NUMBER of permutations for the problem will be 6 according to the FORMULA 3P3. When ORDERED in LEXICOGRAPHICAL manner these will be {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.

The correct OPTION is (a) int

Easiest explanation - The return TYPE of RAND () is int. It can generate random NUMBERS from 0 to RAND_MAX.

Correct option is (a) LEXICOGRAPHICAL order

The best I can explain: Lexicographical order is also known as DICTIONARY order. It is a generalized method of the WAY words are alphabetically ORDERED in a dictionary.

Correct answer is (a) to SET the SEED of RAND() function

Easiest EXPLANATION - The function srand() sets the seed of rand(). It can be used to GENERATE a unique set of random numbers every time.

The correct OPTION is (a) an algorithm that GENERATES random numbers with help of mathematical formula

The explanation is: A pseudo random NUMBER generator generates random numbers with the help of a mathematical formula. We can seed the random number generator with a different value EVERYTIME if we want unique random numbers to be generated.

Right CHOICE is (a) Volker Strassen

Best explanation: Strassen’s MATRIX multiplication algorithm was first published by Volker Strassen in the year 1969 and proved that the n^3 general matrix multiplication algorithm wasn’t OPTIMAL.

Right answer is (b) False

Easiest explanation - Strassen’s ALGORITHM is too numerically UNSTABLE for some applications.The computed result C=AB satisfies the INEQUALITY with a unit ROUNDOFF error which corresponds to strong STABILITY inequality(obtained by replacing matrix norms with absolute values of the matrix elements).

The correct OPTION is (d) M2+M4

The EXPLANATION is: The element at second ROW, first column can be found by the formula M2 + M4, where M2 and M4 can be calculated by

M2= (A(2,1) + A(2,2)) B(1,1)

M4=A(2,2)(B(1,2) – B(1,1)).

Right answer is (c) Bailey

Explanation: The submatrices formed at the LEVELS of recursion consume SPACE. Hence in ORDER to overcome that Bailey discussed TECHNIQUES for reducing the memory required.

Right choice is (a) 7T(n/2) + Theta(n^2)

To explain: The recurrence RELATION used in STRASSEN’s algorithm is 7T(n/2) + Theta(n^2) since there are only 7 recursive MULTIPLICATIONS and Theta(n^2) scalar additions and subtractions involved for computing the product.

The correct option is (d) Higham

Best explanation: The DIFFERENCE in the NUMERICAL stability was demonstrated by Higham. He overemphasized that STRASSEN’s algorithm is numericaly UNSTABLE for some APPLICATIONS.

Correct ANSWER is (a) True

To explain: Strassen’s ALGORITHM requires only 7 recursive multiplications when compared with the naïve THETA(n^3) method which reuires 9 recursive multiplications to compute the product.

Correct answer is (b) THETA(n^2)

EXPLANATION: Using Theta(n^2) scalar additions and subtractions, 14 matrices are computed each of which is n/2 X n/2. Then seven matrix products are computed RECURSIVELY.

Right answer is (c) Divide and Conquer

Best explanation: Strassen’s matrix multiplication algorithm follows divide and conquer technique. In this algorithm the input matrices are divided into n/2 X n/2 sub matrices and then the RECURRENCE RELATION is applied.

Correct answer is (d) O(n^3)

The best explanation: The traditional matrix MULTIPLICATION algorithm takes O(n^3) TIME. The number of recursive MULTIPLICATIONS involved in this algorithm is 8.

Correct answer is (a) O(n^2.81)

The best EXPLANATION: Strassen’s matrix algorithm requires only 7 RECURSIVE multiplications of n/2 x n/2 matrix and THETA(n^2) SCALAR ADDITIONS and subtractions yielding the running time as O(n^2.81).

The CORRECT ANSWER is (c) 4

Explanation: GCD(m,n)=GCD(n, m MOD n)

GCD(20,12)=GCD( 12,8)

= GCD(8,4)

= GCD(4,0) = 4.

Right choice is (B) O(N^2)

For explanation: Binary GCD algorithm is a sub division of Euclidean algorithm with more FASTER operations. Its running TIME is given by O(N^2).

The correct option is (a) GCD (m,n) = GCD (n, m MOD n)

The best explanation: The FORMULA for computing GCD of two numbers using Euclidean ALGORITHM is given as GCD (m,n)= GCD (n, m mod n). It is used recursively until ZERO is obtained as a remainder.

The correct choice is (a) True

The explanation is: EUCLID’s algorithm does not require the CALCULATION of prime factors. We derive the answer STRAIGHT away USING formula. And also, factorization is complex.

The correct CHOICE is (a) O(N)

The BEST explanation: The total running time of EUCLID’s algorithm according to Lame’s analysis is found to be O(N).

Right choice is (a) Co-prime numbers

The best I can EXPLAIN: If GCD of two numbers is 1, they are called as co-prime or relatively prime numbers. It does not MEAN that they are prime numbers. They don’t have any prime factors in COMMON.

The CORRECT choice is (b) Lagrange’s FOUR square theorem

Easy explanation - Lagrange’s four square theorem is ONE of the mathematical applications of Euclid’s algorithm and it is the basic tool for proving theorems in number THEORY. It can be generalized into other TYPES of numbers like the Gaussian integers.

Right option is (a) Less than five times the number of digits

Best explanation: The EUCLID’s algorithm requires less than five times the number of digits. It runs by DIVIDING two NUMBERS. It stops when a remainder ZERO is reached.

Correct choice is (a) True

For explanation: The Euclid’s algorithm runs EFFICIENTLY if the remainder of two NUMBERS is DIVIDED by the MINIMUM of two numbers until the remainder is zero. This improvement in efficiency was put forth by Gabriel Lame.

The correct choice is (b) Euclid

To EXPLAIN: Euclid invented Euclid’s ALGORITHM. Sieve PROVIDED an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

Correct choice is (C) SOLVING quadratic equations

Easy explanation - Solving quadratic equations is not an application of Euclid’s algorithm WHEREAS the rest of the OPTIONS are mathematical APPLICATIONS of Euclid’s algorithm.

The correct choice is (C) 4

The BEST I can EXPLAIN: Euclid’s ALGORITHM states that the GCD of two NUMBERS does not change even if the bigger number is replaced by a difference of two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the same.

The correct option is (a) GCD of TWO numbers

To explain: EUCLID’s algorithm is basically USED to find the GCD of two numbers. It cannot be DIRECTLY APPLIED to three or more numbers at a time.