CBSE Class 9 Maths Ganita Manjari Part 2 Ch 11 The World of Algorithms Long Answer and Case Study Questions with Answers

Long Answer Questions

Question 1. (i) Write out the column-addition algorithm as a numbered list of steps.
(ii) Execute it on 4876 + 5298, stating the value of the carry after each column.
(iii) State the sum.
(iv) State whether the final step of the algorithm was needed here, and why.
Answer:
(i) 1. Write the numbers one below the other, digits aligned from the right.
2. Add the rightmost digits. If the sum is less than 10, write it and set carry to 0; otherwise write its units digit and set carry to 1.
3. Move one column left; add the two digits and the carry, using the same two cases.
4. Repeat Step 3 until no digits are left.
5. If the carry is 1, write 1 to the left of the bottom row.
(ii) Units 6 + 8 = 14 (write 4, carry 1); tens 7 + 9 + 1 = 17 (7, carry 1); hundreds 8 + 2 + 1 = 11 (1, carry 1); thousands 4 + 5 + 1 = 10 (0, carry 1).
(iii) 10 174.
(iv) Yes: a carry of 1 remained after the thousands column; without Step 5 the answer would be 174 (wrong by 10 000).
In simple words: Every column carried here, so the final step had to add the leading 1.

Teacher's Note:
1. Write the steps exactly; wording matters.
2. A table of column, total, digit, carry is clearest.

Question 2. (i) Write out the algorithm that produces the list of divisors of a number n.
(ii) Execute it for n = 45, showing the list after each candidate that changes it.
(iii) Identify the step that is repeated and the step that is conditional.
(iv) State the basic step that the algorithm assumes can already be carried out.
Answer:
(i) 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.
(ii) [ ] → j = 1: [1] → j = 3: [1, 3] → j = 5: [1, 3, 5] → j = 9: [1, 3, 5, 9] → j = 15: [1, 3, 5, 9, 15] → j = 45: [1, 3, 5, 9, 15, 45].
(iii) Repeated: 'for each number j in 1, 2, …, n'. Conditional: 'if j divides n, add j'.
(iv) Deciding directly whether j divides n.
In simple words: Test every number from 1 to 45 and keep those that divide 45.

Teacher's Note:
1. Name the repeated and conditional steps precisely.
2. Basic steps are assumed, not explained.

Question 3. (i) Write out the chapter's first algorithm for gcd(m, n) as a numbered list of steps.
(ii) Execute it for gcd(60, 96), giving both lists of divisors and the list of common divisors.
(iii) State how many candidate numbers were tested altogether in building the two lists.
(iv) Explain why the rightmost element of the list of common divisors is the answer.
Answer:
(i) 1. Let divisors-of-m be divisors(m).
2. Let divisors-of-n be divisors(n).
3. Start with an empty list common-divisors.
4. For each number x in divisors-of-m
    — if x also appears in divisors-of-n, add x to common-divisors.
5. Report the rightmost element of common-divisors as gcd(m, n).
(ii) divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]; divisors(96) = [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96]; common = [1, 2, 3, 4, 6, 12]; gcd = 12.
(iii) 60 + 96 = 156 candidates.
(iv) The lists are built in increasing order, so the rightmost common divisor is the largest, which is the gcd.
In simple words: List all divisors of both, keep the shared ones, and report the biggest.

Teacher's Note:
1. The algorithm calls divisors() twice: building from smaller pieces.
2. 156 tests: very wasteful.

