Algorithms Quiz

Algorithms are step-by-step methods for solving problems. This quiz covers Euclid’s GCD algorithm, Strassen’s matrix multiplication, divide and conquer and how time complexity is described with Big-O.

What this quiz covers

Study tip: Work through Euclid’s algorithm on paper with two or three pairs of numbers until the pattern is obvious.

Questions, answers and explanations

1. Euclid’s algorithm is used for finding ________.

  1. GCD of two numbers
  2. GCD of more than three numbers
  3. LCM of two numbers
  4. LCM of more than two numbers

Answer: GCD of two numbers

Euclid’s algorithm finds the greatest common divisor (GCD) of two integers by repeatedly replacing the larger number with the remainder of the division.

2. Who invented Euclid’s algorithm?

  1. Sieve
  2. Euclid
  3. Euclid-Sieve
  4. Gabriel Lame

Answer: Euclid

The algorithm is named after the Greek mathematician Euclid, who described it around 300 BC in his work Elements.

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

  1. 12
  2. 6
  3. 4
  4. 2

Answer: 4

GCD(12, 4): 12 divided by 4 leaves remainder 0, so the GCD is 4. This also confirms that GCD(16, 12) = GCD(12, 4) = 4.

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

  1. Simplification of fractions
  2. Performing divisions in modular arithmetic
  3. Solving quadratic equations
  4. Solving Diophantine equations

Answer: Solving quadratic equations

Euclid’s algorithm works on integers to find a GCD; it is used for fractions, modular arithmetic and Diophantine equations, but not for solving quadratic equations.

5. Euclid’s algorithm runs efficiently by repeatedly dividing until the remainder becomes zero.

  1. True
  2. False

Answer: True

The algorithm keeps dividing and taking remainders until the remainder becomes zero; the last non-zero remainder is the GCD, which makes it very efficient.

6. According to Gabriel Lame, Euclid’s algorithm requires how many steps?

  1. Less than five times the number of digits
  2. More than five times the number of digits
  3. Less than two times the number of digits
  4. More than two times the number of digits

Answer: Less than five times the number of digits

Lamé’s theorem shows the number of division steps is always less than five times the number of digits of the smaller number.

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

  1. Determination of prime numbers
  2. Lagrange’s four square theorem
  3. Cauchy-Euler theorem
  4. Residue theorem

Answer: Lagrange’s four square theorem

Euclid’s algorithm is used in number theory proofs such as Lagrange’s four-square theorem, as well as in cryptography.

8. If the GCD of two numbers is 1, they are called ________.

  1. Co-prime numbers
  2. Prime numbers
  3. Composite numbers
  4. Rational numbers

Answer: Co-prime numbers

When the GCD of two numbers is 1 they share no common factor other than 1, and such numbers are called co-prime (relatively prime).

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

  1. O(N)
  2. O(N log M)
  3. O(N log N)
  4. O(log N)

Answer: O(log N)

Each step reduces the numbers by at least half every two iterations, so the running time grows logarithmically: O(log N).

10. Euclid’s algorithm does not require calculation of prime factors.

  1. True
  2. False

Answer: True

Euclid’s algorithm only needs division and remainders, so no prime factorization is required, which is why it is much faster than factoring for large numbers.

11. What is the formula used in Euclid’s algorithm?

  1. GCD(m,n) = GCD(n, m mod n)
  2. LCM(m,n) = LCM(n, m mod n)
  3. GCD(m,n,o,p) = GCD(m, m mod n, o, p mod o)
  4. LCM(m,n,o,p) = LCM(m, m mod n, o, p mod o)

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

The core identity is GCD(m, n) = GCD(n, m mod n). It is applied repeatedly until the second argument becomes 0.

12. What is the running time of the Binary GCD algorithm?

  1. O(N)
  2. O(N²)
  3. O(log N)
  4. O(N log N)

Answer: O(log N)

The Binary GCD (Stein’s) algorithm uses shifts and subtraction instead of division, and its running time is logarithmic in the size of the inputs.

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

  1. 8
  2. 2
  3. 4
  4. 6

Answer: 4

20 mod 12 = 8, 12 mod 8 = 4, 8 mod 4 = 0. The last non-zero remainder is 4, so GCD(20, 12) = 4.

14. Strassen’s algorithm is a ________ algorithm.

  1. Non-recursive
  2. Recursive
  3. Approximation
  4. Accurate

Answer: Recursive

Strassen’s algorithm multiplies matrices by splitting them into sub-matrices and calling itself on the pieces, so it is a recursive algorithm.

15. What is the time complexity of Strassen’s algorithm?

  1. O(n²·⁸¹)
  2. O(n³)
  3. O(n¹·⁸)
  4. O(n²)

Answer: O(n²·⁸¹)

Strassen reduces the number of recursive multiplications from 8 to 7, giving a time complexity of about O(n^2.81) (n to the power log2 7).

16. What is the running time of the naive matrix multiplication algorithm?

  1. O(n²·⁸¹)
  2. O(n⁴)
  3. O(n)
  4. O(n³)

Answer: O(n³)

The standard method uses three nested loops over n elements each, so it performs about n × n × n operations, i.e. O(n³).

17. Strassen’s matrix multiplication algorithm uses which technique?

  1. Greedy
  2. Dynamic Programming
  3. Divide and Conquer
  4. Backtracking

Answer: Divide and Conquer

Strassen’s method is a divide and conquer technique: the problem is divided into smaller matrix products whose results are combined.

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

  1. O(n²·⁸¹)
  2. Θ(n²)
  3. Θ(n)
  4. O(n³)

Answer: Θ(n²)

The additions and subtractions of the sub-matrices take quadratic time, Θ(n²), at each level of the recursion.

19. Running time of Strassen’s algorithm is better than the naive Θ(n³) algorithm.

  1. True
  2. False

Answer: True

Because O(n^2.81) grows more slowly than Θ(n³), Strassen’s algorithm is asymptotically faster for large matrices, although it has more overhead for small ones.

20. In the naive matrix multiplication algorithm, what statement belongs inside the innermost loop?

  1. Z[i][j] = Z[i][j] + X[i][k] * Y[k][j]
  2. Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]
  3. Z[i][j] = Z[i][j] * X[i][k] * Y[k][j]
  4. Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: Z[i][j] = Z[i][j] + X[i][k] * Y[k][j]

In the naive method each result cell is built by accumulating products of a row of X and a column of Y: Z[i][j] = Z[i][j] + X[i][k] * Y[k][j].

Take the timed quiz