NCERT Class 9 Ganita Manjari Part 2 Chapter 11 The World of Algorithms PDF Download

Chapter 11: The World of Algorithms

These days the word 'algorithm' pops up everywhere. What exactly is an algorithm? What does it have to do with mathematics?

11.1 Adding Numbers

We first learned to add numbers by counting the sum explicitly. To add 5 and 7, we would draw 5 dots to represent the number 5, then draw 7 more dots to represent the number 7, and finally count the dots, 12, to get the answer. Imagine adding large numbers this way, for instance 473 + 695!

Fortunately, we discovered a much faster way to add numbers. We wrote the numbers one below the other in the Indian number system, with the rightmost digit aligned. We then added each column from right to left, remembering to add a carry to the left if the total was equal to or more than 10.

[Figure: Addition of 473 + 695 shown in three stages with dots, and column addition with carries, See in your textbook]

11.1.1 Adding Numbers Digit by Digit

This is an example of an algorithm, a step-by-step procedure to arrive at an answer. We describe an algorithm by writing down the steps as precisely as possible. For instance, here is one way to describe our addition algorithm.

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 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 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.

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?
2. What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
3. Why is it important to align the columns from right to left?
4. In Step 3, why cannot the value of carry be more than 1?
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.

There is also an important assumption in this algorithm, namely, that we know how to add single digit numbers without counting them out. Typically, any algorithm is built using such basic steps that we assume we can perform directly.

The main advantage of this algorithm is that it is much faster than counting explicitly. For instance, if we move from adding 3-digit numbers to adding 4-digit numbers, we have 10 times as many dots to draw and count. On the other hand, if we add the digits right to left, as in the algorithm above, we only have to add 1 more column. Likewise, 5-digit numbers would generate 100 times as many dots as 3-digit numbers, but only 2 more columns to be added.

Teacher's Note

When you follow an algorithm, do exactly what it says - no shortcuts. In Exercise 1, if you try to skip ahead or use mental maths instead of following the written steps, you might get the right answer but you're missing the point. Algorithms teach you that precision matters and that a clear procedure works every time.

In concrete terms, suppose we can count one dot per second. To count the dots in 33 + 27 would take a minute, to count 334 + 272 would take about ten minutes, while 3347 + 2729 would take over one hour and forty minutes.

On the other hand, suppose we work slowly and carefully and take 15 seconds to add two single digit numbers with a carry. Adding 33 + 27 would take about half a minute, while 334 + 272 would take about 45 seconds, while 3347 + 2729 would take about one minute.

Whenever we provide an algorithm, we also have to justify why it works. Combining the dots and counting the sum is how addition is defined. Why does adding individual digits from right to left result in the sum of the two numbers? The key idea is that we are grouping each number into units, tens, hundreds, ... and adding each group separately. Whenever a smaller group, say units, generates a large group of ten, we carry over the newly formed ten to the tens group.

Think and Reflect

1. See if you can complete the argument about grouping by units, tens, hundreds, ... to justify why the addition algorithm works.
2. How would you modify the algorithm to add two decimal fractions?

In the rest of this chapter we will explore the idea of an algorithm in more detail and in some other contexts.

11.2 Greatest Common Divisor

Let us look at a familiar problem: computing the greatest common divisor (gcd) or highest common factor (hcf) of two numbers. We have already learned different ways to solve this problem, using prime factorisation and other methods.

How can we solve the problem from the definition of gcd? How do we write down an algorithm for this?

The first step is to understand what is required and break down the problem into smaller pieces that we know how to solve.

• We want the greatest common divisor of two numbers.
• For this, we need to first compute the divisors of both numbers and note them down.
• Once we have done this, we need to compare the two collections of divisors and find the largest number that is present in both collections.

Teacher's Note

Breaking a big problem into smaller steps is called decomposition, and it is the heart of all algorithm design. Notice that the three bullet points above each use an operation you already know how to do - finding divisors, noting them down, and comparing numbers. Never try to jump straight to the answer; instead, identify the simple tasks you can do and chain them together.

Key Points

• An algorithm is a step-by-step procedure written down precisely so that it can be followed exactly every time to solve a problem.
• The addition algorithm is much faster than counting dots because it breaks the problem into small steps that work on one column at a time, no matter how large the numbers are.
• Every algorithm must be justified by explaining why the step-by-step process produces the correct answer, not just that it works.
• To design an algorithm, first understand what you need to find, then break the problem down into smaller pieces that you already know how to do.

This is a preview of the first 3 pages. To get the complete chapter, click below.