Question 4. The chapter improves the first gcd algorithm in stages. Taking m = 60 and n = 96 throughout:
(i) State how many candidates are tested when the two lists of divisors are built in two separate scans.
(ii) The two scans are then combined into one. State how many candidates are tested now, and why.
(iii) The algorithm is then changed to test only up to min(m, n). State how many candidates are tested now, and why this is safe.
(iv) Finally the lists are abandoned in favour of a single quantity most-recent-common-divisor. Explain what is gained, and state how many candidates are tested by this last version.
Answer:
(i) 60 + 96 = 156.
(ii) One scan from 1 to max(60, 96): 96. Each j is checked against both numbers once.
(iii) Up to min = 60. Safe because no common divisor can exceed 60.
(iv) k = 2 to 60: 59 candidates. Gain is in storage: one number instead of three lists. Safe because discarded divisors are smaller than one already found.
All four versions report 12.
In simple words: Each stage tests fewer candidates or stores less, but always finds 12.

Teacher's Note:
1. Make a table of the four stages.
2. Distinguish speed gains from storage gains.

Question 5. The figure shows a length m and a length n, each tiled exactly by blocks of size d, with the difference m − n marked.
(i) Use the figure to explain why a block size d that tiles both m and n must also tile m − n.
(ii) Prove the same statement in algebra, by writing m = ad and n = bd.
(iii) Prove the converse: if d divides both n and m − n, then d divides m.
(iv) Explain why (ii) and (iii) together establish that gcd(m, n) = gcd(n, m − n).
Answer:
(i) m is 8 blocks and n is 5 blocks. The part of m beyond n is made of the 3 leftover whole blocks, so m − n is tiled exactly by blocks of size d.
(ii) m − n = ad − bd = (a − b)d, and a − b is a whole number (a ≥ b). So d divides m − n. (Here a = 8, b = 5.)
(iii) n = xd, m − n = yd ⇒ m = (x + y)d, so d divides m.
(iv) The two pairs have exactly the same common divisors, so the same greatest one: gcd(m, n) = gcd(n, m − n).
In simple words: Whole blocks minus whole blocks leave whole blocks, so common divisors carry over both ways.

Teacher's Note:
1. Picture and algebra tell the same story.
2. Both directions are needed for equality of gcds.

Question 6. (i) Write out Euclid's subtraction algorithm for gcd(m, n) as three numbered steps.
(ii) Execute it for gcd(48, 18), listing every successive problem including those produced by the reversing step.
(iii) State the number of reduction steps used.
(iv) Explain the purpose of the first step, and what would go wrong without it.
Answer:
(i) 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 computing gcd(n, m − n).
(ii) gcd(48, 18) → gcd(18, 30) → gcd(30, 18) [reversal] → gcd(18, 12) → gcd(12, 6) → gcd(6, 6) → gcd(6, 0).
(iii) 5 reductions; answer 6.
(iv) Step 1 ensures m ≥ n so that m − n is never negative. Without it, gcd(18, 48) would ask for 18 − 48 = −30 and the justification (which assumes m ≥ n) would fail.
In simple words: The swap step keeps the subtraction from going negative.

Teacher's Note:
1. Reversals are not reductions.
2. Every step of an algorithm has a purpose.

Question 7. (i) Write out Āryabhaṭa's division algorithm for gcd(m, n) as three numbered steps.
(ii) Execute it for gcd(1071, 462), listing every successive problem.
(iii) State the number of reduction steps used.
(iv) Euclid's subtraction algorithm needs 12 reductions for the same pair. Explain why the division algorithm needs so many fewer.
Answer:
(i) 1. If m < n, reverse the numbers. 2. If n = 0, report m. 3. Otherwise, reduce to gcd(n, m mod n).
(ii) 1071 = 462 × 2 + 147; 462 = 147 × 3 + 21; 147 = 21 × 7 + 0. gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0). Answer 21.
(iii) 3 reductions.
(iv) Each division replaces a run of subtractions equal to the quotient: 2 + 3 + 7 = 12, which is exactly Euclid's count. Subtraction removes a fixed amount; division cuts the numbers sharply, so its steps grow with the number of digits.
In simple words: The quotients show how many subtractions each division saves.

Teacher's Note:
1. Quotients add up to Euclid's step count.
2. Great check on understanding.

