# Number Theory in Data Structure MCQ

1. Euclid’s algorithm is used for finding ___________

a) GCD of two numbers

b) GCD of more than three numbers

c) LCM of two numbers

d) LCM of more than two numbers

Answer: a

Euclid’s algorithm is used to find the GCD of two numbers. It cannot be directly applied to three or more numbers at a time.

2. Who invented Euclid’s algorithm?

a) Sieve

b) Euclid

c) Euclid-Sieve

d) Gabriel lame

Answer: b

Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

3. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?

a) 12

b) 6

c) 4

d) 2

Answer: c

Euclid’s algorithm states that the GCD of two numbers does not change even if the bigger number is replaced by a difference between two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the same.

4. Which of the following is not an application of Euclid’s algorithm?

a) Simplification of fractions

b) Performing divisions in modular arithmetic

c) Solving quadratic equations

d) Solving diophantine equations

Answer: c

Solving quadratic equations is not an application of Euclid’s algorithm whereas the rest of the options are mathematical applications of Euclid’s algorithm.

5. Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero.

a) True

b) False

Answer: a

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.

6. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?

a) Less than five times the number of digits

b) More than five times the number of digits

c) Less than two times the number of digits

d) More than two times the number of digits

Answer: a

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.

7. Which of the following is the correct mathematical application of Euclid’s algorithm?

a) Determination of prime numbers

b) Lagrange’s four-square theorem

c) Cauchy-Euler theorem

d) Residue theorem

Answer: b

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.

8. If the GCD of two numbers is 1, then the two numbers are said to be ________

a) Co-prime numbers

b) Prime numbers

c) Composite numbers

d) Rational numbers

Answer: a

If the 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.

9. What is the total running time of Euclid’s algorithm?

a) O(N)

b) O(N log M)

c) O(N log N)

d) O(log N +1)

Answer: a

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

10. Euclidean algorithm does not require the calculation of prime factors.

a) True

b) False

Answer: a

Euclid’s algorithm does not require the calculation of prime factors. We derive the answer straight away using a formula. And also, factorization is complex.

11. What is the formula for the Euclidean algorithm?

a) GCD (m,n) = GCD (n, m mod n)

b) LCM(m,n)=LCM(n, m mod n)

c) GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)

d) LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)

Answer: a

The formula for computing the GCD of two numbers using the Euclidean algorithm is given as GCD (m,n)= GCD (n, m mod n).

It is used recursively until zero is obtained as a remainder.

12. What is the total running time of the binary GCD algorithm?

a) O(N)

b) O(N^{2})

c) O(log N)

d) O(N log N)

Answer: b

The binary GCD algorithm is a sub-division of the Euclidean algorithm with more faster operations. Its running time is given by O(N^{2}).

13. What is the GCD of 20 and 12 using Euclid’s algorithm?

a) 8

b) 2

c) 4

d) 6

Answer: c

GCD of 20 and 12 using Euclid’s algorithm

GCD(m,n)=GCD(n, m mod n)

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

= GCD(8,4)

= GCD(4,0) = 4.

1. Strassen’s algorithm is a/an_____________ algorithm.

a) Non-recursive

b) Recursive

c) Approximation

d) Accurate

Answer: b

Strassen’s Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs.

2. What is the running time of Strassen’s algorithm for matrix multiplication?

a) O(n2.81)

b) O(n3)

c) O(n1.8)

d) O(n2)

Answer: a

Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n2) scalar additions and subtractions yielding the running time is O(n^{2}.81).

3. What is the running time of naïve matrix multiplication algorithm?

a) O(n2.81)

b) O(n4)

c) O(n)

d) O(n^{3})

Answer: d

The traditional matrix multiplication algorithm takes O(n^{3}) time. The number of recursive multiplications involved in this algorithm is 8.

4. Strassen’s matrix multiplication algorithm follows ___________ technique.

a) Greedy technique

b) Dynamic Programming

c) Divide and Conquer

d) Backtracking

Answer: c

