CBSE Class 9 Maths Ganita Manjari Part 2 Ch 11 The World of Algorithms Short Answer Questions with Answers

Short Answer Questions

Question 1. Execute the divisors algorithm for n = 28. Show the list after each candidate that changes it, and state the final list.
Answer:
Start: [ ]
j = 1: [1]; j = 2: [1, 2]; j = 4: [1, 2, 4]; j = 7: [1, 2, 4, 7]; j = 14: [1, 2, 4, 7, 14]; j = 28: [1, 2, 4, 7, 14, 28].
All other candidates leave the list unchanged. divisors(28) = [1, 2, 4, 7, 14, 28].
In simple words: Only the numbers that divide 28 are added, in increasing order.

Teacher's Note:
1. Show only candidates that change the list.
2. 28 is a perfect number: 1 + 2 + 4 + 7 + 14 = 28.

Question 2. Use the chapter's first gcd algorithm to find gcd(36, 90). Write down the two lists of divisors, the list of common divisors, and the answer the algorithm reports.
Answer:
divisors(36) = [1, 2, 3, 4, 6, 9, 12, 18, 36]
divisors(90) = [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]
Common divisors = [1, 2, 3, 6, 9, 18]
Reported answer (rightmost): gcd(36, 90) = 18.
In simple words: List both sets of divisors, keep the shared ones, and take the largest.

Teacher's Note:
1. Check absent entries: 4, 12, 36 are not divisors of 90.
2. Rightmost = answer.

Question 3. Let d be a common divisor of m and n, where m ≥ n. Prove that d is also a divisor of m − n.
Answer:
Since d divides m and n: m = ad and n = bd for natural numbers a, b.
m − n = ad − bd = (a − b)d.
Since m ≥ n, a ≥ b, so a − b is a whole number. Hence d divides m − n.
In simple words: Take d out as a common factor of m − n.

Teacher's Note:
1. Algebra version of the tiling picture.
2. State why a − b is a whole number.

Question 4. Let d be a common divisor of n and m − n, where m ≥ n. Prove that d is also a divisor of m, and state what this result and the previous one together establish.
Answer:
n = xd and m − n = yd for natural numbers x, y.
m = n + (m − n) = xd + yd = (x + y)d, so d divides m.
Together with the previous result: the pairs (m, n) and (n, m − n) have exactly the same common divisors, so gcd(m, n) = gcd(n, m − n).
In simple words: Adding the two multiples of d gives m as a multiple of d.

Teacher's Note:
1. The two directions together justify Euclid's step.
2. Same sets ⇒ same greatest element.

Question 5. Execute Euclid's subtraction algorithm on gcd(45, 18), listing every successive problem including any produced by the reversing step, and state the number of reductions used.
Answer:
gcd(45, 18) → gcd(18, 27) → gcd(27, 18) [reversal] → gcd(18, 9) → gcd(9, 9) → gcd(9, 0).
Answer 9; 4 reductions (the reversal is not counted).
In simple words: Subtract repeatedly, swapping when needed, until the second number is 0.

Teacher's Note:
1. Count reductions and reversals separately.
2. Reversals make no progress.

Question 6. Execute Āryabhaṭa's division algorithm on gcd(315, 91), listing every successive problem, and state the number of reductions used.
Answer:
315 = 91 × 3 + 42; 91 = 42 × 2 + 7; 42 = 7 × 6 + 0.
gcd(315, 91) → gcd(91, 42) → gcd(42, 7) → gcd(7, 0).
Answer 7; 3 reductions.
In simple words: Replace the pair by (divisor, remainder) until the remainder is 0.

Teacher's Note:
1. No reversal is ever needed in Āryabhaṭa's method after the first step.
2. Show each division equation.

Question 7. Compare the two gcd algorithms on gcd(101, 2). State roughly how many reductions each one needs, and explain what causes the difference.
Answer:
Euclid: about 50 reductions (52 when run), removing 2 each time.
Āryabhaṭa: 2 reductions: gcd(2, 1) → gcd(1, 0).
The cause: 2 is tiny compared with 101, so each subtraction removes very little; one division does all ~50 subtractions at once.
In simple words: Division does in one step what subtraction needs fifty steps to do.

Teacher's Note:
1. The quotient = number of subtractions saved.
2. Both give the answer 1.