Question 8. Euclid's subtraction algorithm behaves badly on a pair in which one number is very small.
(i) Explain why gcd(2k + 1, 2) needs roughly k reduction steps.
(ii) Take k = 10, so that the problem is gcd(21, 2). List the first four successive problems and state how many reductions are needed in all.
(iii) State the number of reductions Āryabhaṭa's algorithm needs for gcd(21, 2).
(iv) Explain what this example shows about measuring the work of an algorithm against the value of its input rather than against the number of digits of its input.
Answer:
(i) Each reduction removes only 2 from the large odd number (with a reversal between). To bring 2k + 1 down near 1 takes about k reductions.
(ii) gcd(2, 19), gcd(19, 2), gcd(2, 17), gcd(17, 2), …; 12 reductions in all.
(iii) 2: gcd(21, 2) → gcd(2, 1) → gcd(1, 0).
(iv) Euclid's work follows the value (about 500 steps for gcd(1001, 2)), growing tenfold per extra digit. Āryabhaṭa's follows the number of digits, so it stays usable for large numbers.
In simple words: Subtracting 2 at a time is slow for big numbers; dividing is fast whatever the size.

Teacher's Note:
1. Value-based cost explodes with more digits.
2. Digit-based cost grows gently.

Question 9. Compare the two ways of adding two numbers.
(i) Explain how the dot-counting method works and how much work it requires.
(ii) Explain how the digit-by-digit algorithm works and how much work it requires.
(iii) State what happens to the work done by each method when the numbers grow from 3 digits to 5 digits.
(iv) Explain why 'work proportional to the number of digits' is the goal, and name the gcd algorithm in this chapter that achieves it.
Answer:
(i) Draw one dot per unit for each number and count them all; work ∝ value (473 + 695 needs 1168 dots).
(ii) Add one column at a time (two digits and a carry); work ∝ number of digits.
(iii) Dot-counting: about 100 times more work. Column method: just 2 more columns.
(iv) Digits grow very slowly (ten times the value for one more digit), so such algorithms cope with big inputs. Āryabhaṭa's division algorithm achieves this for the gcd.
In simple words: Counting dots grows with size; column addition grows only with length.

Teacher's Note:
1. Use the chapter's timing example for impact.
2. Links efficiency to real usability.

Question 10. (i) Write an algorithm that produces the prime factorisation of a number n.
(ii) Execute it for n = 180 and write the factorisation in index form.
(iii) Explain how the result could be represented as a list so that a computer could store it.
(iv) Explain how the prime factorisations of two numbers could be compared in order to read off their gcd.
Answer:
(i) 1. Start with an empty list factorisation; set remaining to n.
2. For each number p in 2, 3, 4, …, n
    — set count to 0;
    — while p divides remaining, replace remaining by remaining ÷ p and add 1 to count;
    — if count > 0, add the pair (p, count) to factorisation.
3. Report factorisation. (Each p that divides is automatically prime, since smaller factors are already removed.)
(ii) 180 → ÷2 → 90 → ÷2 → 45 → ÷3 → 15 → ÷3 → 5 → ÷5 → 1. 180 = \( 2^2 \times 3^2 \times 5 \).
(iii) As a list of (prime, exponent) pairs: [(2, 2), (3, 2), (5, 1)].
(iv) For each prime in both lists, keep the smaller exponent; multiply. E.g. 180 and 84 = \( 2^2 \times 3 \times 7 \) give \( 2^2 \times 3 = 12 \).
In simple words: Divide out each prime as often as possible, record the counts, and compare exponents for the gcd.

Teacher's Note:
1. No separate primality test needed.
2. Min of exponents gives the gcd.

Question 11. (i) Write an algorithm primedivisors(n) that produces the list of prime divisors of n.
(ii) Execute it for n = 84, showing the full list of divisors first.
(iii) State the list of prime divisors of 84.
(iv) Explain why this algorithm needs prime(n) as a sub-step, and what that illustrates about building algorithms out of smaller ones.
Answer:
(i) 1. Let D = divisors(n). 2. Start with an empty list prime-divisors. 3. For each x in D
    — if prime(x) reports that x is prime, add x to prime-divisors.
