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

Very Short Answer Questions

Question 1. Explain in one sentence what an algorithm is, and give one reason why its steps must be written down precisely.
Answer:
An algorithm is a systematic step-by-step procedure that solves every problem of a given kind.
Steps must be precise so that anyone (or any machine) can follow them without guessing; gaps would be filled differently by different readers and give different answers.

Teacher's Note:
1. Precision = no guesswork.
2. Machines follow instructions literally.

Question 2. Write out the list of divisors of 20 exactly as the chapter's divisors algorithm would produce it.
Answer:
divisors(20) = [1, 2, 4, 5, 10, 20].

Teacher's Note:
1. The list is in increasing order.
2. Include 1 and 20.

Question 3. Explain why the column-addition algorithm requires the digits of the two numbers to be aligned from the right rather than from the left.
Answer:
The method adds digits of the same place value: units with units, tens with tens.
Aligning from the right does this; aligning from the left would put, say, hundreds above tens when the numbers have different lengths.

Teacher's Note:
1. Try 586 + 48 aligned from the left to see the error.
2. Place value decides alignment.

Question 4. Explain why the carry in the column-addition algorithm can never take the value 2.
Answer:
The largest column total is 9 + 9 + 1 = 19, which contains only one ten.
So the carry out is at most 1, and a carry of 2 can never arise.

Teacher's Note:
1. Show the worst case clearly.
2. This keeps the algorithm to two cases.

Question 5. Execute Euclid's subtraction algorithm on gcd(20, 12), writing down each successive problem it produces.
Answer:
gcd(20, 12) → gcd(12, 8) → gcd(8, 4) → gcd(4, 4) → gcd(4, 0).
It reports 4, using 4 reductions.

Teacher's Note:
1. Keep the smaller number, replace the larger by the difference.
2. Stop when the second number is 0.

Question 6. Āryabhaṭa's division algorithm reduces gcd(m, n) to gcd(n, m mod n). Apply it to gcd(84, 36) and state how many reduction steps it needs.
Answer:
gcd(84, 36) → gcd(36, 12) → gcd(12, 0), since 84 mod 36 = 12 and 36 mod 12 = 0.
gcd = 12, in 2 reduction steps.

Teacher's Note:
1. Write each remainder calculation.
2. Count arrows for the step count.

Question 7. State the stopping condition of Euclid's algorithm and the value it reports when that condition is reached.
Answer:
It stops when the second number is 0, i.e. at gcd(m, 0).
It reports m, because every number divides 0, so the greatest common divisor of m and 0 is m.

Teacher's Note:
1. Same stopping rule for Āryabhaṭa's method.
2. gcd(m, 0) = m.

Question 8. Name the mathematician whose name gave us the word 'algorithm', and state the century in which he worked.
Answer:
Al-Khwārizmī, in the ninth century (about 780–850 CE), at the House of Wisdom in Baghdad.

Teacher's Note:
1. Link to his book on Indian numerals.
2. A good cross-curricular history point.

Question 9. Explain what is meant by executing an algorithm.
Answer:
Executing an algorithm means carrying out its steps one at a time on a particular input, tracking how the named quantities change, until it reports its answer.

Teacher's Note:
1. Different from justifying or analysing.
2. Always execute on a specific input.

Question 10. State the basic step that the divisors algorithm assumes can already be performed.
Answer:
It assumes we can decide directly whether j divides n.

Teacher's Note:
1. Basic steps are taken as given.
2. The algorithm never explains how to test divisibility.

Question 11. Write the list of common divisors of 30 and 42, and state gcd(30, 42).
Answer:
divisors(30) = [1, 2, 3, 5, 6, 10, 15, 30]; divisors(42) = [1, 2, 3, 6, 7, 14, 21, 42].
Common divisors = [1, 2, 3, 6]; gcd(30, 42) = 6.

Teacher's Note:
1. The rightmost common divisor is the gcd.
2. List both sets fully first.

Question 12. Explain why the list of divisors produced by the chapter's algorithm is automatically in increasing order, without any sorting being done.
Answer:
Candidates are tested in the order 1, 2, 3, …, n, and each divisor found is added at the end.
So every new entry is larger than those already there.

Teacher's Note:
1. Order comes free from the scan.
2. No sorting step is needed.

Question 13. Explain what a data structure is, and name the one used throughout this chapter.
Answer:
A data structure is a way of organising the values an algorithm keeps track of so that its operations are convenient.
This chapter uses the list (in ascending order).

Teacher's Note:
1. Lists are the simplest data structure.
2. More will come in later grades.

Question 14. Find the values of 47 mod 8 and 100 mod 12.
Answer:
47 = 8 × 5 + 7, so 47 mod 8 = 7.
100 = 12 × 8 + 4, so 100 mod 12 = 4.

Teacher's Note:
1. mod gives the remainder.
2. The remainder is always less than the divisor.

Question 15. In the gcd algorithm that does away with lists, state the value given to most-recent-common-divisor before the scan begins, and explain why that value is a safe starting point.
Answer:
It starts at 1.
1 divides every number, so it is certainly a common divisor; the algorithm stays correct even if nothing larger is found (for coprime numbers).

Teacher's Note:
1. A safe start guarantees a correct answer.
2. Coprime pairs give 1.

Question 16. The improved gcd algorithm scans the candidates k = 2, 3, …, min(m, n). State how many candidates it examines for m = 45 and n = 80.
Answer:
min(45, 80) = 45, so it tests k = 2 to 45: 45 − 2 + 1 = 44 candidates.

Teacher's Note:
1. Count inclusive ranges carefully: last − first + 1.
2. It starts at 2 because 1 is pre-set.

