CLASS 9 · GANITA MANJARI PART II · CHAPTER 11

The World of Algorithms

Write, test and improve precise algorithms for addition, divisors, GCD, LCM, primes and prime factorisation.

22 worked answersAll 4 exercise sets

What you will learn

Describe a step-by-step algorithm precisely.
Explain why an algorithm is correct.
Use efficient GCD and prime-factorisation procedures.

Read the NCERT questions ↗← All chapters

22 worked answers · short steps first, explanations when you need them

Exercise Set 11.1

Textbook pages 38

Question 1

Use the stated digit-by-digit algorithm to add two four-digit numbers; show one valid example.

Steps only

Example: 4,738 + 2,695

Units: 8 + 5 = 13; write 3, carry 1.

Tens: 3 + 9 + 1 = 13; write 3, carry 1.

Hundreds: 7 + 6 + 1 = 14; write 4, carry 1.

Thousands: 4 + 2 + 1 = 7. Result: 7,433.

Answer

For example, 4,738 + 2,695 = 7,433. Leave the final carry at 0.

Question 2

What happens when the stated addition algorithm adds a five-digit number to a three-digit number?

Steps only

Example: align 12,345 and 678 as 12,345 and 00,678.

The written algorithm asks for two digits in every column, but the shorter number has no digits in the two left columns.

Treating missing leading places as zeros fixes the procedure.

Answer

As originally worded, the algorithm does not fully handle unequal lengths. Add the rule “pad the shorter number with leading zeros”.

Question 3

Why must columns be aligned from the right when adding whole numbers?

Steps only

The rightmost column represents units.

The next columns represent tens, hundreds, thousands, and so on.

Right alignment puts equal place values in the same column.

Answer

Right alignment ensures that units are added to units, tens to tens, and so on.

Question 4

Why can the carry in Step 3 never exceed 1?

Steps only

Largest possible column total = 9 + 9 + 1 = 19.

19 contains one ten and nine units.

Answer

The carry is at most 1.

Question 5

What happens if the final-carry step is omitted? Give one success and one failure example.

Steps only

Works: 1,234 + 1,111 = 2,345; the last column creates no carry.

Fails: 4,738 + 6,695 should be 11,433; omitting the final carry reports 1,433.

Answer

It works only when the leftmost processed column leaves carry 0; it loses the leading 1 when the final carry is 1.

Exercise Set 11.2

Textbook pages 43–44

Question 1(i)

Write an algorithm that lists elements of increasing List 1 that are absent from increasing List 2.

Steps only

Start missing-from-2 as an empty list.

For each x in List 1: if x does not appear in List 2, append x to missing-from-2.

Report missing-from-2.

Answer

Scan List 1 and retain exactly the values that are not members of List 2.

Question 1(ii)

Write an algorithm that lists elements of increasing List 2 that are absent from increasing List 1.

Steps only

Start missing-from-1 as an empty list.

For each x in List 2: if x does not appear in List 1, append x to missing-from-1.

Report missing-from-1.

Answer

Scan List 2 and retain exactly the values that are not members of List 1.

Question 2

Describe an algorithm to compute lcm(m,n) for positive integers.

Steps only

Set k = max(m,n).

While k is not divisible by both m and n, increase k by 1.

Report the first k divisible by both.

Answer

The first common multiple reached is lcm(m,n).

Question 3(i)

If divisors of n are generated in pairs, how many candidate numbers must be examined?

Steps only

If j divides n, its paired divisor is n/j.

Once j exceeds √n, its partner is below √n and has already appeared.

Answer

Only the integers from 1 through ⌊√n⌋ need to be examined.

Question 3(ii)

Will the original GCD algorithm still work when divisors are generated in pairs?

Steps only

All divisors are still found, so intersecting the two divisor collections is valid.

Pairwise discovery does not automatically place the full list in increasing order.

Sort the common divisors or track the largest common value while scanning.

Answer

Yes, after removing the assumption that the rightmost item is automatically the greatest.

Exercise Set 11.3

Textbook pages 45