4. Report prime-divisors.
(ii) divisors(84) = [1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84].
(iii) [2, 3, 7].
(iv) 'Is x prime?' is not a basic step, so the algorithm calls prime(x), which itself uses divisors(). Each algorithm treats smaller ones as basic steps, so big problems are built from small solved pieces.
In simple words: Find divisors, test each for primality, and keep the primes.

Teacher's Note:
1. Layering: divisors → prime → primedivisors.
2. Decomposition is the chapter's key idea.

Question 12. (i) Explain what a list is and how the divisors algorithm builds one up.
(ii) Explain why the algorithm gives names such as list-of-divisors and j to the values it keeps track of.
(iii) State the single operation on a list that the divisors algorithm needs.
(iv) Explain how the final version of the gcd algorithm manages to do away with lists altogether, and why that is an improvement.
Answer:
(i) A list is an ordered sequence in square brackets that can grow. The algorithm starts with [ ] and appends each divisor found: for 18, [ ] → [1] → [1, 2] → [1, 2, 3] → [1, 2, 3, 6] → [1, 2, 3, 6, 9] → [1, 2, 3, 6, 9, 18].
(ii) Names let steps refer to changing values: 'add j to list-of-divisors' is impossible without names. They keep the algorithm short.
(iii) Append a value at the end.
(iv) Only the largest common divisor was ever needed, so it keeps one number, most-recent-common-divisor, replacing it when a larger one appears. This saves storage and simplifies the algorithm.
In simple words: Lists store values in order; if only the biggest matters, one number is enough.

Teacher's Note:
1. Naming is part of good algorithm writing.
2. Storage efficiency is a real gain.

Question 13. Let List 1 be the list of divisors of 24 and List 2 the list of divisors of 36.
(i) Write out both lists.
(ii) Write an algorithm that produces the list of elements common to two increasing lists, and execute it on these two lists.
(iii) Write out the elements of List 1 that are not in List 2, and the elements of List 2 that are not in List 1.
(iv) State gcd(24, 36) and say which part of your work gives it.
Answer:
(i) List 1 = [1, 2, 3, 4, 6, 8, 12, 24]; List 2 = [1, 2, 3, 4, 6, 9, 12, 18, 36].
(ii) 1. Start with an empty list common. 2. For each x in List 1
    — if x also appears in List 2, add x to common.
3. Report common. Result: [1, 2, 3, 4, 6, 12].
(iii) In List 1 only: [8, 24]. In List 2 only: [9, 18, 36].
(iv) gcd(24, 36) = 12, the rightmost entry of the common list from (ii).
In simple words: Common elements give the gcd; the differences are just extra information.

Teacher's Note:
1. Set operations on lists.
2. Only (ii) is needed for the gcd.

Question 14. An algorithm is not complete until it has been justified.
(i) Explain why a justification is needed as well as the steps.
(ii) Justify the divisors algorithm: explain why the list it produces contains every divisor of n and nothing else.
(iii) Justify the first gcd algorithm: explain why the number it reports really is the greatest common divisor.
(iv) State what the tiling picture in this chapter is used to justify.
Answer:
(i) Steps say what to do, not why it works. A precise procedure can still compute the wrong thing; only an argument covering all inputs settles correctness.
(ii) Every number from 1 to n is tested, so no divisor is missed; only numbers passing 'j divides n' are kept, so nothing else enters. Order is increasing automatically.
(iii) Both lists are complete and correct, so the common list holds exactly the common divisors, in increasing order. Its rightmost entry is the largest, which is the gcd. It is never empty since 1 always qualifies.
(iv) The reduction gcd(m, n) = gcd(n, m − n) in Euclid's algorithm.
In simple words: A justification shows the algorithm is right for every possible input.

Teacher's Note:
1. 'Nothing missed, nothing extra' is the standard shape.
2. Examples alone are never proof.

