Experts have designed these Class 9 Maths Notes and Chapter 11 The World of Algorithms Class 9 Ganita Manjari Notes for effective learning.
Class 9 Maths Chapter 11 The World of Algorithms Notes
Class 9 Maths Ganita Manjari Chapter 11 Notes
Ganita Manjari Class 9 Chapter 11 Notes – Class 9 The World of Algorithms Notes
An algorithm is a systematic, step-by-step procedure used to solve a problem.
- Algorithms are made up of basic instructions that can be performed directly.
- The addition algorithm works by arranging numbers in columns according to their place values and adding digits from right to left while carrying when required. Repeat the process until there are no more digits left.
- Some steps in an algorithm may be repeated, while others may be performed only when a particular condition is satisfied.
- Running through an algorithm step by step is called executing the algorithm.
- The divisors of a number can be found by checking every number from 1 to the given number and recording those that divide it exactly.
- The greatest common divisor (gcd) or Highest Common Factor (HCF) of two numbers is the greatest number that divides both numbers exactly.
- Lists are examples of data structures. They help organise intermediate values, such as divisors and common divisors, while executing an algorithm.
- A basic gcd algorithm finds the divisors of both numbers, prepares a list of common divisors and reports the greatest one.
- The gcd algorithm can be improved by checking only the numbers up to the smaller of the two given numbers and keeping track of the greatest common divisor found.
- A common divisor cannot be larger than the smaller of two numbers.
- Euclid’s subtraction algorithm repeatedly replaces the greater number with the difference between the two numbers.
- Aryabhata’s division algorithm improves this method by replacing repeated subtraction with division and using the remainder.
- In the division algorithm, the gcd of ‘m’ and ‘n’ is the same as the gcd of and the remainder obtained when ‘m’ is divided by ‘n’
- An algorithm must be justified to show that it produces the correct result.
- Algorithms can also be analysed according to the number of steps they require. An algorithm that uses fewer steps is considered more efficient.
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.
- 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 10 or 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 10 or 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.
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:
If j divides n, add j to the list-of-divisors.
Greatest Common Divisor (GCD)
Finding divisors of a number using a systematic algorithm.
Creating lists of divisors and comparing them to find common divisors.
Finding the Greatest Common Divisor
- Comparing divisor lists of two numbers.
- Identifying common divisors.
- Selecting the greatest common divisor from the list of common divisors.
- Understanding the need for systematic methods instead of manual checking.
Algorithm to find gcd(m, n)
1. Let divisors-of-w be the list obtained by computing divisors(m) in increasing order.
2. Let divisors-of-w be the list obtained by computing divisors(w) in increasing order.
3. Start with an empty list common-divisors.
4. For each number x in the list of divisors-of-w: If x also appears in the list of divisors-of-w, add x to the list common-divisors.
5. Report the rightmost element of the list common-divisors as gcd(w, n).
Euclid’s Subtraction Algorithm
For a set of divisors (say m, n) where m> n, Euclid’s algorithm for gcd (m, n):
- If m < n, reverse the numbers and complete gcd (n, m)
- If n = 0, report the answer as m
- Otherwise, reduce the problem to compute gcd (n, m – n)
Aryabhata’s Division Algorithm
For a set of divisors (say m, n) where m > n, Aryabhata’s division algorithm for gcd (m, n):
- If m < n, reverse the numbers and complete gcd (n, m)
- If n = 0, report the answer as m
- Otherwise, reduce the problem to compute gcd (n, m mod n)
An algorithm is a systematic step-by-step procedure used to solve a problem.
For adding numbers:
Sum of digits + Carry from previous column = Result digit
If the sum is greater than 9: Carry = 1
A number d is a divisor of n, if: n ÷ d = a whole number
Euclid’s Subtraction Algorithm: For a pair of numbers (say m, n) where m > n, Euclid’s algorithm for gcd (m, n):
- If m < n, reverse the numbers and complete gcd (n, m)
- If n = 0, report the answer as m
- Otherwise, reduce the problem to compute gcd (n, m – n)
Aryabhata’s Division Algorithm: For a pair of numbers (say m, n) where m > n, Aryabhata’s division algorithm for gcd (m, n): - If m < n, reverse the numbers and complete gcd (n, m)
- If n = 0, report the answer as m
- Otherwise, reduce the problem to compute gcd (n, m mod n)
Common Errors:
| Errors | Corrections |
| (i) Starting addition from the leftmost digit | Addition should always begin from the rightmost digit because carrying moves towards higher place values. |
| (ii) Forgetting to include carry while adding the next column | Always add the carry value with the next column digits. |
| (iii) Writing incorrect divisors of a number | A divisor must divide the number exactly without leaving any remainder. |
| (iv) Confusing factors and multiples | Factors divide a number completely, whereas multiples are obtained by multiplying a number by integers. |
| (v) Incorrectly applying Euclid’s subtraction algorithm | Always subtract the smaller number from the larger number and continue until both numbers become equal. |
| (vi) Stopping Euclid’s algorithm before the remainder becomes zero | Continue the process until the remainder becomes 0. The last non-zero divisor is the gcd. |
| (vij) Interchanging quotient and remainder in Euclid’s division algorithm | Remember the correct relation: m = nq + r, where r must always be smaller than n. |
| (viii) Finding common divisors but not selecting the greatest one | The gcd is the largest divisor common to both numbers. |
| (ix) Ignoring the number of steps while comparing algorithms | Efficiency of an algorithm depends on the number of steps required to solve a problem. |
| (x) Confusing Euclid’s subtraction algorithm with Aryabhata’s division algorithm | Subtraction repeatedly reduces numbers by subtraction, while Aryabhata’s method uses division and remainder. |