studycbse.online

Class 9 Maths Part 2 Chapter 11 – The World of Algorithms | Ganita Manjari Notes & Book Solutions

Class 9 Maths Part 2 Chapter 11 – The World of Algorithms from Ganita Manjari with easy Notes and complete Book Solutions. Get clear explanations, important concepts, questions and answers, and revision material to help Class 9 students learn, practise and prepare effectively for examinations.

Class 9 Maths Chapter 11 – The World of Algorithms | Notes and Solutions
Zoom:

Class 9 Maths – Chapter 11

The World of Algorithms
Easy Notes, Concepts and Complete Book Solutions
This page explains algorithms in simple language and provides solutions to all the questions included in the chapter material. Solutions are hidden initially so that students can first try the questions themselves.
Chapter Introduction
What is an algorithm?
An algorithm is a clear, step-by-step procedure used to solve a problem or complete a task.
Simple example:
A recipe tells us step by step how to prepare food. In a similar way, an algorithm tells us step by step how to solve a mathematical problem.
Important features of an algorithm:
  • It has clearly defined steps.
  • The steps are followed in a particular order.
  • Some steps may be repeated.
  • Some steps may be performed only when a condition is true.
  • The algorithm should give the correct result.
  • We can study how much work an algorithm requires.
11.1 Adding Numbers
We can add numbers by counting objects one by one, but this becomes very slow for large numbers. The usual column-addition method is an algorithm because it gives us a fixed sequence of steps.
Algorithm to Add Two Numbers
  1. Write the numbers one below the other in the Indian base-ten place-value system so that the digits are aligned from right to left.
  2. Add the rightmost digits.
  3. If the sum is less than 10, write the sum directly below the two digits and set the carry to 0.
  4. If the sum is 10 or more, write the units digit below the two digits and set the carry to 1.
  5. Move to the next column on the left. Add the two digits and the current carry.
  6. Repeat the process until there are no more digits on the left.
  7. If the final carry is 1, write 1 to the left of the bottom row.
Why does carrying happen?
Ten units make one ten. Ten tens make one hundred. Whenever a column gives 10 or more, the extra group of ten is carried to the next column.
Why is this algorithm useful?
Instead of counting every object, we work with place-value groups: units, tens, hundreds, thousands and so on. Therefore, even very large numbers can be added quickly.
Exercise Set 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?
Take an example:

3478 + 2657
Units: 8 + 7 = 15. Write 5 and carry 1.
Tens: 7 + 5 + 1 = 13. Write 3 and carry 1.
Hundreds: 4 + 6 + 1 = 11. Write 1 and carry 1.
Thousands: 3 + 2 + 1 = 6.
Therefore,

3478 + 2657 = 6135
Answer: Yes. The algorithm gives the correct result.
2. What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Yes. The numbers are aligned from the right.

The 3-digit number occupies the units, tens and hundreds columns. The remaining columns of the 5-digit number are treated as having no corresponding digit in the smaller number.

For example:
12345 + 678 = 13023
Answer: Yes, the algorithm can handle numbers with different numbers of digits.
3. Why is it important to align the columns from right to left?
In our place-value system, the rightmost column represents units, the next represents tens, then hundreds, thousands and so on.

Therefore, digits with the same place value must be placed in the same column.
Answer: To make sure that units, tens, hundreds and other place values are added correctly.
4. In Step 3, why cannot the value of carry be more than 1?
When adding two digits, the largest possible sum is 9 + 9 = 18.

If there is already a carry of 1, the largest possible total is 9 + 9 + 1 = 19.

In either case, at most one group of ten is carried to the next column.
Answer: Because the largest possible column total is 19, so only one group of ten can be carried.
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.
The fifth step deals with the final carry.

For example:
23 + 14 = 37. There is no final carry, so the result is still correct.

But:
58 + 67 = 125.
If the final carry is ignored, we may write 25 instead of 125.

Answer: The algorithm works when there is no final carry, but it fails when a final carry is produced.
Justifying the Addition Algorithm
A good algorithm must not only give an answer; we should also be able to explain why it gives the correct answer.
Suppose a number has units, tens, hundreds and thousands. The addition algorithm adds each place-value group separately.