Question 15. Write an account of the history behind the word 'algorithm'. Your account must include
(i) who Al-Khwārizmī was, when he lived and where he worked;
(ii) what his treatise set out, and what happened to the original;
(iii) the chain of forms by which his name became the word 'algorithm';
(iv) what the word originally denoted and what it has come to mean;
(v) the names and dates of the works in which Āryabhaṭa's and Euclid's methods were written down.
Answer:
(i) A Persian mathematician (c. 780–850 CE) at the House of Wisdom in Baghdad, who learnt Sanskrit to study Indian mathematics.
(ii) Around 820 CE he explained the Indian place-value system and methods for +, −, ×, ÷. The Arabic original is lost; a 12th-century Latin translation, Liber Algorismi de numero Indorum, survives.
(iii) Algoritmi → algorismus → algorism → algorithm.
(iv) Originally an Indian method of arithmetic with place-value numerals; now any well-defined step-by-step procedure.
(v) Āryabhaṭa: Āryabhaṭīya (499 CE). Euclid: Elements.
In simple words: An Indian way of calculating, explained by a Baghdad scholar, gave the world the word 'algorithm'.

Teacher's Note:
1. Organise under the five headings.
2. Highlights India's role in world mathematics.

Question 16. Compare all three methods of this chapter on the single problem gcd(252, 105).
(i) Use the divisor-list method: give the list of common divisors and the number of candidates tested in building the two lists of divisors.
(ii) Use Euclid's subtraction algorithm and state the number of reductions it needs.
(iii) Use Āryabhaṭa's division algorithm, listing the successive problems, and state the number of reductions.
(iv) Rank the three methods by the amount of work required and justify the ranking.
Answer:
(i) Common divisors [1, 3, 7, 21]; answer 21; 252 + 105 = 357 tests.
(ii) gcd(252, 105) → (105, 147) → [rev] (147, 105) → (105, 42) → (42, 63) → [rev] (63, 42) → (42, 21) → (21, 21) → (21, 0): 6 reductions.
(iii) gcd(252, 105) → gcd(105, 42) → gcd(42, 21) → gcd(21, 0): 3 reductions.
(iv) Divisor lists (357) > Euclid (6) > Āryabhaṭa (3). Divisor lists depend on the values; Euclid removes one copy per step; Āryabhaṭa does all copies at once. Quotients 2 + 2 + 2 = 6 match Euclid's count.
In simple words: All three give 21, but with 357, 6 and 3 units of work.

Teacher's Note:
1. Same answer, very different effort.
2. Quotient sum = Euclid's steps again.

Question 17. The chapter asks what happens if the candidates are scanned in reverse order.
(i) Explain what changes in the divisors algorithm if the candidates are tested from n down to 1.
(ii) Explain what changes in the most-recent-common-divisor version of the gcd algorithm if the candidates are tested from min(m, n) down to 1.
(iii) State which of the two scanning directions is better for the gcd, and why.
(iv) Write out the improved gcd algorithm that results, as a numbered list of steps.
Answer:
(i) Same divisors, same work, but the list is in decreasing order (18: [18, 9, 6, 3, 2, 1]). The first gcd algorithm would then need to report the leftmost entry.
(ii) The first common divisor met is the largest, so the algorithm can stop immediately.
(iii) Downwards is better: it can stop early (60 and 96: 49 tests vs 59; gcd(60, 120): 1 test). Worst case (coprime) it equals the upward scan.
(iv) 1. If m < n, reverse the numbers.
2. For each k in n, n − 1, …, 1
    — if k divides both m and n, report k as gcd(m, n) and stop.
In simple words: Scanning down lets the algorithm stop at the first common divisor it finds.

Teacher's Note:
1. Early stopping is a key efficiency trick.
2. Never worse, often better.