Question 1

How does the original GCD algorithm change if divisors are examined from n down to 1?

Steps only

Each divisor list is produced in decreasing order.

The common-divisor list is also decreasing.

Report its leftmost element, not its rightmost element.

Answer

The algorithm remains correct after changing the final selection from rightmost to leftmost.

Question 2

What happens if the no-list GCD scan starts at min(m,n) and works backwards to 1?

Steps only

For k = min(m,n), min(m,n) − 1, …, 1: test whether k divides both numbers.

Stop and report the first successful k.

Answer

The first common divisor found is the GCD, so the scan can stop immediately.

End-of-Chapter Exercises

Textbook pages 50

Question 1(i)

Compute gcd(375, 825) using repeated division by the remainder.

Steps only

825 = 2×375 + 75

375 = 5×75 + 0

Answer

gcd(375, 825) = 75.

Question 1(ii)

Compute gcd(51000, 81000) using repeated division by the remainder.

Steps only

81000 = 1×51000 + 30000

51000 = 1×30000 + 21000

30000 = 1×21000 + 9000

21000 = 2×9000 + 3000

9000 = 3×3000 + 0

Answer

gcd(51000, 81000) = 3000.

Question 1(iii)

Compute gcd(1789287, 237656) using repeated division by the remainder.

Steps only

1789287 = 7×237656 + 125695

237656 = 1×125695 + 111961

125695 = 1×111961 + 13734

111961 = 8×13734 + 2089

13734 = 6×2089 + 1200

2089 = 1×1200 + 889

1200 = 1×889 + 311

889 = 2×311 + 267

311 = 1×267 + 44

267 = 6×44 + 3

44 = 14×3 + 2

3 = 1×2 + 1

2 = 2×1 + 0

Answer

gcd(1789287, 237656) = 1.

Question 1(iv)

Compute gcd(2587392, 157656) using repeated division by the remainder.

Steps only

2587392 = 16×157656 + 64896

157656 = 2×64896 + 27864

64896 = 2×27864 + 9168

27864 = 3×9168 + 360

9168 = 25×360 + 168

360 = 2×168 + 24

168 = 7×24 + 0

Answer

gcd(2587392, 157656) = 24.

Question 2

For m ≥ n, verify that d divides m and n exactly when d divides n and m mod n.

Steps only

Write m = qn + r, where r = m mod n.

If d divides m and n, then d divides r = m − qn.

If d divides n and r, then d divides m = qn + r.

Answer

Thus d | m and d | n if and only if d | n and d | (m mod n).

Question 3

Write an algorithm prime(n) that checks whether n is prime.

Steps only

If n < 2, report false.

Compute divisors(n).

If the list is exactly [1,n], report true; otherwise report false.

Answer

prime(n) is true exactly when n has the two distinct positive divisors 1 and n.

Question 4

Write an algorithm primedivisors(n).

Steps only

Set result to an empty list.

For each d in divisors(n): if prime(d) is true, append d to result.

Report result.

Answer

The reported list contains exactly the prime divisors of n.

Question 5(i)

Describe how to represent the prime factorisation 180 = 2² × 3² × 5¹.

Steps only

Store ordered pairs (prime, exponent).

For 180: [(2,2), (3,2), (5,1)].

Answer

Represent 180 by [(2,2), (3,2), (5,1)].

Question 5(ii)

How can prime-factor representations be compared to find a GCD or LCM?

Steps only

For each prime in either list, compare its exponents.

GCD: keep the smaller exponent; a missing prime has exponent 0.

LCM: keep the larger exponent.

Answer

Use component-wise minimum exponents for the GCD and maximum exponents for the LCM.

Question 5

Write an algorithm to compute the prime factorisation of n.

Steps only

Set remaining = n and factors = an empty list.

For p = 2, 3, … while p² ≤ remaining: repeatedly divide remaining by p and count the divisions; append (p,count) when count > 0.

If remaining > 1, append (remaining,1). Report factors.

Answer

The algorithm returns the prime–exponent pairs whose product is n.