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

Exercise Set 11.2

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 elements in List 2 that are not present in List 1.
Answer:
(i) Simple method (like the common-divisors algorithm):
Algorithm: elements of List 1 not in List 2
1. Start with an empty list only-in-1.
2. For each number x in List 1:
    — if x does not occur in List 2, add x to only-in-1.
3. Report only-in-1.
Faster method using the increasing order. Walk through both lists together. Let a be the current number of List 1 and b the current number of List 2.
1. Start with an empty list only-in-1; let a = first number of List 1 and b = first number of List 2.
2. Repeat until List 1 is used up:
    — if List 2 is used up, add a to only-in-1 and move to the next number of List 1;
    — else if a = b, move to the next number in both lists;
    — else if a < b, add a to only-in-1 and move to the next number of List 1;
    — else (a > b), move to the next number of List 2.
3. Report only-in-1.
Why it is correct: if a < b, every later entry of List 2 is even larger than b, so a can never appear in List 2 and belongs in the answer. If a > b, then b cannot equal a or any later entry of List 1, so we skip b. Every comparison moves forward in at least one list, so at most (length of List 1 + length of List 2) comparisons are needed.
Example: List 1 = divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375], List 2 = divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825].
a = b for 1, 3, 5 (move in both); a = 15, b = 11: a > b, move in List 2; 15 = 15 and 25 = 25 (move in both); a = 75 > b = 33, then > 55 (move in List 2); 75 = 75 (move in both);
a = 125 < b = 165: add 125; a = 375 > 165, > 275 (move in List 2); a = 375 < b = 825: add 375. List 1 is finished.
Elements of List 1 not in List 2: [125, 375].
(ii) Simply swap the roles of the two lists.
Algorithm: elements of List 2 not in List 1
1. Start with an empty list only-in-2.
2. For each number y in List 2:
    — if y does not occur in List 1, add y to only-in-2.
3. Report only-in-2.
(Faster version: the same as in (i) with List 1 and List 2 interchanged — add b when b < a, move in List 1 when b > a, and add all remaining numbers of List 2 once List 1 is used up.)
For the same example, elements of List 2 not in List 1: [11, 33, 55, 165, 275, 825].

Teacher's Note:
1. The simple method is always acceptable; the faster one shows how the increasing order can be exploited.
2. Trace the pointers a and b on the board, one comparison per line, so students see why nothing is missed.

Question 2. Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Answer:
The lcm of m and n is the smallest number that is a multiple of both.
Method 1 (straight from the definition). The lcm must be a multiple of the larger number, so test the multiples of the larger number in order until the smaller number divides one.
Algorithm lcm(m, n)
1. Let big be the larger and small the smaller of m and n.
2. For each k = 1, 2, 3, …:
    — let x = k × big;
    — if small divides x, report x as lcm(m, n) and stop.
The algorithm must stop, at the latest when k = small, because small × big = m × n is a common multiple.
Example: lcm(6, 8): big = 8, small = 6. k = 1: x = 8 (6 does not divide); k = 2: x = 16 (no); k = 3: x = 24 (yes) → stop. So lcm(6, 8) = 24.
Method 2 (using the gcd). For any two numbers \( \text{lcm}(m, n) = \frac{m \times n}{\gcd(m, n)} \).
(Reason: if g = gcd(m, n), then m = ga and n = gb where a and b have no common factor except 1; the smallest common multiple is gab = \( \frac{(ga)(gb)}{g} \).)
Algorithm lcm(m, n) using gcd
1. Find g = gcd(m, n), for example by Euclid's algorithm.
2. Report (m × n) ÷ g as lcm(m, n).
Example: gcd(375, 825) = 75, so lcm(375, 825) = \( \frac{375 \times 825}{75} = \frac{309375}{75} \) = 4125. Check: 4125 = 11 × 375 = 5 × 825.
Method 2 is much quicker for large numbers, since the gcd can be found fast by the division method of Section 11.3.

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?
Answer:
(i) If j divides n, then n = j × k with k = \( \frac{n}{j} \), and k is also a divisor. So divisors come in pairs (j, k) with j × k = n.
Let j be the smaller member of a pair, so j ≤ k. Then j × j ≤ j × k = n, that is, j ≤ √n.
So the smaller member of every pair lies between 1 and √n. We only need to test j = 1, 2, 3, … while j × j ≤ n, and whenever j divides n we record the pair \( \left(j, \frac{n}{j}\right) \).
Example, n = 18: 4 × 4 = 16 ≤ 18 but 5 × 5 = 25 > 18, so test only j = 1, 2, 3, 4: 1 → (1, 18); 2 → (2, 9); 3 → (3, 6); 4 → no. Just 4 tests instead of 18.
For n = 825: 28 × 28 = 784 ≤ 825 < 841 = 29 × 29, so 28 tests are enough instead of 825.
(If n is a perfect square, the pair (√n, √n) gives only one divisor; e.g. for 36 the pair (6, 6) gives just 6.)
We need to examine only the numbers from 1 to √n (about √n numbers) instead of all n numbers.
(ii) Our gcd algorithm builds common-divisors in the order of divisors-of-m and reports the rightmost element. That is right only because the lists are in increasing order.
Pair-by-pair lists are not in increasing order. Take m = 12, n = 18:
divisors-of-m (in pairs) = [1, 12, 2, 6, 3, 4]; divisors-of-n (in pairs) = [1, 18, 2, 9, 3, 6].
Checking each x in divisors-of-m: 1 (yes), 12 (no), 2 (yes), 6 (yes), 3 (yes), 4 (no), so common-divisors = [1, 2, 6, 3]. The rightmost element is 3, but gcd(12, 18) = 6. Wrong answer.
(The earlier steps still collect all the common divisors correctly; only the final "report the rightmost element" step fails.)
No, not in the manner described. It can be repaired either by changing the last step to "report the largest element of common-divisors", or by rearranging the divisors into increasing order: write the smaller members of the pairs left to right and then the larger members right to left. For 12: [1, 2, 3] followed by [4, 6, 12] gives [1, 2, 3, 4, 6, 12].

Teacher's Note:
1. Part (i) is the key idea behind fast primality testing: never test beyond √n.
2. In part (ii), students often say "yes" because all the common divisors are still found; stress that the reporting step depends on the order.
3. A single counter-example, such as gcd(12, 18), is enough to show an algorithm is wrong.