Question 18. A student writes the following algorithm for the divisors of a number.
1. Start with an empty list-of-divisors.
2. For each number j in the sequence 1, 2, 3, …, n − 1
    — if j divides n, add j to the list-of-divisors.
(i) Execute the student's algorithm for n = 12 and write down the list it produces.
(ii) State the list that the correct algorithm produces for n = 12.
(iii) Identify precisely what is wrong with the student's algorithm.
(iv) Explain what would go wrong if this faulty algorithm were used inside the first gcd algorithm, giving an example of a pair of numbers for which the reported gcd would be wrong.
Answer:
(i) [1, 2, 3, 4, 6].
(ii) [1, 2, 3, 4, 6, 12].
(iii) The range stops at n − 1 instead of n, so n itself is never tested, and the largest divisor is always missing.
(iv) When one number divides the other, the gcd is the smaller number, and that is exactly what gets lost. m = 12, n = 24: faulty lists [1, 2, 3, 4, 6] and [1, 2, 3, 4, 6, 8, 12]; reported gcd 6, but the true gcd is 12.
In simple words: Stopping one short drops n itself, which can be the gcd.

Teacher's Note:
1. Off-by-one errors are silent and dangerous.
2. Test edge cases where one number divides the other.

Question 19. (i) Write an algorithm that finds the largest number in a list, keeping track of a single quantity called largest-so-far.
(ii) Execute it on the list [7, 3, 11, 5, 11, 2], showing the value of largest-so-far after each element.
(iii) Justify the algorithm: explain why the value it reports really is the largest element.
(iv) Explain how this algorithm is related to the most-recent-common-divisor version of the gcd algorithm.
Answer:
(i) 1. Let largest-so-far be the first element. 2. For each remaining element x, in order
    — if x is greater than largest-so-far, replace largest-so-far by x.
3. Report largest-so-far.
(ii) 7 → 7 → 11 → 11 → 11 (tie, no change) → 11. Reports 11.
(iii) At each stage it holds the largest element seen so far: true at the start, and kept true at each step. Every element is seen once, so at the end it is the overall largest.
(iv) Same pattern: a running best value, started safely (first element / 1) and replaced when something better appears. The gcd version only considers candidates passing the divisibility test.
In simple words: Keep the best so far and update it whenever something bigger appears.

Teacher's Note:
1. 'Running best' is a reusable pattern.
2. Justification by 'always true so far' (an invariant).

Question 20. Write an account of what makes a good algorithm, drawing all your illustrations from this chapter. Your account must cover
(i) the precision with which the steps are written;
(ii) the basic steps an algorithm is allowed to assume;
(iii) repeated steps and conditional steps;
(iv) the justification that the algorithm is correct;
(v) the analysis of how much work the algorithm does.
Answer:
(i) Precision: every step says exactly what to do. Following the addition steps literally reveals a gap: they don't say missing digits count as 0. 'If j divides n, add j' is precise.
(ii) Basic steps: single-digit addition (addition algorithm); divisibility testing (divisors algorithm). Algorithms layer: prime() uses divisors(), primedivisors() uses prime().
(iii) Repeated and conditional steps: 'for each j' lets short text do long work; 'if j divides n' lets the algorithm react. Addition repeats Step 3 and chooses between two cases.
(iv) Justification: place-value grouping (addition); 'nothing missed, nothing extra' (divisors); tiling picture and two-way algebra (Euclid).
(v) Analysis: dot-counting and divisor lists grow with value; column addition and Āryabhaṭa grow with digits (gcd(1001, 2): ~500 steps vs 2).
In simple words: A good algorithm is precise, honest about assumptions, uses repetition and conditions wisely, is proved correct, and is efficient.

Teacher's Note:
1. Five separate qualities; illustrate each.
2. Correct ≠ efficient.

Case Study Based Questions