Question 8. Write an algorithm primedivisors(n) that produces the list of those divisors of n which are prime numbers, and execute it for n = 60.
Answer:
1. Let D be the list obtained by computing divisors(n).
2. Start with an empty list prime-divisors.
3. For each number x in the list D
    — if prime(x) reports that x is prime, add x to prime-divisors.
4. Report prime-divisors.
For 60: D = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]; primes among them: [2, 3, 5].
In simple words: Find all divisors, then keep only the prime ones.

Teacher's Note:
1. Builds on prime(n), which builds on divisors(n).
2. 1 is not prime.

Question 9. Write an algorithm that produces the list of elements of List 1 that do not appear in List 2, where both lists are in increasing order. Execute it for List 1 = [1, 2, 3, 6, 9, 18] and List 2 = [1, 2, 3, 6, 12].
Answer:
1. Start with an empty list only-in-first.
2. For each number x in List 1
    — if x does not appear anywhere in List 2, add x to only-in-first.
3. Report only-in-first.
Execution: 1, 2, 3, 6 are found in List 2 and skipped; 9 and 18 are not. Result: [9, 18].
In simple words: Go through List 1 and keep what is missing from List 2.

Teacher's Note:
1. The output is still in increasing order.
2. Compare with the 'common elements' algorithm.

Question 10. The figure shows gcd(408, 170) worked out in the Indian long-division layout used by Āryabhaṭa's method.
(i) Write down the three successive problems the layout records.
(ii) State the number of reduction steps used.
(iii) State gcd(408, 170) and say which feature of the layout tells you that the computation has finished.
Answer:
(i) gcd(408, 170), gcd(170, 68), gcd(68, 34).
(ii) Three divisions, so 3 reduction steps.
(iii) gcd = 34. The remainder 0 at the foot of the last division shows it has finished (the problem has become gcd(34, 0)).
In simple words: Each remainder becomes the next divisor until the remainder is 0; the last divisor is the gcd.

Teacher's Note:
1. The layout is from the Āryabhaṭīya (499 CE).
2. Remainder 0 = stop.

