NCERT Solutions Class 9 Mathematics Ganita Manjari 2 Chapter 11 The World of Algorithms Examples

Examples

Example (improved gcd algorithm). Let m = 6, n = 12. Find gcd(m, n) using the improved algorithm that keeps only a single quantity most-recent-common-divisor.
Answer:
min(6, 12) = 6, so we scan k = 2, 3, 4, 5, 6, starting with most-recent-common-divisor = 1.
k = 2: divides 6 and 12 → updated to 2.
k = 3: divides 6 and 12 → updated to 3.
k = 4: divides 12 but not 6 → stays 3.
k = 5: divides neither → stays 3.
k = 6: divides 6 and 12 → updated to 6.
The scan is over, so gcd(6, 12) = 6.

Example 1. Find gcd(99, 2) using the improved (division) version of Euclid's algorithm.
Answer:
Step 1: 99 = 49 × 2 + 1  ⇒  gcd(99, 2) = gcd(2, 1)
Step 2: 2 = 2 × 1 + 0  ⇒  gcd(2, 1) = gcd(1, 0)

Hence gcd(99, 2) = 1.

Example 2. Find gcd(825, 375) using the improved (division) version of Euclid's algorithm.
Answer:
Step 1: 825 = 2 × 375 + 75  ⇒  gcd(825, 375) = gcd(375, 75)
Step 2: 375 = 5 × 75 + 0  ⇒  gcd(375, 75) = gcd(75, 0)

Hence gcd(825, 375) = 75.

Example 3. Find gcd(60, 16) using the improved (division) version of Euclid's algorithm.
Answer:
Step 1: 60 = 3 × 16 + 12  ⇒  gcd(60, 16) = gcd(16, 12)
Step 2: 16 = 1 × 12 + 4  ⇒  gcd(16, 12) = gcd(12, 4)
Step 3: 12 = 3 × 4 + 0  ⇒  gcd(12, 4) = gcd(4, 0)

Hence gcd(60, 16) = 4.

Think and Reflect and In-text Questions

Think and Reflect (page 39), Question 1. See if you can complete the argument about grouping by units, tens, hundreds, … to justify why the addition algorithm works.
Answer:
Take 473 + 695. In place-value form, 473 = 4 hundreds + 7 tens + 3 units and 695 = 6 hundreds + 9 tens + 5 units.
Adding means putting the two collections together, and we may combine them group by group, since the order of combining does not change the total.
Units: 3 + 5 = 8 → 8 units, nothing to carry.
Tens: 7 + 9 = 16 (+ 0 carried) = 16 → keep 6 tens, pass 1 hundred on.
Hundreds: 4 + 6 = 10 (+ 1 carried) = 11 → keep 1 hundred, pass 1 thousand on.
Thousands: 0 + 0 (+ 1 carried) = 1 → 1 thousand.
The regrouping is allowed because 10 units = 1 ten, 10 tens = 1 hundred, 10 hundreds = 1 thousand; in general 10 × 10^k = 10^k+1.
So 473 + 695 = 1 thousand + 1 hundred + 6 tens + 8 units = 1168.
The general argument:
1. Every number is a sum of groups: (units digit) units + (tens digit) tens + (hundreds digit) hundreds + … .
2. So the sum of two numbers is the sum of their unit groups, plus the sum of their ten groups, and so on; adding the groups separately is exactly adding column by column.
3. A group's total may reach 10 or more. Ten of one group make one of the next higher group, so we keep the units digit of the total and pass 1 to the next group: this is the carry.
4. We work right to left (units first) because a carry always goes to the next higher group on the left, and that group must receive its carry before its own total is settled.
5. After the last group, a leftover carry forms a new group on the left: this is Step 5.
Each step only regroups the same collection, so the total never changes and the digits written are exactly the place-value digits of the sum. This justifies the addition algorithm.

Teacher's Note:
1. Physical bundles (sticks tied in tens and hundreds) make the regrouping argument concrete.
2. Link point 4 to Exercise 11.1, Q3: the order of work and the alignment both come from place value.

