Algorithms: Questions and Answers

28 algorithms questions solved step by step. Open a question for the full working, the marks for each step and exam practice.

• These days the word ‘algorithm’ pops up everywhere. What exactly is an algorithm? What does it have to do with mathematics?Answer: An algorithm is a step-by-step procedure, written down precisely, that always leads to the answer of a problem. Mathematics is full of them: the column method for adding 473 + 695 = 1168 is an algorithm.
• Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?Answer: 4785 + 3692 = 8477, and the steps give it correctly. But the steps fail when a column adds up to exactly 10 (for example 3456 + 2154, where 6 + 4 = 10): the steps only say what to do when the sum is less than 10 or more than 10.
• What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?Answer: Not as written. After 3 columns the shorter number has no digits left, but Step 3 says “add the two digits”, so the steps do not say what to do. Treat the missing digits as 0 (e.g. 389 = 00389); then 52746 + 389 = 53135 correctly.
• Why is it important to align the columns from right to left?Answer: So that digits with the same place value (units under units, tens under tens, …) are added together. If numbers are aligned from the left, digits of different place values get added and the answer is wrong (473 + 25 would come out as 723 instead of 498).
• In Step 3, why cannot the value of carry be more than 1?Answer: The biggest possible column sum is 9 + 9 + 1 = 19, which is less than 20. So a column never makes two tens, and the carry is always 0 or 1.
• What happens if we do not include the fifth step in the algorithm above? Give examples where the algorithm will work correctly and where it will fail to work.Answer: The last carry is lost. It still works when the leftmost column adds up to less than 10 (473 + 325 = 798), but fails when it adds up to more than 10 (473 + 695 would give 168 instead of 1168).
• 1. See if you can complete the argument about grouping by units, tens, hundreds, … to justify why the addition algorithm works.
  2. How would you modify the algorithm to add two decimal fractions?Answer: 1. Each number is a sum of units, tens, hundreds, …; adding group by group gives the same total, and whenever a group reaches ten or more, 10 of that group are exchanged for 1 of the next group (the carry). 2. Align the decimal points, fill in zeros on the right, add from right to left as before, and put the decimal point in the answer under the other points.
