Chapter 11 The World of Algorithms
Practice questions
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
Answer and explanation
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.
How many reductions does the division method need for gcd(1071, 462), compared with 12 for the subtraction method?
- 3
- 12
- 2
- 21
Answer and explanation
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.
Find gcd(391, 299) by the division method.
- 13
- 23
- 17
- 1
Answer and explanation
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.
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
Answer and explanation
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.
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
Answer and explanation
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.
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)
Answer and explanation
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.
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
Answer and explanation
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.
For gcd(375, 825), how many possible divisors does the version that scans from 1 to min(m, n) examine?
- 1200
- 825
- 375
- 450
Answer and explanation
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.
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
Answer and explanation
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.
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
Answer and explanation
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.
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]
Answer and explanation
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.
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]
Answer and explanation
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.
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
Answer and explanation
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.
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
Answer and explanation
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.
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
Answer and explanation
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.
The word 'algorithm' comes from the name of which scholar?
- Euclid
- Āryabhaṭa
- Al-Khwārizmī
- Brahmagupta
Answer and explanation
Answer: C
Al-Khwārizmī wrote about the Indian numerals and methods of calculation around 820 CE. The Latin form of his name, Algoritmi, gave 'algorism' and then 'algorithm'.
Why is the division method much faster than the subtraction method for gcd(101, 2)?
- It uses smaller numbers from the start
- It does not need a stopping rule
- It finds the answer by guessing
- One division gives the same remainder as about 50 subtractions of 2
Answer and explanation
Answer: D
Subtracting 2 from 101 again and again ends at the remainder 1 after 50 subtractions. 101 mod 2 = 1 gives that in one step, so the whole calculation takes 2 reductions: gcd(2, 1), then gcd(1, 0).
Find gcd(1071, 462) by the division method.
- 7
- 147
- 21
- 3
Answer and explanation
Answer: C
1071 mod 462 = 147, then 462 mod 147 = 21, then 147 mod 21 = 0. The last non-zero divisor is 21, so gcd(1071, 462) = 21. Check: 1071 = 21 × 51 and 462 = 21 × 22.
Using gcd(m, n) = gcd(n, m mod n), what does gcd(252, 198) become after one step?
- gcd(198, 54)
- gcd(198, 252)
- gcd(54, 36)
- gcd(252, 54)
Answer and explanation
Answer: A
252 = 198 × 1 + 54, so 252 mod 198 = 54 and the problem becomes gcd(198, 54). gcd(54, 36) comes one step later.
What is 47 mod 6?
- 7
- 5
- 1
- 41
Answer and explanation
Answer: B
47 = 6 × 7 + 5, so the remainder is 5. The quotient 7 is not the remainder.