Question 17. Explain why the chapter's first gcd algorithm can take the rightmost element of the list of common divisors as the answer.
Answer:
The list of common divisors is built in increasing order, so its rightmost element is its largest.
The greatest common divisor is by definition the largest common divisor.

Teacher's Note:
1. Rightmost = largest.
2. The leftmost would always be 1.

Question 18. Write an algorithm prime(n), in at most three steps, that decides whether n is a prime number by making use of divisors(n).
Answer:
1. Let D be the list obtained by computing divisors(n).
2. Count the entries of D.
3. If the count is exactly 2, report that n is prime; otherwise report that n is not prime.

Teacher's Note:
1. A prime has exactly two divisors: 1 and itself.
2. This test correctly rejects 1.

Question 19. Use Āryabhaṭa's division algorithm to find gcd(1071, 462), and state the number of reduction steps it takes.
Answer:
gcd(1071, 462) → gcd(462, 147) → gcd(147, 21) → gcd(21, 0).
(1071 mod 462 = 147, 462 mod 147 = 21, 147 mod 21 = 0.)
gcd = 21, in 3 reduction steps.

Teacher's Note:
1. Show each division.
2. Large numbers still need few steps.

Question 20. Add 6857 and 2749 by the column-addition algorithm, stating the value of the carry after each column is dealt with.
Answer:
Units: 7 + 9 = 16 → write 6, carry 1.
Tens: 5 + 4 + 1 = 10 → write 0, carry 1.
Hundreds: 8 + 7 + 1 = 16 → write 6, carry 1.
Thousands: 6 + 2 + 1 = 9 → write 9, carry 0.
Sum = 9606.

Teacher's Note:
1. Record the carry after every column.
2. No final carry here, so Step 5 writes nothing.

Question 21. Explain why adding two numbers by drawing dots and counting them becomes impractical as the numbers grow, while adding digit by digit does not.
Answer:
Dot-counting needs one dot per unit, so work grows with the value: each extra digit multiplies it by about 10.
Column addition needs one column per digit, so work grows with the number of digits: each extra digit adds just one column.

Teacher's Note:
1. Value-based vs digit-based work.
2. This is the chapter's central efficiency idea.

Question 22. State what changes and what stays the same when Euclid's subtraction algorithm is upgraded to Āryabhaṭa's division algorithm.
Answer:
Same: the reversing step (if m < n) and the stopping step (if n = 0, report m).
Changes: only the reduction: gcd(n, m − n) becomes gcd(n, m mod n).

Teacher's Note:
1. One line changes; the gain is huge.
2. Division bundles many subtractions.

Question 23. Explain in one sentence what m mod n means, and show that 17 mod 5 = 2.
Answer:
m mod n is the remainder when m is divided by n.
17 = 5 × 3 + 2, so 17 mod 5 = 2.

Teacher's Note:
1. Always write the division equation.
2. Remainder < divisor.

Question 24. Give a pair of numbers for which Euclid's subtraction algorithm needs far more reduction steps than Āryabhaṭa's division algorithm, and state roughly how many each would need.
Answer:
Take gcd(101, 2).
Euclid: about 50 reductions (52 when run). Āryabhaṭa: 2 reductions: gcd(2, 1) → gcd(1, 0).

Teacher's Note:
1. A tiny second number makes subtraction slow.
2. Any gcd(2k + 1, 2) works.

Question 25. Explain why it is enough to look for common divisors up to min(m, n), and not necessary to go as far as max(m, n).
Answer:
A divisor never exceeds the number it divides, so a common divisor cannot exceed the smaller number.
Candidates between min(m, n) and max(m, n) are certain to fail, so testing them is wasted work.

Teacher's Note:
1. Can nearly halve the scan.
2. Safe because nothing is lost.

Question 26. Write down the successive problems produced by Euclid's subtraction algorithm for gcd(30, 12), and state the answer it reports.
Answer:
gcd(30, 12) → gcd(12, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 6) → gcd(6, 0).
gcd(18, 12) comes from the reversing step. Answer: 6 (4 reductions).

Teacher's Note:
1. Reversals are not counted as reductions.
2. Mark which arrow is a reversal.

Question 27. Name the treatise in which Āryabhaṭa's method appears, together with its date, and name the book in which Euclid wrote down his algorithm.
Answer:
Āryabhaṭa: the Āryabhaṭīya (499 CE).
Euclid: the Elements.

Teacher's Note:
1. Both methods predate the word 'algorithm'.
2. Euclid was the first to write his method down.

Question 28. Explain what it means to say that an algorithm has been justified, and state why a justification is needed in addition to the steps themselves.
Answer:
Justifying an algorithm means giving an argument that its answer is correct for every input.
It is needed because following steps correctly does not prove the steps themselves are right; the steps say what, the justification says why.

Teacher's Note:
1. Examples are never enough.
2. A precise procedure can still be wrong.

Question 29. Rewrite the conditional step of the divisors algorithm in the explicit form 'if … then …', and name the quantity it changes.
Answer:
If j divides n, then add j to the list-of-divisors.
It changes the list-of-divisors, which gains one entry at its end.

Teacher's Note:
1. Conditional steps always have an 'if'.
2. Name the quantity that changes.

Question 30. State one way in which the effort required by the divisor-list gcd algorithm depends on the value of the two numbers rather than on the number of digits used to write them.
Answer:
It tests every candidate up to min(m, n), so the number of tests equals the value of the smaller number: doubling that value doubles the work even with no extra digit, and one more digit multiplies the work by about 10.

Teacher's Note:
1. Value-based cost is the weakness.
2. Contrast with Āryabhaṭa's method.