Think and Reflect (page 39), Question 2. How would you modify the algorithm to add two decimal fractions?
Answer:
In a decimal fraction the places after the point are tenths, hundredths, thousandths, … . The rightmost digits of two decimals need not have the same place value (in 12.75 it is hundredths, in 3.6 it is tenths). What lines up place values is the decimal point.
Modified algorithm to add two decimal fractions
1. Write the numbers one below the other with their decimal points in the same column (units under units, tenths under tenths, and so on).
2. If one number has fewer digits after the point, attach 0s at its right end so both have the same number of decimal places. (Missing digits on the left are also taken as 0.)
3. Ignoring the point, add column by column from right to left exactly as for whole numbers (carry 0 or 1).
4. Put the decimal point in the answer directly below the points of the two numbers.
This works because 10 hundredths = 1 tenth and 10 tenths = 1 unit, so carrying across the decimal point is just as before.
Example: 12.75 + 3.6. Write 3.6 as 3.60. Hundredths: 5 + 0 = 5; tenths: 7 + 6 = 13 → write 3, carry 1; units: 2 + 3 + 1 = 6; tens: 1 + 0 = 1.

12.75 + 3.6 = 16.35.

Think and Reflect (page 41). 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:
Algorithm divisors(n): start with an empty list-of-divisors; for each j = 1, 2, 3, …, n, if j divides n, add j to the list.
(a) n = 15. j = 1: yes (15 = 1 × 15) → [1]; j = 2: no; j = 3: yes (15 = 3 × 5) → [1, 3]; j = 4: no; j = 5: yes → [1, 3, 5]; j = 6 to 14: no; j = 15: yes → [1, 3, 5, 15].
divisors(15) = [1, 3, 5, 15], after testing 15 numbers.
(b) n = 135. Every j from 1 to 135 is tested. Since 135 = 1 × 135 = 3 × 45 = 5 × 27 = 9 × 15, and all other numbers leave a remainder, the algorithm finds, in order,
divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135], after testing 135 numbers.
(c) n = 775. Every j from 1 to 775 is tested. Since 775 = 1 × 775 = 5 × 155 = 25 × 31,
divisors(775) = [1, 5, 25, 31, 155, 775], after testing 775 numbers.
How the work grows
n = 15: 15 tests, 4 divisors; n = 135: 135 tests, 8 divisors; n = 775: 775 tests, 6 divisors.

The algorithm tests every number from 1 to n, so the number of tests equals n. It does not depend on how many divisors n has: 135 has more divisors than 775, yet 775 needs far more work.
From 15 to 135 the work becomes 9 times as much; from 15 to 775 it becomes about 52 times as much.
Each extra digit makes a number roughly 10 times larger, so each extra digit multiplies the work by about 10. (Each single test, dividing n by j, also gets harder as the numbers grow.)
The work grows in proportion to the value of the number, not to its number of digits.

In-text Question (page 48). 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:
The improved algorithm: (1) if m < n, swap and compute gcd(n, m); (2) if n = 0, report m; (3) otherwise reduce to gcd(n, m mod n).
Let k be any natural number, m = 2k + 1 and n = 2.
Step 1: k ≥ 1, so m = 2k + 1 ≥ 3 > 2; no swap.
Step 2: n = 2 ≠ 0.
Step 3 (first reduction): 2k + 1 = k × 2 + 1, so (2k + 1) mod 2 = 1 (an odd number always leaves remainder 1 on division by 2). The problem becomes gcd(2, 1).
Step 3 (second reduction): 2 = 2 × 1 + 0, so 2 mod 1 = 0 and the problem becomes gcd(1, 0).
Step 2: n = 0, so the answer is 1.
gcd(2k + 1, 2) = gcd(2, 1) = gcd(1, 0) = 1.
None of this depends on k, so every problem of the form gcd(2k + 1, 2) needs exactly two reduction steps.
For instance: k = 7, gcd(15, 2): 2 division steps (about 8 by subtraction); k = 49, gcd(99, 2): 2 steps (about 50 by subtraction); k = 500, gcd(1001, 2): 2 steps (about 501 by subtraction).
With repeated subtraction the number of reductions grows with k, but with the division (remainder) method it stays at 2.

Teacher's Note:
1. The argument works for a general k, so it covers infinitely many cases at once; a table of examples alone would not prove it.
2. Compare the two columns of the last line to show why division beats repeated subtraction.