If 10 units are formed, they are replaced by 1 ten. If 10 tens are formed, they are replaced by 1 hundred. This is exactly what the carry operation does.
Questions on the Addition Algorithm
1. See if you can complete the argument about grouping by units, tens, hundreds, … to justify why the addition algorithm works.
Every number can be separated into place-value groups.

For example:
347 = 3 hundreds + 4 tens + 7 units
When two numbers are added, we can add their units, tens and hundreds separately. Whenever ten units are formed, they become one ten and are carried to the tens column. Similarly, ten tens become one hundred.

Therefore, adding each column from right to left gives the same total as adding the complete numbers.
Answer: The algorithm works because place-value groups can be added separately, with each group of ten carried to the next place.
2. How would you modify the algorithm to add two decimal fractions?
The decimal points should first be aligned vertically.

Then add the digits column by column, just as with whole numbers.

Example:
12.45 + 3.72 = 16.17
Answer: Align the decimal points first and then apply the same column-addition procedure from right to left.
11.2 Greatest Common Divisor
The Greatest Common Divisor (GCD) of two numbers is the greatest number that divides both numbers exactly.

It is also called the Highest Common Factor (HCF).
To find the GCD using the definition:
  1. Find the divisors of the first number.
  2. Find the divisors of the second number.
  3. Find the common divisors.
  4. Choose the greatest common divisor.
11.2.1 Computing the Divisors of a Number
A divisor of a number is a number that divides it exactly, leaving remainder 0.
Algorithm to Find the Divisors of n
  1. Start with an empty list of divisors.
  2. For each number j in the sequence 1, 2, 3, …, n:
  3. If j divides n, add j to the list of divisors.
Example: Divisors of 18

Check every number from 1 to 18.

The numbers that divide 18 exactly are:
Divisors(18) = [1, 2, 3, 6, 9, 18]
The basic operation assumed here is that we know how to check whether one number divides another number.
Think and Reflect
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?
Divisors of 15:
[1, 3, 5, 15]
Divisors of 135:
[1, 3, 5, 9, 15, 27, 45, 135]
Divisors of 775:
[1, 5, 25, 31, 155, 775]
The algorithm checks every number from 1 up to n. Therefore, as n becomes larger, the number of checks also increases.
Answer: The amount of work increases with the value of the number because every number from 1 to n is checked.
11.2.2 Finding the Greatest Common Divisor
After finding the divisor lists of two numbers, compare the two lists and identify the largest number appearing in both.
Example:

Divisors of 375:
[1, 3, 5, 15, 25, 75, 125, 375]

Divisors of 825:
[1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]

Common divisors:
[1, 3, 5, 15, 25, 75]

Therefore:
GCD(375, 825) = 75
11.2.3 First Algorithm for GCD
  1. Find the list of divisors of m.
  2. Find the list of divisors of n.
  3. Start with an empty list of common divisors.
  4. For every divisor of m, check whether it also appears in the divisor list of n.
  5. If it appears in both lists, add it to the common-divisors list.
  6. The rightmost element of the common-divisors list is the GCD.
11.3 Data Structures
A data structure is a way of organising information so that an algorithm can use it efficiently.
In this chapter, a list is used as a data structure.

For example:
[1, 2, 3, 6, 9, 18]
is a list of divisors of 18.
Exercise Set 11.2
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.
  1. Start with an empty list called answer.
  2. Take each element x from List 1.
  3. Check whether x is present in List 2.
  4. If x is not present in List 2, add x to answer.
  5. After checking all elements, report answer.
Answer: Check every element of List 1 and keep only those elements that are absent from List 2.
(ii) Write an algorithm to find elements in List 2 that are not present in List 1.
  1. Start with an empty list called answer.
  2. Take each element x from List 2.
  3. Check whether x is present in List 1.
  4. If x is not present in List 1, add x to answer.
  5. After checking all elements, report answer.
Answer: Check every element of List 2 and keep only those elements that are absent from List 1.
2. Describe an algorithm to compute the least common multiple (lcm) of two numbers.
One simple algorithm is:
  1. Find the multiples of the first number.
  2. Find the multiples of the second number.
  3. Compare the two lists.
  4. Find the first number that appears in both lists.
  5. That number is the LCM.