Strassen’s matrix multiplication algorithm follows the divide and conquers technique. In this algorithm, the input matrices are divided into n/2 x n/2 sub matrices and then the recurrence relation is applied.

5. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________

a) O(n2.81)

b) Theta(n^{2})

c) Theta(n)

d) O(n3)

Answer: b

Using Theta(n2) scalar additions and subtractions, 14 matrices are computed each of which is n/2 x n/2. Then seven matrix products are computed recursively.

6. Running time of Strassen’s algorithm is better than the naïve Theta(n3) method.

a) True

b) False

Answer: a

Strassen’s Algorithm requires only 7 recursive multiplications when compared with the naïve Theta(n^{3}) method which requires 9 recursive multiplications to compute the product.

7. Given the program of naïve method.

for i=1 to n do for j=1 to n do Z[i][j]=0; for k=1 to n do ___________________________

Fill in the blanks with appropriate formula

a) Z[i][j] = Z[i][j] + X[i][k]*Y[k][j]

b) Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]

c) Z[i][j] = Z[i][j] * X[i][k]*Y[k][j]

d) Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: a

In the naïve method of matrix multiplication, the number of iterating statements involved is 3, because of the presence of rows and columns.

The element in each row of one matrix is multiplied by each element in the column of the second matrix. The computed value is placed in the new matrix Z[i][j].

8. Who demonstrated the difference in numerical stability?

a) Strassen

b) Bailey

c) Lederman

d) Higham

Answer: d

The difference in the numerical stability was demonstrated by Higham. He overemphasized that Strassen’s algorithm is numerically unstable for some applications.

9. What is the recurrence relation used in Strassen’s algorithm?

a) 7T(n/2) + Theta(n^{2})

b) 8T(n/2) + Theta(n^{2})

c) 7T(n/2) + O(n2)

d) 8T(n/2) + O(n^{2})

Answer: a

The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n2) since there are only 7 recursive multiplications and Theta(n^{2}) scalar additions and subtractions involved for computing the product.

10. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?

a) Strassen

b) Lederman

c) Bailey

d) Higham

Answer: c

The submatrices formed at the levels of recursion consume space. Hence in order to overcome that Bailey discussed techniques for reducing the memory required.

11. What is the formula to calculate the element present in the second row, the first column of the product matrix?

a) M1+M7

b) M1+M3

c) M2+M4 – M5 + M7

d) M2+M4

Answer: d

The element in the second row, the 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)).

12. Strassen’s Matrix Algorithm was proposed by _____________

a) Volker Strassen

b) Andrew Strassen

c) Victor Jan

d) Virginia Williams

Answer: a

Strassen’s matrix multiplication algorithm was first published by Volker Strassen in the year 1969 and proved that the n3 general matrix multiplication algorithm wasn’t optimal.

13. How many iterating statements are involved in the naïve method of matrix multiplication?

a) 1

b) 2

c) 3

d) 4

Answer: c

In the naïve method of matrix multiplication, the number of iterating statements involved is 3, because of the presence of rows and columns in a matrix.

The element in each row of the first matrix is multiplied by each element in the column of the second matrix.

14. Strassen’s algorithm is quite numerically unstable as the naïve method.

a) True

b) False

Answer: a

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).

15. Compute the product matrix using Strassen’s matrix multiplication algorithm.

Given a11=1; a12=3;a21=5;a22=7

b11=8;b12=4;b21=6;b22=2

a) c11=20;c12=12;c21=100;c22=15

b) c11=22;c12=8;c21=90;c22=32

c) c11=15;c12=7;c21=80;c22=34

d) c11=26;c12=10;c21=82;c22=34

Answer: d

The solution can be obtained by

C11=1*8 + 3*6 =8+18=26

C12=1*4 + 3*2 =4+6=10

C21=5*8 + 7*6 =40+42=82

C22= 5*4 + 7*2=20+14=34.

1. What is a pseudo-random number generator?

a) an algorithm that generates random numbers with help of mathematical formula

b) an algorithm that generates random numbers according to user activity

c) an algorithm that generates random numbers according to time

