• Foundation
  • About 30 min
  • 15 practice questions

Final self-assessment: The World of Algorithms

Test yourself on the whole course: 15 questions with answers explained.

If something looks wrong, please tell us.

Attempt all 15 questions in one sitting of about 30 minutes, writing down your working and traces. The questions mix ideas from all five lessons and are a little harder than the lesson checks. Check your answers only after you finish, and read every explanation, including those for questions you got right.

Final self-assessment

  1. 1. When 4875 + 3649 is worked out by the column addition algorithm, in how many columns is a carry of 1 produced?

    1. 1
    2. 2
    3. 3
    4. 4
    Show answer

    Answer: C. Units: 5 + 9 = 14, carry 1. Tens: 7 + 4 + 1 = 12, carry 1. Hundreds: 8 + 6 + 1 = 15, carry 1. Thousands: 4 + 3 + 1 = 8, carry 0. So three columns produce a carry, and the sum is 8524.

  2. 2. Adding two 5-digit numbers instead of two 3-digit numbers multiplies the work of counting dots by about how much?

    1. 10
    2. 100
    3. 2
    4. 1000
    Show answer

    Answer: B. Two more digits make the numbers about 10 × 10 = 100 times larger, so there are about 100 times as many dots to count. The column method needs only 2 more columns.

  3. 3. How should the column addition algorithm be changed to add decimals such as 12.75 + 3.6?

    1. Line up the left-hand digits
    2. Remove the decimal points and add as whole numbers
    3. Add the whole-number parts and the decimal parts separately without carrying
    4. Line up the decimal points, treat a missing digit as 0, and carry as usual
    Show answer

    Answer: D. Lining up the decimal points puts tenths under tenths and hundredths under hundredths: 12.75 + 3.60. Carrying works as before, giving 16.35. Lining up the left-hand digits would add digits of different place values.

  4. 4. divisors(45) is being executed. What is list-of-divisors just after j = 10 has been checked?

    1. [1, 3, 5, 9]
    2. [1, 3, 5, 9, 15, 45]
    3. [1, 3, 5]
    4. [1, 3, 5, 9, 10]
    Show answer

    Answer: A. Among j = 1 to 10, the divisors of 45 are 1, 3, 5 and 9 (10 does not divide 45). 15 and 45 are added only later, when j reaches them.

  5. 5. What does prime(91) report, and what is the list D = divisors(91)?

    1. Prime, with D = [1, 91]
    2. Not prime, with D = [1, 7, 13, 91]
    3. Not prime, with D = [1, 3, 7, 13, 91]
    4. Prime, with D = [1, 13, 91]
    Show answer

    Answer: B. 91 = 7 × 13, so divisors(91) = [1, 7, 13, 91], which has 4 entries, not 2. So 91 is not prime. 3 does not divide 91, because 9 + 1 = 10 is not a multiple of 3.

  6. 6. Which algorithm correctly produces the list of prime divisors of n?

    1. Report divisors(n) unchanged
    2. Report the first two entries of divisors(n)
    3. For each j from 1 to n, add j if j is prime
    4. Start with an empty list; for each d in divisors(n), if prime(d) reports 'prime', add d to the list
    Show answer

    Answer: D. We need numbers that are both divisors of n and prime, so we filter divisors(n) using prime(d). Adding every prime up to n would include primes that do not divide n, and the first two divisors include 1, which is not prime.

  7. 7. The list-free gcd algorithm is run for gcd(48, 60). Which values does most-recent-common-divisor take, in order?

    1. 1, 2, 3, 4, 6, 12
    2. 1, 2, 4, 8, 12
    3. 1, 2, 3, 4, 6, 8, 12
    4. 1, 12
    Show answer

    Answer: A. k runs from 2 to 48. Values that divide both 48 and 60 are 2, 3, 4, 6 and 12 (8 does not divide 60, and 24 does not divide 60). So the value goes 1, 2, 3, 4, 6, 12, and gcd(48, 60) = 12.

  8. 8. For gcd(375, 825), how many possible divisors does the version that scans from 1 to min(m, n) examine?

    1. 1200
    2. 825
    3. 375
    4. 450
    Show answer

    Answer: C. min(375, 825) = 375, so j runs from 1 to 375: 375 values. The first algorithm examined 375 + 825 = 1200 and the combined scan 825.

  9. 9. In the list-free gcd algorithm, the smaller number grows from 3 digits to 5 digits. Roughly how does the work change?

    1. It doubles
    2. It grows about 10 times
    3. It grows about 20 times
    4. It grows about 100 times
    Show answer

    Answer: D. The algorithm checks every k up to the smaller number. Two more digits make that number about 100 times larger, so about 100 times as many values are checked.

  10. 10. Euclid's subtraction algorithm is run for gcd(56, 21). Which of these problems does NOT appear during the run?

    1. gcd(21, 14)
    2. gcd(14, 7)
    3. gcd(21, 7)
    4. gcd(7, 0)
    Show answer

    Answer: C. The run is gcd(56, 21) → gcd(21, 35) → swap gcd(35, 21) → gcd(21, 14) → gcd(14, 7) → gcd(7, 7) → gcd(7, 0), giving 7. gcd(21, 7) never appears.

  11. 11. d divides n and d divides m − n. Which argument shows that d divides m?

    1. m is larger than n
    2. n = xd and m − n = yd, so m = n + (m − n) = (x + y)d
    3. d must equal 1
    4. m − n is smaller than m
    Show answer

    Answer: B. Adding the two expressions gives m = xd + yd = (x + y)d, which is d times a whole number, so d divides m. Sizes alone prove nothing about divisibility.

  12. 12. Euclid's subtraction algorithm needs about k reductions for gcd(2k + 1, 2). About how many does it need for gcd(1001, 2)?

    1. About 3
    2. About 50
    3. About 500
    4. About 1000
    Show answer

    Answer: C. 1001 = 2k + 1 gives k = 500. Each reduction takes away only 2, so about 500 reductions are needed. The division method would need only 2.

  13. 13. Find gcd(391, 299) by the division method.

    1. 13
    2. 23
    3. 17
    4. 1
    Show answer

    Answer: B. 391 = 299 × 1 + 92 → gcd(299, 92). 299 = 92 × 3 + 23 (92 × 3 = 276) → gcd(92, 23). 92 = 23 × 4 + 0 → gcd(23, 0). Answer 23. Check: 391 = 23 × 17 and 299 = 23 × 13.

  14. 14. How many reductions does the division method need for gcd(1071, 462), compared with 12 for the subtraction method?

    1. 3
    2. 12
    3. 2
    4. 21
    Show answer

    Answer: A. gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0): 3 reductions. 21 is the gcd itself, not the number of steps.

  15. 15. Why may gcd(m, n) be replaced by gcd(n, m mod n)?

    1. Because m mod n is always 1
    2. Because the remainder is always larger than n
    3. Because division is faster than multiplication
    4. Because m mod n = m − q × n, so m, n and n, m mod n have exactly the same common divisors
    Show answer

    Answer: D. If m = q × n + r, then r = m − q × n. Any d dividing m and n divides r, and any d dividing n and r divides q × n + r = m. The common divisors are the same, so the gcd is the same.

Questions 1-3: lesson 1 (column addition as an algorithm). Questions 4-6: lesson 2 (divisors and prime). Questions 7-9: lesson 3 (first gcd algorithm and improvements). Questions 10-12: lesson 4 (Euclid's subtraction algorithm). Questions 13-15: lesson 5 (the division method).

Sign in to keep track of the lessons you finish.

Privacy · Terms · Refunds · Delivery