• Algorithm to find the divisors of n: 1. Start with an empty list-of-divisors. 2. For each number j in the sequence 1, 2, 3, …, n – if j divides n, add j to the list-of-divisors. Let us execute this algorithm for a small number, say 18.Answer: divisors(18) = [1, 2, 3, 6, 9, 18]. The list comes out in increasing order because the numbers are checked from 1 up to 18.
• Try to execute the algorithm to compute the divisors of 15, 135, and 775. How does the amount of work increase as the numbers grow?Answer: divisors(15) = [1, 3, 5, 15], divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135], divisors(775) = [1, 5, 25, 31, 155, 775]. The algorithm checks every number from 1 to n, so the work grows in step with the number itself: 15, 135 and 775 checks. One more digit means about 10 times as much work.
• If we look through the divisors of 375 and 825 above, we see that the answer is 75. What if the numbers were 54000 and 81000?Answer: gcd(54000, 81000) = 27000. Each number has 80 divisors, too many to compare by eye, so we build the list of common divisors systematically; its rightmost element is 27000.
• Suppose we want to compute gcd(375, 825).Answer: Divisors of 375: [1, 3, 5, 15, 25, 75, 125, 375]; divisors of 825: [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. Common divisors: [1, 3, 5, 15, 25, 75]. So gcd(375, 825) = 75.
• Suppose List 1 and List 2 are two lists of numbers in increasing order.Answer: (i) Start with an empty list; for each x in List 1, if x does not appear in List 2, add x to it; report the list. (ii) The same with the two lists swapped. For List 1 = divisors(375), List 2 = divisors(825): (i) [125, 375], (ii) [11, 33, 55, 165, 275, 825].
• Describe an algorithm to compute the least common multiple (lcm) of two numbers.Answer: Check the multiples of the larger number in order: big, 2 × big, 3 × big, …; the first one that the smaller number divides is the lcm. It is always found by small × big. Example: lcm(12, 18): 18 ✗, 36 ✓, so lcm = 36.
• Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).Answer: (i) Only the numbers j with j × j ≤ n, that is, from 1 up to √n (for 18, only 1, 2, 3, 4). (ii) Not as described: the pair list (1, 18, 2, 9, 3, 6, …) is not in increasing order, so the rightmost common divisor need not be the gcd. Report the largest common divisor instead, or put the list in order first.
• Let us keep track of a quantity called most-recent-common-divisor. We know that 1 is always a common divisor, so we can start with most-recent-common-divisor set to 1. We then scan all numbers from 2 to min(m, n). For each k from 2 to min(m, n), if k divides both m and n, update most-recent-common-divisor to k. Example: Let m = 6, n = 12.Answer: min(6, 12) = 6. most-recent-common-divisor goes 1 → 2 (k = 2) → 3 (k = 3) → stays 3 (k = 4, 5) → 6 (k = 6). Scan complete: gcd(6, 12) = 6.
• How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?Answer: The divisor lists come out in decreasing order, so the list of common divisors is also decreasing. The gcd is then the leftmost (first) element, so Step 5 must say “report the leftmost element”. (We could even stop at the first common divisor found.)
• What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?Answer: The first k that divides both numbers is the gcd, so we can stop there; no list and no most-recent-common-divisor are needed. But the update rule must change: if we kept updating all the way down, the last update would be k = 1 and the answer would wrongly be 1.
• Let us assume that m ≥ n. Then, gcd(m, n) is the same as gcd(n, m − n). Why is this the case?Answer: Every common divisor of m and n also divides m − n, and every common divisor of n and m − n also divides m. So the two pairs have exactly the same common divisors, and therefore the same greatest one.
• Euclid’s algorithm for gcd(m, n): 1. If m < n, reverse the numbers and compute gcd(n, m) 2. If n = 0, report the answer as m 3. Otherwise, reduce the problem to compute gcd(n, m − n). Let us apply this algorithm to gcd(375, 825), the problem that we saw before.Answer: gcd(375, 825) → gcd(825, 375) → gcd(375, 450) → gcd(450, 375) → gcd(375, 75) → gcd(75, 300) → … → gcd(75, 75) → gcd(75, 0), so gcd(375, 825) = 75, after 7 subtraction steps.
• Are we close to our original goal of finding an algorithm where the effort is proportional to the number of digits?Answer: No. Euclid’s subtraction algorithm can need a number of steps proportional to the value of the numbers: gcd(99, 2) takes about 49 subtractions, and gcd(2k + 1, 2) about k.
• Consider the earlier example gcd(99, 2) that took a long time to converge. Here is what happens when we execute the improved algorithm.Answer: 99 mod 2 = 1, so gcd(99, 2) → gcd(2, 1); 2 mod 1 = 0, so gcd(2, 1) → gcd(1, 0). Answer 1, in only two reduction steps.
• In other words, we needed only two reduction steps to get to the final answer. Check that this would happen for any similar problem of the form gcd(2k + 1, 2).Answer: (2k + 1) mod 2 = 1, so gcd(2k + 1, 2) → gcd(2, 1); then 2 mod 1 = 0, so → gcd(1, 0) = 1. Always two reductions, whatever the value of k.
• The above modified algorithm can be carried out concisely using the “long division” method given by Indians at least from the time of Āryabhaṭa. We illustrate the method through the following examples—Answer: 1. gcd(99, 2) = 1 2. gcd(825, 375) = 75 3. gcd(60, 16) = 4
• Compute the following using the improved version of Euclid’s algorithm.Answer: (i) 75 (ii) 3000 (iii) 1 (iv) 24
• Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.Answer: Write m = qn + r, where r = m mod n. If d divides m and n, then d divides r = m − qn. If d divides n and r, then d divides m = qn + r. So the two conditions are equivalent.
• Write an algorithm prime(n) to check if n is prime.
  (Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)Answer: prime(n): compute divisors(n); if the list has exactly two numbers, report “n is prime”, otherwise report “n is not prime”. E.g. divisors(13) = [1, 13] → prime; divisors(15) = [1, 3, 5, 15] → not prime.
• Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
  (Hint: Compute divisors(n) and then filter out the primes in this list.)Answer: Start with an empty list prime-divisors; for each x in divisors(n), if prime(x) says x is prime, add x; report prime-divisors. E.g. primedivisors(60) = [2, 3, 5].
• We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.Answer: Represent a factorisation as a list of (prime, power) pairs in increasing order of the prime: 180 → [(2, 2), (3, 2), (5, 1)]. Build it by taking each prime p in primedivisors(n) and counting how many times p divides n. To compare two factorisations for the gcd, take each prime that appears in both lists with the smaller of its two powers; e.g. gcd(180, 750) = 2 × 3 × 5 = 30.

All maths questions