Ganita Manjari Class 9 Chapter 11 Solutions The World of Algorithms

Students often refer to Ganita Manjari Class 9 Solutions and Part 2 Class 9 Maths Chapter 11 The World of Algorithms Solutions to verify their answers.

The World of Algorithms Class 9 Solutions

Class 9 Ganita Manjari Chapter 11 Solutions

Class 9 Maths Ganita Manjari Chapter 11 Solutions The World of Algorithms

Think and Reflect (NCERT Textbook Page No. 39)

Question 1.
See if you can complete the argument about grouping by units, tens, hundreds, …to justify why the addition algorithm works.
Solution:
Each column contains equal place-value groups. Suppose the total in one column is S. We can write S as 10c + r, where r is the units digit of S and c is the carry value. Writing r in the current column and carrying c to the next column does not change the total value because ten groups of one place value form one group of the next place value.
S x 10^k = r x 10^k + c x 10^k+1
Here, the power of ten is the place value of the current column. The same argument works successively for units, tens, hundreds and every column to the left.

For 473 + 695:

• Units: 3 + 5 = 8, so write 8.
• Tens: 7 + 9 = 16 tens. This is 6 tens and 1 hundred, so write 6 and carry 1.
• Hundreds: 4 + 6 + 1 = 11 hundreds. This is 1 hundred and 1 thousand, so write 1 and carry 1.
• The final carry gives the thousands digit 1. Hence, the sum is 1168.

At every stage, the same total quantity is merely regrouped. Therefore, the column addition algorithm gives the correct sum.

Question 2.
How would you modify the algorithm to add two decimal fractions?
Solution:
1. Write the decimal fractions one below the other with their decimal points aligned.
2. Add trailing zeros, if needed, so both numbers have the same number of decimal places.
3. Add from the rightmost column to the left, using the same carry rule as for whole numbers.
4. Place the decimal point in the answer directly below the aligned decimal points.
5. If a final carry remains, write it on the left.
Example:

• Hundredths: 5 + 0 = 5.
• Tenths: 7 + 8 = 15. Write 5 and carry 1 to the units column.
• Units: 2 + 3 + 1 = 6.
• Tens: 1 + 0 = 1.

Think and Reflect (NCERT Textbook Page No. 41)

Try to execute the algorithm for 15, 135 and 775. How does the amount of work increase as the numbers grow?
Solution:
The algorithm tests every integer from 1 to n. Whenever j divides n, it is added to list-of-divisors. The list changes at the following values.

For 15, the list is updated at j = 1, 3, 5 and 15. divisors (15) = [1, 3, 5, 15]
For 135, it is updated at j = 1, 3, 5, 9, 15, 27, 45 and 135. divisors (135) = [1, 3, 5, 9, 15, 27, 45, 135]
For 775, it is updated at y = 1, 5, 25, 31, 155 and 775. divisors (135) = [1, 5, 25, 31, 155, 775]
All other tested values leave the list unchanged. The number of checks is exactly n, so the work grows directly with the value of n, not with the number of divisors found. For example, 135 requires 9 times as many checks as 15, and 775 requires 775 checks even though it has only 6 divisors.

Ex 11.1 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Exercise 11.1 Solutions

Exercise 11.1 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Ex 11.1 Solutions

Question 1.
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?
Solution:
The algorithm steps stated (refer NCERT textbook page 38) is incomplete because it does not say what to do when a column sum is exactly 10.

Algorithm to add two numbers
1. Write the numbers one below the other in the Indian baseten place-value system so that the digits are aligned
from right to left.

2. Add the rightmost digits.

• If the sum is less than 10, write the sum directly below the two digits. Set the value of carry to 0.
• If the sum is more than 10, write the units digit of the sum directly below the two digits. Set the value of carry to 1.

3. Move to the next column of digits on the left. Add the two digits and the current value of carry.

• If the sum is less than 10, write the sum directly below the two digits. Set the value of carry to 0.
• If the sum is more than 10, write the units digit of the sum directly below the two digits. Set the value of carry to 1.

4. Repeat Step 3 until there are no more digits on the left.

5. If the value of carry is 1, write 1 to the left of the bottom row.
Take the two 4-digit numbers 2468 and 7532.
Write the numbers one below the other in the Indian base- ten place-value system.
In the units column, 8 + 2 = 10. In step 2, the two stated conditions are ‘less than 10’ and ‘more than 10’. Neither condition applies to 10, so the algorithm gives no next action and cannot be completed exactly as written.
The correction is to replace ‘more than 10’ with ‘equal to or more than 10’ in Steps 2 and 3.

Units: 8 + 2=10. Write 0 and carry 1.
Tens: 6 + 3 + 1 = 10. Write 0 and carry 1.
Hundreds: 4 + 5 + 1 = 10. Write 0 and carry 1.
Thousands: 2 + 7 + 1 = 10. Write 0 and carry 1.
Step 5 writes the final carry 1 on the left, giving 10000.
2468 + 7532 = 10000

