Class 09 | Ganita Manjari 02 | Ch. 11 The World Of Alogrithms | NCERT Solutions

Class 09 | Ganita Manjari 02 | Ch. 11 The World Of Alogrithms | NCERT Solutions

Exercise 11.1

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:
Let us add 5493 and 2658.

Number Addition Steps

Step 1: Write the numbers one below the other, aligning the digits from right to left.
Step 2: Add the ones: 3 + 8 = 11. Write 1 and carry 1.
Step 3: Add the tens: 9 + 5 + 1(carry) = 15. Write 5 and carry 1.
Step 4: Add the hundreds: 4 + 6 + 1(carry) = 11. Write 1 and carry 1.
Step 5: Add the thousands: 5 + 2 + 1(carry) = 8. Write 8 and carry 0.
Thus, the result is 8151, which is correct.

2. What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Solution:
The steps to add two numbers do not handle this situation correctly because it does not explain what to do when one number has no digit in a particular column.
For example:

Number Addition Steps

The missing digits should be treated as 0,
23759 + 00465 = 24224
Therefore, the algorithm needs an additional instruction for columns where one number has no digit.

Number Addition Steps

3. Why is it important to align the columns from right to left?
Solution:
It is important because digits in the same column must have the same place value.
For example, ones must be added to ones, tens to tens, hundreds to hundreds, and so on. This ensures that the addition gives the correct result.

4. In Step 3, why cannot the value of carry be more than 1?
Solution:
When adding two digits, the greatest possible sum including 1 carry is 9 + 9 + 1 = 19.
Therefore, the sum can have one digit to carry to the next column and the value of carry can only be 0 or 1.

Learn Math

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:
If the fifth step is omitted, a final carry of 1 will not be written. Therefore, the algorithm will fail whenever the addition produces a carry from the leftmost column.
Example where it works:
298 + 436 = 734
There is no final carry, so the answer is correct.
Example where it doesn’t work:
567 + 678 = 1245
After adding the leftmost column, 5 + 6 + 1(carry) = 12
Without Step 5, the algorithm writes only the units digit 2 and the final carry 1 is not written, giving 245 instead of 1245.

Learn Math

Exercise 11.2

1. Suppose List 1 and List 2 are wo lists of nurnbers in increasing order.
(i) Write an algorithm to find elements in List 1 that are not present in List 2.
Solution:
Algorithm:
1. Start with an empty list called only-in-1.
2. Take each number x in List 1 from left to right.
3. Check if x is present in List 2. If not, add x to the end of only-in-1.
4. After checking every number in List 1, report only-in-1.

Number Addition Steps

(ii) Write an algorithm to flnd elements in List 2 that are not present in List 1.
Solution:
Algorithm:
1. Start with an empty list called only-in-2.
2. Take each number x in List 2 from left to right.
3. Check if x is present in List 1. If not, add x to the end of only-in-2.
4. After checking every number in List 2, report only-in-2.

2. Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Solution:
Let the two numbers be m and n.
Algorithm:
1. Let multiples-of-m be the list obtained by computing the multiples of m.
2. Let multiples-of-n be the list obtained by computing the multiples of n.
3. Start with an empty list common-multiples.
4. For each number x in the list of multiples-of-m:
If x also appears in the list of multiples-of-n, add x to the list common-multiples.
5. Report the leftmost element of the list common-multiples as LCM (m, n).
The leftmost common multiple is reported because the multiples are listed in increasing order, so the first common multiple is the least common multiple.

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?
Solution:
Divisors of a number occur in pairs. For example, the divisors of 18 are (1, 18), (2, 9), (3, 6).
The product of two divisors in each pair is n.
To find all the divisor pairs of n, we do not need to check all numbers from 1 to n. Once we reach $\sqrt{n}$, the remaining divisors are the corresponding partners of the divisors already found.
For example: for 18,
$\sqrt{18}$≈ 4.24
Thus, we only need to check 1, 2, 3 and 4.
The divisors found are 1, 2, 3 and their corresponding partners are 18, 9, 6.
Therefore, we need to examine numbers only up to $\sqrt{n}$.

(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Solution:
Yes, the GCD algorithm will still work.
The GCD of two numbers is the greatest common divisor of those numbers. Listing the divisors in pairs does not change the divisors; it only groups them differently.
For example, the divisors of 18 can be written as (1, 18), (2, 9), (3, 6).
They are the same divisors whether we list them individually or in pairs. Hence, the common divisors and therefore the GCD remain unchanged.

Exercise 11.3

1. How 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 down to 1?
Solution:
If we examine the numbers from n down to 1, we will still find all the divisors of n. However, they will be listed in decreasing order.
For example, the divisors of 18 would be 18, 9, 6, 3, 2, 1.
Thus, the algorithm for finding the divisors remains the same except for the order in which the divisors are obtained.
If this list is used to find the GCD of two numbers, the first common divisor will be the GCD instead of the last common divisor.

2. What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
Solution:
If we start checking the common divisors from min(m, n) and work backwards to 1, the first common divisor found will be the GCD.
This is because min(m, n) is the largest possible common divisor of m and n. As we move downwards, the first number that divides both m and n must be their greatest common divisor.
Therefore, we can stop the algorithm as soon as the first common divisor is found.
For example, for m = 18 and n = 24, we check 18, 17, 16, ….., 6
Since 6 divides both 18 and 24, we stop and obtain gcd(18, 24) = 6
Thus, this method can be faster because it does not need to check the remaining smaller numbers.