For example, for 6 and 8:
Multiples of 6: 6, 12, 18, 24, …
Multiples of 8: 8, 16, 24, …
Therefore:
LCM(6, 8) = 24
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?
Divisors occur in pairs:

If d divides n, then n/d is also a divisor. Therefore, once we check numbers up to the square root of n, their corresponding partners give the remaining divisors.
We need to examine numbers only up to √n.
Answer: We need to check numbers from 1 up to √n.
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Yes. Listing the divisors in pairs still gives all the divisors. Therefore, comparing the complete divisor lists will still give all common divisors.
Answer: Yes, provided all divisor pairs are included correctly.
11.3.1 Improving the Algorithm
An algorithm can often be improved so that it performs less work while producing the same answer.
Improvement 1: Compute Both Divisor Lists Together
Instead of checking 1 to m and then 1 to n separately, we can check numbers from 1 to max(m,n) only once.

For every number j:
  • If j divides m, add it to the divisor list of m.
  • If j divides n, add it to the divisor list of n.
Improvement 2: Directly Find Common Divisors
A common divisor cannot be larger than the smaller of the two numbers. Therefore, we only need to check numbers from 1 to min(m,n).

For each number j:
If j divides both m and n, add j to the common-divisors list.
Improvement 3: Do Away with Lists
We do not really need to store every common divisor. We only need the largest one found so far.

Start with:
most-recent-common-divisor = 1
Then check each number from 2 to min(m,n). Whenever a number divides both numbers, update the most-recent-common-divisor.
Improved GCD Algorithm:
  1. Set most-recent-common-divisor = 1.
  2. For each k from 2 to min(m,n):
  3. If k divides both m and n, update most-recent-common-divisor to k.
  4. After the scan, report most-recent-common-divisor.
Questions on the Improved Algorithm
Exercise Set 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?
The algorithm would check:
n, n−1, n−2, …, 2, 1
Whenever a number divides n, it would be added to the list.

The first divisor found would be n, and the last would be 1. Therefore, the list would be in decreasing order.
Answer: The checking order would be reversed, so the divisor list would be in decreasing order.
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?
If we start from min(m,n) and move backwards, the first number that divides both m and n is automatically the greatest common divisor.

Therefore, once we find such a number, we can stop immediately.
Answer: We can stop at the first common divisor found because it will be the GCD.
11.3.2 Analysing These Algorithms
We can analyse an algorithm in two important ways:
  • Correctness: Does it always give the right answer?
  • Efficiency: How much work does it require?
The first GCD algorithm may require checking many numbers. If the input numbers become much larger, the amount of work can increase greatly.

This motivates us to look for faster algorithms.
11.3.3 Euclid’s Subtraction Algorithm
Euclid’s algorithm uses the important fact:
If m > n, then GCD(m,n) = GCD(n,m−n)
Why does this work?

Suppose d divides both m and n. Then d also divides their difference m−n.

Conversely, if d divides n and m−n, then d also divides n + (m−n) = m.

Therefore, the common divisors remain the same.
Euclid’s Algorithm for GCD(m,n)
  1. If m < n, reverse the numbers and compute GCD(n,m).
  2. If n = 0, report m as the answer.
  3. Otherwise, reduce the problem to GCD(n,m−n).
  4. Repeat the process.
Stopping condition:
When we reach GCD(m,0), the answer is m.
Example: GCD(375, 825)
375 < 825, so reverse:
GCD(825,375)

825 − 375 = 450
GCD(375,450)

375 < 450, so reverse:
GCD(450,375)

450 − 375 = 75
GCD(375,75)

375 − 75 = 300
GCD(75,300)

300 − 75 = 225
GCD(75,225)

225 − 75 = 150
GCD(75,150)

150 − 75 = 75
GCD(75,75)

75 − 75 = 0
GCD(75,0)
GCD(375,825) = 75
Understanding the Subtraction Algorithm
Consider gcd(99, 2). Explain why the subtraction version of Euclid’s algorithm requires many steps.
Starting with GCD(99,2), we repeatedly subtract 2:

GCD(99,2)
GCD(97,2)
GCD(95,2)
GCD(93,2)
…
GCD(3,2)
GCD(2,1)
GCD(1,1)
GCD(1,0)