Question 2.
What happens if you add a 5-digit number to a 3-digit number? Do our steps handle this situation correctly?
Solution:
No. The original steps do not explain how to handle a column in which the shorter number has no digit.
For example, consider 12345 + 123. After three columns, the digits of 123 are exhausted, but Step 3 still says to add two digits.
Treat each missing leading digit as 0. Equivalently, place leading zeros before the shorter number:

Units: 5 + 3 = 8.
Tens: 4 + 2 = 6.
Hundreds: 3 + 1 = 4.
Thousands: 2 + 0 = 2.
Ten-thousands: 1 + 0 = 1.
Therefore, the algorithm works for numbers of unequal length only after adding the rule that a missing leading digit is treated as 0.

Question 3.
Why is it important to align the columns from right to left?
Solution:
It is important to align the columns from right to left, because even if two numbers have different numbers of digits, their digits with the same place-value position must come under the same column. The right most digits always represent the ones place. If the numbers are not right-aligned, unlike place values are added, and the result is incorrect.

For example, 347 and 25 must be written as .

Then 7 units are added to 5 units, and 4 tens are added to 2 tens.

Question 4.
In Step 3, why cannot the value of carry be more than 1?
Solution:
The greatest possible total in a column is obtained by adding two digits, 9 and 9, along with a carry of 1.
9 + 9 + 1 = 19
The tens digit of any total from 0 to 19 is either 0 or 1. Therefore, the carry to the next column can only be 0 or 1, never more than 1.

Question 5.
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.
Solution:
Step 5 is needed only when the leftmost column produces a final carry.
Example where the algorithm still works:

The leftmost column has no carry, so omitting Step 5 does not change the answer.
Example where the algorithm fails:

The thousands column gives 8 + 7 + 1 = 16. The digit 6 is written in the thousands place and 1 remains as a final carry. Without Step 5, the algorithm would report 6419 as the final sum instead of 16419.

Ex 11.2 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Exercise 11.2 Solutions

Exercise 11.2 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Ex 11.2 Solutions

Question 1.
Suppose List 1 and List 2 are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in List 1 that are not present in List 2.
(ii) Write an algorithm to find the elements in List 2 that are not present in List 1.
Solution:
(i) 1. Start with an empty list called only-in-List-1.
2. For each number x in List 1:
If x does not appear in List 2, add x to only-in-List-1.
3. Report only-in-List-1.
Because List 1 is in increasing order, the reported list is also in increasing order.

(ii) 1. Start with an empty list called only-in-List-2.
2. For each number x in List 2:
If x does not appear in List 1, add x to only-in-List-2.
3. Report only-in-List-2.
This is the same procedure with the roles of the two lists reversed.

Question 2.
Describe an algorithm to compute the least common multiple (LCM) of two numbers.
Solution:
1. Let larger-number be max (m, n) and smaller-number be min (m, n).
2. Set current-multiple = larger-number.
3. Check: If smaller-number divides current-multiple exactly, report current-multiple as 1cm (m, n) and stop. Otherwise, go to step 4
4. Update current-multiple by adding larger-number to it. Go back to step 3.
Let us verify the algorithm with the numbers 12 and 18.

• Larger-number = 18, smaller-number = 12
• Current-multiple = 18 → is 18 divisible by 12? No.
• Current-multiple = 18 + 18 = 36 → is 36 divisible by 12?

Yes → LCM = 36. Stop.