Question 11. The column-addition algorithm is used to add a 5-digit number to a 3-digit number. Explain what has to be done about the two empty columns on the left, and state whether the steps as written in the chapter handle the situation correctly.
Answer:
Treat the two empty places of the 3-digit number as 0, so every column has two digits (in practice, bring down the longer number's digits plus any carry).
The steps work if Step 1 aligns from the right, but they do not say that missing digits count as 0; the reader must supply this. Writing the zeros removes the ambiguity.
In simple words: Fill the empty places with zeros and the algorithm works unchanged.

Teacher's Note:
1. Shows why precise steps matter.
2. Hidden assumptions are gaps in an algorithm.

Question 12. Justify the column-addition algorithm by means of the place-value grouping argument: explain why adding the digits column by column from the right produces the sum of the two numbers.
Answer:
586 = 5 × 100 + 8 × 10 + 6 and 748 = 7 × 100 + 4 × 10 + 8.
Sum = (5 + 7) × 100 + (8 + 4) × 10 + (6 + 8): units with units, tens with tens, hundreds with hundreds, which is column addition.
If a group overflows (6 + 8 = 14), the extra ten is one unit of the next group, so it is carried left.
Working from the right ensures each carry is ready before its column is added.
In simple words: Column addition just adds like place values, carrying each extra ten to the next place.

Teacher's Note:
1. Grouping explains both the columns and the carry.
2. Each place is worth ten of the one to its right.

Question 13. Show what goes wrong if the final step of the column-addition algorithm is left out. Give one addition for which the shortened algorithm still gives the right answer and one for which it does not, showing the answer it produces in each case.
Answer:
The final step writes the leftover carry at the left.
Still works: 341 + 256: no carries, answer 597 (correct).
Fails: 586 + 748: columns give 4, 3, 3 with a final carry 1; the shortened algorithm gives 334 instead of 1334, which is 1000 short.
In simple words: Without the last step, any final carry is lost.

Teacher's Note:
1. The error equals the value of the dropped carry.
2. Test algorithms on edge cases.

Question 14. Divisors occur in pairs. Explain how this fact reduces the number of candidates that must be examined to find all the divisors of n, and illustrate your explanation by listing the divisor pairs of 36.
Answer:
Each divisor d pairs with n ÷ d; in each pair the smaller member is at most √n (else the product would exceed n).
So testing only up to √n finds every pair; the partner is written down directly. Work falls from about n tests to about √n.
For 36 (√36 = 6): (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), which gives all nine divisors from testing 1 to 6.
In simple words: Find the small half of each pair; the big half comes free.

Teacher's Note:
1. The repeated pair (6, 6) explains why squares have an odd number of divisors.
2. Links to Chapter 9.

Question 15. Trace the most-recent-common-divisor version of the gcd algorithm for m = 18 and n = 24. State the range of candidates scanned, show every update of most-recent-common-divisor, and state the answer.
Answer:
Range: k = 2 to min(18, 24) = 18.
Start: 1. k = 2 divides both → 2. k = 3 → 3. k = 6 → 6.
No later update (9 fails 24; 12 fails 18). Answer: gcd(18, 24) = 6.
In simple words: Keep the latest common divisor found; the last one is the gcd.

Teacher's Note:
1. Show only the updates.
2. The final value held is the answer.

Question 16. The chapter makes four successive improvements to the first gcd algorithm. Explain why each improvement leaves the answer unchanged, and state what is gained by making them.
Answer:
1. Combining the two scans tests the same candidates in one pass.
2. Computing common divisors directly just skips recording divisors that would be discarded.
3. Stopping at min(m, n) skips only candidates that cannot be common divisors.
4. Keeping only the most-recent common divisor drops only smaller ones, which can never be greatest.
Gain: tests fall from m + n to max(m, n) to min(m, n), and storage falls from two lists to one number.
In simple words: Each change organises the search better without changing what is searched for.

Teacher's Note:
1. Correctness must be preserved at every refinement.
2. Efficiency and storage both improve.

Question 17. Explain the etymology of the word 'algorithm', naming the scholar involved and the intermediate forms of the word, and state what the word originally denoted.
Answer:
From Al-Khwārizmī (c. 780–850 CE), House of Wisdom, Baghdad, who wrote on Indian arithmetic around 820 CE.
The Latin translation Liber Algorismi de numero Indorum used 'Algoritmi' for his name.
Forms: algorismus → algorism → algorithm.
Originally it meant an Indian method of arithmetic; later, any well-defined step-by-step procedure.
In simple words: The word traces back to a scholar's name and first meant Indian-style calculation.

Teacher's Note:
1. The Arabic original is lost.
2. Good link to history of mathematics.

Question 18. Use Āryabhaṭa's division algorithm to compute gcd(825, 375). Set your working out in the long-division layout, and state the number of reduction steps used.
Answer:
375 ) 825 ( 2 → 750, remainder 75
75 ) 375 ( 5 → 375, remainder 0
gcd(825, 375) → gcd(375, 75) → gcd(75, 0). gcd = 75, in 2 reductions.
In simple words: Divide, then divide the divisor by the remainder, until the remainder is 0.

Teacher's Note:
1. Each remainder becomes the next divisor.
2. The last divisor is the gcd.

Question 19. Write an algorithm prime(n) that uses divisors(n), and explain why the correct test is that the list has exactly two entries rather than that it has no entries other than 1.
Answer:
1. Let D be the list obtained by computing divisors(n).
2. If D has exactly two entries, report that n is prime; otherwise report that n is not prime.
'No entries other than 1' would fail for every n > 1, because n always divides itself and appears in D.
'Exactly two' also correctly rejects 1, whose list [1] has one entry.
In simple words: A prime has exactly two divisors: 1 and itself.

Teacher's Note:
1. Test the definition on edge cases like 1 and 2.
2. Wording must match the definition exactly.

Question 20. For n = 10 000, compare the number of candidate divisors examined by (i) the chapter's divisors algorithm, which tests every number from 1 to n, and (ii) the pair-based method, which tests only up to √n. State the two counts and the factor by which the work is reduced.
Answer:
(i) 10 000 tests.
(ii) √10 000 = 100 tests.
Reduction factor = 10 000 ÷ 100 = 100. For a million it would be 1000.
In simple words: Testing only up to the square root cuts the work a hundredfold here.

Teacher's Note:
1. The saving grows as n grows.
2. Square root is a powerful shortcut.