d) an algorithm that generates random numbers with help of user input

Answer: a

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.

2. What should be the return type of the rand() function?

a) int

b) float

c) long

d) double

Answer: a

The return type of rand () is int. It can generate random numbers from 0 to RAND_MAX.

3. What is the purpose of using function srand()?

a) to set the seed of rand() function

b) to generate random numbers

c) to enable rand() function

d) to improve the efficiency of rand()

Answer: a

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

4. What is the range of rand()?

a) 0 to RAND_MAX

b) 0 to infinity

c) 0 to 2147483647

d) 0 to 32767

Answer: a

The function rand() generates random numbers in the range 0 to RAND_MAX. The value of RAND_MAX is a minimum of 32,767.

5.What is the correct formula for generating random numbers in the range (lower,upper) using rand()?

a) rand() % (upper – lower)

b) rand() + lower

c) (rand()%(upper-lower)) + lower

d) (rand()%(upper-lower+1)) + lower

Answer: d

The correct formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. The function rand() generates random numbers in the range 0 to RAND_MAX.

6. Which of the following will generate random numbers in the range 1-100 (both inclusive)?

a) rand() % 100

b) rand() % 101

c) (rand() % (101)) + 1

d) (rand() % (100)) + 1

Answer: d

Formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. So the correct answer will be (rand() % (100)) + 1.

7. What is the minimum value of RAND_MAX possible in any implementation?

a) 0

b) 32767

c) 2147483647

d) 128

Answer: b

The value of RAND_MAX varies according to implementation. But it is guaranteed to be at least 32767.

8. Function rand() does not generate unique random numbers every time.

a) true

b) false

Answer: a

Function rand() does not generate unique random numbers every time. For achieving this we have to use srand() along with rand().

9. What is the default value of seed if function rand() is called before srand()?

a) srand(0)

b) srand(1)

c) srand(time(null))

d) srand(-1)

Answer: b

If srand() is not called before the call to the function rand() then the value of the seed is taken as srand(1) by default. We should use srand() before rand() in order to use our own seed.

10. Pseudo-random number generators cannot be used for data encryption.

a) true

b) false

Answer: a

Pseudo-random number generators cannot be used for data encryption as the random numbers generated by them are predictable. For data encryption, the numbers should be absolutely unpredictable.

12. Which header file contains the function rand() in C language?

a) stdlib

b) iostream

c) stdio

d) time

Answer: a

In C language the header file stdlib contains the function rand(). It generates pseudo-random numbers.

1. The dictionary ordering of elements is known as?

a) Lexicographical order

b) Colexicographical order

c) Well order

d) Sorting

Answer: a

Lexicographical order is also known as dictionary order. It is a generalized method of the way words are alphabetically ordered in a dictionary.

2. How many permutations will be formed from the array arr={1,2,3}?

a) 2

b) 4

c) 6

d) 8

Answer: c

The formula nPn will give No. of permutations for an array of size n. So for the given problem, we have 3P3=6 or 3!=6.

3. What will be the lexicographical order of permutations formed from the array arr={1,2,3}?

a) {{2,1,3},{3,2,1},{3,1,2},{2,3,1},{1,2,3},{1,3,2}}

b) {{1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,2,1},{3,1,2}}

c) {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}

d) {{2,1,3},{3,1,2},{3,2,1},{2,3,1},{1,2,3},{1,3,2}}

Answer: c

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}}.

5. Heap’s algorithm does not require an auxiliary array to create permutations.

a) true

b) false

Answer: a

Heap’s algorithm does not require any extra array for generating permutations. Thus it can keep its space requirement to a very low level. This makes it a preferable algorithm for generating permutations.

6. What is the time complexity of Heap’s algorithm?

a) O(n log n)

b) O(n^{2})

c) O(n*n!)

d) O(n!)

Answer: d

The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). It is calculated by using the substitution method. It is found to be equal to O(n!).

11. What will be the output of the code that generates permutations and also can handle duplicates, for the input str[]=” AA”?

a) AA

