- 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. When 4875 + 3649 is worked out by the column addition algorithm, in how many columns is a carry of 1 produced?
- 1
- 2
- 3
- 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. Adding two 5-digit numbers instead of two 3-digit numbers multiplies the work of counting dots by about how much?
- 10
- 100
- 2
- 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. How should the column addition algorithm be changed to add decimals such as 12.75 + 3.6?
- Line up the left-hand digits
- Remove the decimal points and add as whole numbers
- Add the whole-number parts and the decimal parts separately without carrying
- 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. divisors(45) is being executed. What is list-of-divisors just after j = 10 has been checked?
- [1, 3, 5, 9]
- [1, 3, 5, 9, 15, 45]
- [1, 3, 5]
- [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. What does prime(91) report, and what is the list D = divisors(91)?
- Prime, with D = [1, 91]
- Not prime, with D = [1, 7, 13, 91]
- Not prime, with D = [1, 3, 7, 13, 91]
- 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. Which algorithm correctly produces the list of prime divisors of n?
- Report divisors(n) unchanged
- Report the first two entries of divisors(n)
- For each j from 1 to n, add j if j is prime
- 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. The list-free gcd algorithm is run for gcd(48, 60). Which values does most-recent-common-divisor take, in order?
- 1, 2, 3, 4, 6, 12
- 1, 2, 4, 8, 12
- 1, 2, 3, 4, 6, 8, 12
- 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. For gcd(375, 825), how many possible divisors does the version that scans from 1 to min(m, n) examine?
- 1200
- 825
- 375
- 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. In the list-free gcd algorithm, the smaller number grows from 3 digits to 5 digits. Roughly how does the work change?
- It doubles
- It grows about 10 times
- It grows about 20 times
- 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. Euclid's subtraction algorithm is run for gcd(56, 21). Which of these problems does NOT appear during the run?
- gcd(21, 14)
- gcd(14, 7)
- gcd(21, 7)
- 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. d divides n and d divides m − n. Which argument shows that d divides m?
- m is larger than n
- n = xd and m − n = yd, so m = n + (m − n) = (x + y)d
- d must equal 1
- 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. Euclid's subtraction algorithm needs about k reductions for gcd(2k + 1, 2). About how many does it need for gcd(1001, 2)?
- About 3
- About 50
- About 500
- 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. Find gcd(391, 299) by the division method.
- 13
- 23
- 17
- 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. How many reductions does the division method need for gcd(1071, 462), compared with 12 for the subtraction method?
- 3
- 12
- 2
- 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. Why may gcd(m, n) be replaced by gcd(n, m mod n)?
- Because m mod n is always 1
- Because the remainder is always larger than n
- Because division is faster than multiplication
- 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.