Question 3.
Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
(i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n?
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Solution:
(i) Look at the pairs of divisors of 18: (1, 18), (2, 9), (3,6)
In each pair, one number is smaller and the other is larger, and their product is always 18.
As we check numbers in increasing order: 1, 2, 3, 4,… the smaller number in each divisor pair increases, while its corresponding larger number (18 ÷ smaller number) decreases. The two numbers move closer to each other.
At some point, the two numbers meet. After this point, the divisor pairs only appear in the reverse order. Checking further numbers would not give any new divisors; it would only repeat the pairs already found.
Therefore, instead of checking every number from 1 to n, we only need to check numbers up to the largest number whose square is less than or equal to n.
For 18:
4 × 4 = 16 < 18
5 × 5 = 25 > 18
So, we only need to check:
1, 2, 3, 4
That is, only 4 numbers instead of all 18 numbers. In general, to find all divisors of a number n, we only need to examine numbers up to √n. This is a much smaller number of checks compared to examining every number from 1 to n, especially when n is large.

(ii) No, not without one further change.
Pairwise generation does not usually place the divisors in increasing order. Therefore, the common- divisors list is not guaranteed to be increasing, and its rightmost element need not be the greatest.
For example, pairwise lists may be formed as follows:
divisors(36) = [1, 36, 2, 18, 3, 12, 4, 9, 6]
divisors(24) = [1, 24, 2, 12, 3, 8, 4, 6]
Scanning the first list produces common-divisors = [1,2, 12, 3, 4, 6], Its rightmost element is 6, but gcd(36, 24)= 12.
To correct the algorithm, sort the divisor lists before using the rightmost-element rule, or keep track of the largest common divisor found rather than the most recent one.

Ex 11.3 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Exercise 11.3 Solutions

Exercise 11.3 Class 9 Ganita Manjari Solutions – Ganita Manjari Class 9 Ex 11.3 Solutions

Question 1.
Flow 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 to down 1?
Solution:
The divisor list would be in decreasing order rather than increasing order.

• Start with an empty list-of-divisors.
• For each j in the sequence n, n – 1, n – 2, …, 1, add j when j divides n.

If both divisor lists are formed this way, the common- divisors list is also in decreasing order. Step 5 of the gcd algorithm must therefore report the leftmosfelement, not the rightmost element.
For example: For 18 and 24, the common-divisors list is [6, 3, 2, 1], The leftmost element 6 is the gcd.
The algorithm may also stop as soon as the first common divisor is found, because later common divisors will be smaller.

Question 2.
What about the last algorithm described above? What happens when we look at common divisors starting from min(m, ri) and work backwards to 1?
Solution:
The first common divisor found is automatically the greatest common divisor. There is no need to store a list or maintain most-recent-common-divisor.

If we look at common divisors starting from min(m, n) and work backwards to 1, then:
1. Set k to min(m, n).
2. If k divides both m and n, report k as gcd(m, n) and stop.
3. Otherwise, reduce k by 1 and repeat Step 2.

For m = 18 and n = 24, scanning downwards first reaches the common divisor 6, so gcd(18, 24) = 6.
This often stops early, but in the worst case of coprime numbers, it still scans down to 1.

Ganita Manjari Class 9 Maths Chapter 11 End of Chapter Exercise Solutions

The World of Algorithms End of Chapter Exercise Solutions

Question 1.
Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375, 825)
Solution:

(ii) gcd(51000, 81000)
Solution:

(iii) gcd( 1789287, 237656)
Solution:

(iv) gcd(2587392, 157656)
Solution:

Question 2.
Assume that m > n. Verify that d divides m and n if and only if d divides both n and m mod n.
Solution:
By the division algorithm, write m = qn + r, where r = m mod n and 0 ≤ r < n.
m = qn + r

Forward direction
Suppose d divides both m and n. Then m = ad and n = bd for some integers a and b.
r = m – qn = ad- qbd = (a- qb)d
Thus d divides r. Since r = m mod n, d divides both n and m mod n.

Reverse direction
Suppose d divides both n and m mod n(r). Then n = bd and r = cd for some integers b and c.
m = qn + r = qbd + cd= (qb 4- c)d
Thus, d divides m. Therefore, d divides m and n if and only if d divides n and m mod n.

Question 3.
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(w) to write out prime (n)?]
Solution:
1. If n is less than 2, report False and stop.
2. Let list-of-divisors be the list obtained by computing divisors(w).
3. If list-of-divisors contains exactly the two distinct values 1 and n, report True.
4. Otherwise, report False.
This works because a prime number has exactly two distinct positive divisors, 1 and itself.
For example, divisors (13) = [1, 13], so prime (13) is True; divisors (15) = [1,3, 5, 15], so prime (15) is False.

Question 4.
Write an algorithm prime divisors(w) to compute the list of divisors of n that are prime numbers.
[Hint: Compute divisors(w) and then filter out the primes in this list.]
Solution:
1. Let list-of-divisors be the list obtained by computing divisors(w).
2. Start with an empty list called list-of-prime-divisors.
3. For each number x in list-of-divisors:
If primc(x) is True, add x to list-of-prime-divisors.
4. Report list-of-prime-divisors.
Example: divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]. After filtering, prime divisors(60) = [2, 3, 5],

Question 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.
(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?
Solution:
1. Let list-of-prime-divisors be prime divisors (n).

2. Start with an empty list called factor-pairs.

3. For each prime p in list-of-prime-divisors:

• Set exponent to 0.
• While p divides n:
  • Divide n by p.
  • Increase exponent by 1.
• Add the pair (p, exponent) to factor-pairs.

4. Report factor-pairs.
Each pair records one prime factor and the number of times it divides n.
(i) 180 = 2² × 3² × 5¹
A convenient data-structure representation is the list of pairs [(2, 2), (3, 2), (5, 1)]. In each pair, the first value is the prime and the second value is its exponent.

(ii) Match equal primes in the two factor-pair lists. Keep only the primes present in both numbers, and use the smaller exponent for each common prime.

If a prime is absent from one factorisation, treat its exponent as 0, so it contributes no factor to the gcd. Example:
180 = 2² × 3² × 5¹
84 = 2² × 3 × 7
gcd( 180, 84) = 2^{min(2, 2)} × 3^{min(2, 1)} = 4 × 3 = 12
Therefore, gcd(180, 84) = 12.