Question 21. The Carry Column: A clerk adds 8695 and 4738 using the column-addition algorithm, working from the rightmost column towards the left.
(a) Find the sum of the units column and state the value the carry is set to.
(b) State the digit written down in the tens column.
(c) State the value of the carry after the leftmost column of digits has been added.
(d) Write down the sum of the two numbers.
Answer:
(a) 5 + 8 = 13; write 3, carry 1.
(b) 9 + 3 + 1 = 13, so the digit is 3.
(c) Thousands: 8 + 4 + 1 = 13, so the carry is 1.
(d) 13 433 (the final step writes the leading 1).
In simple words: Every column carries, so the final step adds a leading 1.

Teacher's Note:
1. Hundreds: 6 + 7 + 1 = 14.
2. Check with ordinary addition.

Question 22. Divisor Detective: The divisors algorithm is executed for n = 50, testing the candidates j = 1, 2, 3, … in order.
(a) Write down the list-of-divisors immediately after the candidate j = 5 has been dealt with.
(b) Write down the final list-of-divisors.
(c) State how many candidates the algorithm tested altogether.
(d) State how many divisors 50 has.
Answer:
(a) [1, 2, 5].
(b) [1, 2, 5, 10, 25, 50].
(c) 50.
(d) 6 (50 tests to find 6 divisors).
In simple words: Fifty tests find just six divisors, showing how wasteful testing everything is.

Teacher's Note:
1. Motivates the √n shortcut.
2. Track the list mid-way, not just at the end.

Question 23. Two Lists: The first gcd algorithm is run on 40 and 72. It first builds divisors(40) = [1, 2, 4, 5, 8, 10, 20, 40] and divisors(72) = [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72].
(a) Write down the list of common divisors that the algorithm builds next.
(b) State gcd(40, 72).
(c) State which element of the list of common divisors the algorithm reports, and why.
(d) Write down the elements of divisors(40) that do not appear in divisors(72).
Answer:
(a) [1, 2, 4, 8].
(b) 8.
(c) The rightmost (8): the list is increasing, so the rightmost is the largest.
(d) [5, 10, 20, 40].
In simple words: Keep the shared divisors and report the largest, 8.

Teacher's Note:
1. Rightmost = greatest.
2. Difference lists are a bonus skill.

Question 24. Euclid's Reductions: Euclid's subtraction algorithm is applied to gcd(72, 54).
(a) Write down the problem that the first reduction step produces.
(b) Write down all the successive problems until the algorithm stops, including any produced by the reversing step.
(c) State the number of reduction steps used.
(d) State gcd(72, 54).
Answer:
(a) gcd(54, 18).
(b) gcd(72, 54) → gcd(54, 18) → gcd(18, 36) → gcd(36, 18) [reversal] → gcd(18, 18) → gcd(18, 0).
(c) 4 reductions.
(d) 18.
In simple words: Subtract, swap when needed, and stop at a zero.

Teacher's Note:
1. Mark the reversal clearly.
2. Don't count reversals.

Question 25. Āryabhaṭa's Shortcut: Āryabhaṭa's division algorithm is applied to gcd(210, 45).
(a) Find 210 mod 45.
(b) Write down all the successive problems the algorithm produces.
(c) State the number of reduction steps used.
(d) State gcd(210, 45).
Answer:
(a) 210 = 45 × 4 + 30, so 30.
(b) gcd(210, 45) → gcd(45, 30) → gcd(30, 15) → gcd(15, 0).
(c) 3.
(d) 15.
In simple words: Use remainders to shrink the pair quickly.

Teacher's Note:
1. 45 mod 30 = 15; 30 mod 15 = 0.
2. Few steps even for large numbers.

Question 26. Racing the Algorithms: Two students compute gcd(1001, 2). Ananya uses Euclid's subtraction algorithm and Bhavesh uses Āryabhaṭa's division algorithm.
(a) State roughly how many reduction steps Ananya's method needs.
(b) State exactly how many reduction steps Bhavesh's method needs.
(c) State which student finishes first.
(d) Explain what this pair of answers shows about judging an algorithm by the size of the numbers written down rather than by their value.
Answer:
(a) About 500 (502 when run).
(b) 2: gcd(2, 1) → gcd(1, 0).
(c) Bhavesh, by a huge margin.
(d) The numbers look small (5 digits in all), yet one method takes 500 steps. Euclid's cost follows the value; Āryabhaṭa's follows the number of digits. Methods tied to value become unusable quickly.
In simple words: Same problem, 500 steps versus 2: the method matters more than the numbers.