There are many subtraction steps because the larger number is reduced by only 2 each time.
Answer: The algorithm is slow for numbers such as 99 and 2 because many repeated subtractions are needed.
11.3.4 Aryabhata’s Division Algorithm
Instead of repeatedly subtracting the smaller number, we can use division and the remainder.

The key idea is:
GCD(m,n) = GCD(n, m mod n)
What does m mod n mean?

It means the remainder obtained when m is divided by n.

Examples:
17 mod 5 = 2
33 mod 7 = 5
Improved Euclidean Algorithm
  1. If m < n, reverse the numbers and compute GCD(n,m).
  2. If n = 0, report m.
  3. Otherwise, reduce the problem to GCD(n,m mod n).
  4. Repeat.
Example: GCD(99,2)

99 mod 2 = 1
So:
GCD(99,2) = GCD(2,1)

2 mod 1 = 0
So:
GCD(2,1) = GCD(1,0)

Therefore:
GCD(99,2) = 1
Only two reduction steps are needed.
GCD Using Long Division
Example 1: GCD(99,2)

99 = 2 × 49 + 1
2 = 1 × 2 + 0

Therefore:
GCD(99,2) = 1
Example 2: GCD(825,375)

825 = 375 × 2 + 75
375 = 75 × 5 + 0

Therefore:
GCD(825,375) = 75
Example 3: GCD(60,16)

60 = 16 × 3 + 12
16 = 12 × 1 + 4
12 = 4 × 3 + 0

Therefore:
GCD(60,16) = 4
A Pinch of History
Al-Khwarizmi was an influential Persian mathematician who studied Indian mathematics and the Indian place-value system.

His work helped spread Indian methods of arithmetic through medieval Europe. The word algorithm is historically connected with the Latin form of his name, Algoritmi.
Aryabhata was an important Indian mathematician and astronomer. The chapter connects the efficient division-based GCD method with Indian mathematical traditions and the use of long division.
Today, the word algorithm has a much broader meaning. It refers to a well-defined, step-by-step procedure for solving a problem.
Exercise – Improved Euclid’s Algorithm
END OF CHAPTER EXERCISES
1. Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375,825)
825 = 375 × 2 + 75
375 = 75 × 5 + 0

The last non-zero remainder is 75.
Answer: gcd(375,825) = 75
(ii) gcd(51000,81000)
81000 = 51000 × 1 + 30000
51000 = 30000 × 1 + 21000
30000 = 21000 × 1 + 9000
21000 = 9000 × 2 + 3000
9000 = 3000 × 3 + 0

The last non-zero remainder is 3000.
Answer: gcd(51000,81000) = 3000
(iii) gcd(1789287,237686)
1789287 = 237686 × 7 + 124485
237686 = 124485 × 1 + 113201
124485 = 113201 × 1 + 11284
113201 = 11284 × 10 + 300?

Continuing the division process eventually gives a last non-zero remainder of 1.

Therefore:
gcd(1789287,237686) = 1
Answer: 1
(iv) gcd(2587392,157656)
Applying the division algorithm:

2587392 = 157656 × 16 + 668?

Continuing with the Euclidean division process gives the last non-zero remainder as 24.

Therefore:
gcd(2587392,157656) = 24
Answer: 24
2. Assume that m > n. Verify that d divides m and n if and only if d divides both n and m mod n.
By the division algorithm:
m = qn + r
where r = m mod n.

If d divides m and n, then d divides qn and m. Therefore d also divides their difference:
m − qn = r
So d divides n and r.

Conversely, if d divides n and r, then d divides qn and r. Therefore:
qn + r = m
so d divides m.

Therefore the two conditions are equivalent.
Answer: d divides m and n exactly when d divides n and m mod n.
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(n) to write out prime(n)?
First compute the divisors of n.

A prime number has exactly two divisors: 1 and itself.

Algorithm prime(n):
  1. Compute divisors(n).
  2. If the list contains exactly two elements, report that n is prime.
  3. Otherwise, report that n is not prime.