b) AA,AA

c) A, A

d) A

Answer: a

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.

1. What is meant by the term lexicographical order?

a) dictionary ordering of elements

b) reverse dictionary ordering of elements

c) to sort according to the value of the first element

d) to sort according to the value of the last element

Answer: a

Lexicographical order is nothing but the dictionary order or preferably the order in which words appear in the dictionary. It is a generalized method of the way words are alphabetically ordered in a dictionary.

2. How many combinations of 2 elements will be formed from the array arr={1,2,3}?

a) 1

b) 2

c) 3

d) 4

Answer: c

The formula nCr will give No.of combinations of r elements for an array of size n. So for the given problem, we have 3C2=3.

3. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?

a) {{2,1},{3,2},{3,1}}

b) {{1,2},{2,3},{1,3}}

c) {{1,2},{1,3},{2,3}}

d) {{2,1},{3,1},{3,2}}

Answer: c

The number of combinations for the problem will be 3 according to the formula 3C2. When ordered in lexicographical manner these will be {{1,2},{1,3},{2,3}}.

4. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from an array of size n?

a) O(n*r)

b) O(n/r)

c) O(n)

d) O(r)

Answer: d

Code to print combinations will require an auxiliary space of O(r) other than call stack memory. This memory is required by an array that is used for storing combinations formed.

5. The code for printing combinations is not in-place.

a) true

b) false

Answer: a

Code to print combinations will require an auxiliary space of O(r) other than call stack memory. So it is not an in-place algorithm.

6. What will be the time complexity of the code to print combinations?

a) O(n)

b) O(n2)

c) O(n log n)

d) O(2^{n})

Answer: d

The recurrence relation of the code to print combinations will be T(n)=2T(n-1)+k. It is found to be equal to O(2^{n}).

1. What is meant by integer partition?

a) representing an integer as a sum of positive and negative real numbers

b) representing an integer as a sum of positive and negative integers

c) representing an integer as a sum of positive integers

d) representing an integer as a sum of positive real numbers

Answer: c

Integer partition is the way of representing an integer as a sum of positive integers. Partitions differing only in their order are considered to be the same.

2. How many partitions will be formed for integer 3?

a) 2

b) 3

c) 4

d) 8

Answer: b

We need to find the combinations of positive integers which give 3 as their sum. These will be {3}, {2,1}, {1,1,1}. Thus the correct answer is 3.

3. What is meant by number theory?

a) study of integers

b) study of complex numbers

c) numerology

d) theory of the origination of mathematics

Answer: a

Number theory is a branch of mathematics that deals with the study of integers. Partitioning of a number comes under the study of number theory.

4. Which of the following is true according to Ramanujan’s congruence?

a) No. of partitions are divisible by 5 for a number 3 more than a multiple of 5

b) No. of partitions are divisible by 5 for a number 4 more than a multiple of 5

c) No. of partitions are divisible by 5 for a number 2 more than a multiple of 5

d) No. of partitions are divisible by 5 for a number 1 more than a multiple of 5

Answer: b

Ramanujan’s congruence is some relations found for the no. of partitions of an integer. According to it, the number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5.

5. The no. of partitions of which of the following integer will be divisible by 5?

a) 3

b) 5

c) 9

d) 6

Answer: c

According to Ramanujan’s congruence number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5. So out of the given options, 9 is the only integer that satisfies this condition.

1. What is meant by the power set of a set?

a) subset of all sets

b) set of all subsets

c) set of particular subsets

d) empty set

Answer: b

Power set of a set is defined as the set of all subsets. Ex- S={1,2} then P={{},{1},{2}{1,2}}.

2. What Number of elements in the power set of set S={1,2,3} will be?

a) 2

b) 4

c) 6

d) 8

Answer: d

The power set of a set is defined as the set of all subsets. A number of elements in the power set of a set having n elements are given as 2n. Thus, here the number of elements will be 23=8.

3. What Number of elements in the power set of set S={1,2,2} will be?

a) 2

b) 4

c) 6

d) 8