Teacher's Note:
1. A memorable race to discuss efficiency.
2. One extra digit ≈ ten times the value.

Question 27. The Word 'Algorithm': A student reads that the word 'algorithm' has a history reaching back to ninth-century Baghdad.
(a) Name the scholar from whose name the word comes, and the institution at which he worked.
(b) Name the surviving Latin translation of his treatise.
(c) Write down, in order, the three forms through which his name passed on its way to the modern word.
(d) State what the word originally denoted, before it broadened to its present meaning.
Answer:
(a) Al-Khwārizmī, the House of Wisdom, Baghdad.
(b) Liber Algorismi de numero Indorum.
(c) algorismus → algorism → algorithm.
(d) An Indian method of arithmetic using place-value numerals.
In simple words: The word began as the name of a scholar who explained Indian arithmetic.

Teacher's Note:
1. Title means 'Book of Al-Khwārizmī on Indian Numerals'.
2. Arabic original lost.

Question 28. Naming Things: Here is the chapter's divisors algorithm.
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.
(a) Name the data structure used by this algorithm.
(b) State what the name j stands for.
(c) Give one reason why giving names to the values kept track of makes the algorithm easier to write down.
(d) Write down the conditional step of the algorithm.
Answer:
(a) A list.
(b) The number currently being tested as a possible divisor (1, 2, …, n in turn).
(c) Without names the step could not say 'add j to it'; one short line stands for n separate actions.
(d) If j divides n, add j to the list-of-divisors.
In simple words: Names let one short instruction describe many repeated actions.

Teacher's Note:
1. Link to variables in programming.
2. Conditional = 'if'.

Question 29. Mind the Bug: A student leaves out the instruction that sets the carry back to 0 when a column total is less than 10. The carry, once set to 1, therefore stays at 1. The student uses this faulty version to add 348 and 427.
(a) State the digit written in the units column and the value the carry takes there.
(b) State the digit the faulty algorithm writes in the hundreds column, and the digit the correct algorithm writes there.
(c) Write down the answer the faulty algorithm produces, remembering that its final step is still carried out.
(d) Write down the correct answer, and state which instruction had to be restored to obtain it.
Answer:
(a) 8 + 7 = 15: digit 5, carry 1.
(b) Tens 4 + 2 + 1 = 7 (both agree). Hundreds: faulty 3 + 4 + 1 = 8; correct 3 + 4 + 0 = 7.
(c) Carry still 1 at the end, so 1875.
(d) 775. Restore: 'set the carry to 0 when a column total is less than 10'.
In simple words: Forgetting to reset the carry creates two errors: a wrong digit and an extra leading 1.

Teacher's Note:
1. The bug was invisible until the hundreds column.
2. Early correct steps don't prove an algorithm right.

Question 30. Divisors in Pairs: A student pairs up the divisors of 100, writing each divisor beside its partner.
(a) Write down all the divisor pairs of 100.
(b) State the largest number that has to be examined in order to find all the pairs.
(c) State how many divisors 100 has altogether.
(d) Explain why the number of divisors of 100 comes out odd rather than even.
Answer:
(a) (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
(b) 10 (= √100).
(c) 9: [1, 2, 4, 5, 10, 20, 25, 50, 100].
(d) The pair (10, 10) repeats a number, contributing one divisor instead of two, because 100 = 10 × 10 is a perfect square.
In simple words: Perfect squares have one pair with a repeated number, so the count is odd.

Teacher's Note:
1. Links to Chapter 9's result on perfect squares.
2. Only test up to √n.