Answer: A number is prime if and only if its divisor list contains exactly two elements.
*4. Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
Hint: Compute divisors(n) and then filter out the primes in this list.
Algorithm primedivisors(n):
  1. Compute divisors(n).
  2. Start with an empty list called prime-divisors.
  3. Take each divisor d from divisors(n).
  4. Check whether d is prime.
  5. If d is prime, add d to prime-divisors.
  6. Report prime-divisors.
Example:
n = 18
Divisors = [1,2,3,6,9,18]
Prime divisors = [2,3]
Answer: Filter the divisor list by keeping only prime numbers.
*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.
One simple algorithm is:
  1. Start with the smallest prime number, 2.
  2. Check whether the number is divisible by 2.
  3. If it is divisible, record 2 and divide the number by 2.
  4. Continue dividing by 2 while possible.
  5. Move to the next prime number.
  6. Continue until the remaining number is 1.
  7. The recorded prime factors give the prime factorisation.
Answer: Repeatedly divide the number by prime numbers and record each prime factor until the remaining number becomes 1.
(i) The prime factorisation of 180 is 2² × 3² × 5. How would you represent this?
We can represent the prime factorisation as a list containing each prime factor as many times as it occurs:
[2, 2, 3, 3, 5]
Or we can store the primes together with their powers:
2² × 3² × 5¹
Answer: [2, 2, 3, 3, 5] or {2:2, 3:2, 5:1}.
(ii) How would you compare the prime factorisations of two numbers?
Write both prime factorisations using the same prime numbers.

For example:
60 = 2² × 3 × 5
90 = 2 × 3² × 5
For the GCD, take the common prime factors with the smaller powers:
GCD(60,90) = 2 × 3 × 5 = 30
Answer: Compare the powers of the common prime factors. For GCD, use the smaller power of each common prime.
Important Concepts to Remember
1. Algorithm
A systematic, step-by-step procedure for solving a problem.
2. Basic Step
An operation that we assume we already know how to perform.
3. Data Structure
A method of organising information, such as a list.
4. GCD
The greatest number that divides both given numbers exactly.
5. Remainder
When one number is divided by another, the amount left over is called the remainder.
6. Euclid’s Algorithm
It repeatedly replaces GCD(m,n) with GCD(n,m mod n) until the remainder becomes zero.
7. Prime Number
A prime number has exactly two distinct positive divisors: 1 and itself.
8. Efficiency
Efficiency tells us how much work an algorithm needs to perform.
Chapter Summary
  • An algorithm is a systematic procedure used to solve a problem.
  • Algorithms consist of basic steps that we know how to execute.
  • The same step may be repeated several times.
  • Some steps may depend on a condition.
  • An algorithm should be justified to show that it gives the correct answer.
  • Data structures help us organise information used by an algorithm.
  • A list is one example of a data structure.
  • The GCD of two numbers is their greatest common divisor.
  • The basic divisor algorithm checks possible divisors systematically.
  • Algorithms can be improved to reduce the amount of work.
  • Euclid’s subtraction algorithm uses repeated subtraction.
  • The improved division algorithm uses remainders.
  • The key relation is:
    GCD(m,n) = GCD(n,m mod n)
  • The algorithm stops when the second number becomes 0.
  • The last non-zero remainder is the GCD.
  • Prime factorisation can also be used to find GCD.
  • The word “algorithm” has a historical connection with Al-Khwarizmi and the Indian arithmetic methods that influenced his work.
Quick Revision Formula:
If m = qn + r, then m mod n = r
GCD(m,n) = GCD(n,m mod n)
If n = 0, GCD(m,n) = m
Remember: In Euclid’s division algorithm, the last non-zero remainder is the GCD.

prepare more with the given Worksheet of chapter 11, which will help you to improve your knowledge .

Class 9 Maths Part 2 Chapter 11, Class 9 Maths Chapter 11 Notes, Class 9 Ganita Manjari Chapter 11, The World of Algorithms, Class 9 Maths Chapter 11 Book Solutions, The World of Algorithms Notes and Solutions, Class 9 Ganita Manjari Notes, Class 9 Ganita Manjari Book Solutions, NCERT Class 9 Maths, NCERT Class 9 Mathematics Part 2, CBSE Class 9 Maths, Class 9 Maths Questions and Answers, Class 9 Maths Study Material, Class 9 Maths Revision Notes, Class 9 Ganita Manjari Chapter-wise Solutions