Answer: c

For finding the number of elements in the power set of the given set we need to remove duplicates. So we will be left with 6 unique elements which will be P={{},{1},{2},{1,2},{2,2},{1,2,2}}.

9. The number of elements in the power set decreases when there are duplicates present in the set.

a) True

b) False

Answer: a

In case when duplicates are present in the set then the number of elements in the power set decreases. It is because we remove subsets with identical elements.

1. Which one of the following problem types does the inclusion-exclusion principle belong to?

a) Numerical problems

b) Graph problems

c) String processing problems

d) Combinatorial problems

Answer: d

The 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.,).

2. Which of the following is a correct representation of inclusion-exclusion principle (|A, B| represents the intersection of sets A, B)?

a) |A U B|=|A|+|B|-|A,B|

b) |A,B|=|A|+|B|-|A U B|

c) |A U B|=|A|+|B|+|A,B|

d) |A,B|=|A|+|B|+|A U B|

Answer: a

The formula for computing the union of two sets according to the inclusion-exclusion principle is |A U B|=|A|+|B|-|A, B| where |A, B| represents the intersection of the sets A and B.

3. ____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability.

a) Inclusion-exclusion principle

b) Quick search algorithm

c) Euclid’s algorithm

d) Set theory

Answer: a

Inclusion-exclusion principle serves as one of the most useful principles of enumeration in combinationatorics and discrete probability because it provides a simple formula for generalizing results.

4. Which of the following is not an application of the inclusion-exclusion principle?

a) Counting intersections

b) Graph coloring

c) Matching of bipartite graphs

d) Maximum flow problem

Answer: d

Counting intersections, Graph coloring, and Matching of bipartite graphs are all examples of the inclusion-exclusion principle whereas the maximum flow problem is solved using the Ford-Fulkerson algorithm.

5. Who invented the concept of inclusion-exclusion principle?

a) Abraham de Moivre

b) Daniel Silva

c) J.J. Sylvester

d) Sieve

Answer: a

The concept of the 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.

6. According to the inclusion-exclusion principle, an n-tuple-wise intersection is included if n is odd.

a) True

b) False

Answer: a

According to the inclusion-exclusion principle, an n-tuple-wise intersection is included if n is odd and excluded if n is even.

7. With reference to the given Venn diagram, what is the formula for computing |AUBUC| (where |x, y| represents the intersection of sets x and y)?

a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C|

b) |A, B,C|=|A|+|B|+|C|-|A U B|-|A U C|-|B U C|+|A U B U C|

c) |A, B,C|=|A|+|B|+|C|+|A,B|-|A,C|+|B,C|+|A U B U C|

d) |A U B U C|=|A|+|B|+|C| + |A,B| + |A,C| + |B,C|+|A, B,C|

Answer: a

The formula for computing the union of three sets using the 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.

8. Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle?

a) including cardinalities of sets

b) excluding cardinalities of pairwise intersections

c) excluding cardinalities of triple-wise intersections

d) excluding cardinalities of quadruple-wise intersections

Answer: c

According to the 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.

9. Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing.

a) true

b) false

Answer: a

The application of counting intersections can be fulfilled if and only if it is combined with De Morgan laws to count the cardinality of the intersection of sets.

10. Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3, and 5.

a) 22

b) 25

c) 26

d) 33

Answer: c

Consider sample space S={1,…100}. Consider three subsets A, B, and C that have elements that are divisible by 2, 3, and 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.

11. ____________ 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.

a) Euler’s phi function

b) Euler’s omega function

c) Cauchy’s totient function

d) Legrange’s function

Answer: a

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.

12. Let A={1,2,3} B={2,3,4} C={1,3,5} D={2,3}. Find the cardinality of the sum of all the sets.

a) 6

b) 5

c) 4

d) 7

Answer: b

First, include the cardinalities of all the sets. Then, exclude the cardinalities of even intersections. Then include the cardinalities of odd intersections.

Hence, 3+3+3+2-2-2-2-1-2-1+1+2+1+1-1=5.