The World of Algorithms | CBSE Class 9 Maths Notes

This note covers algorithms, addition by place value, divisor lists, greatest common divisors, data structures, improvements to a scanning procedure, Euclid’s subtraction algorithm, Āryabhaṭa’s division algorithm, correctness, efficiency, and the historical origin of the word algorithm.

What is an algorithm, and how do its steps solve a problem?

Definition: An algorithm is a precisely described, step-by-step procedure for solving a problem. Its instructions use basic operations that we already know how to perform.

An algorithm explains what to do and in what order. Executing an algorithm means carrying out its instructions step by step. A description must be precise enough for someone following it to know which action comes next, including when a condition changes that action.

How do repetition and conditions work?

A repeated step applies the same instruction several times. Checking possible divisors of a number involves repeating a divisibility check. A conditional step performs an action only when a stated requirement is satisfied, such as recording a number only when it divides another exactly.

The input is the information supplied to a procedure. Addition takes the two numbers to be added as its input. The output is the answer produced. The procedure needs to connect this starting information to its answer through instructions that can actually be carried out.

Correctness concerns whether the procedure gives the required answer. Efficiency concerns how much work it requires, which can be studied by counting steps as the input grows. A correct procedure can still require a great deal of work.

Why begin with simple operations?

To add 5 and 7, represent them by separate collections of dots, combine the collections, and count 12 dots. This follows the meaning of addition directly. However, drawing and counting dots becomes laborious for an addition such as 473 + 695. The symbol + means addition. The symbol = means “is equal to”; an equation is a statement that two quantities are equal.

A better procedure groups numbers into place values and works with their digits. This illustrates a recurring approach: begin with a method whose correctness is clear, examine the work it requires, and improve it while preserving the answer it computes.

How does the digit-by-digit addition algorithm work?

The Indian base-ten place-value system groups a number into units, tens, hundreds, and larger places. Each place represents ten times the place immediately to its right. Aligning whole numbers from the right places units under units, tens under tens, and hundreds under hundreds.

A carry records a group transferred into the next column on the left. When a column total reaches ten, retain its units digit in that column and carry one into the next place. Work from right to left so that each carry is available when needed.

1. Write the two whole numbers with matching place-value columns aligned.
2. Add the units digits. Write the units digit of the total below the column, and record whether a carry is needed.
3. Move one column left and add both digits together with the current carry.
4. Repeat for the remaining columns, recording a new carry after each addition.
5. If a carry of 1 remains after the leftmost column, write it to the left of the answer.

Worked example 1. Add 473 and 695 by place value.

Answer: The units give 3 + 5 = 8. The tens give 7 + 9 = 16, so write 6 and carry 1. The hundreds give 4 + 6 + 1 = 11, so write 1 and carry 1. The final sum is 1168.

What must a complete instruction cover?

Note: A column total equal to 10 also needs a carry: write 0 and carry 1. Instructions covering totals below 10 and above 10 leave this equality case unresolved.

If the whole numbers have different lengths, a missing digit in a higher column must be treated as zero. For decimal fractions, numbers with digits after a decimal point, align corresponding places by aligning the decimal points, rather than merely aligning the final digits.

The carry cannot exceed 1 when adding two numbers this way: two digits and an incoming carry total at most 9 + 9 + 1 = 19. Omitting the final carry would lose the new highest place in the worked addition.

Why is place-value addition correct and more efficient?

Property: Regrouping preserves the total

Place-value addition adds units to units, tens to tens, and so on. Transferring ten units into one ten does not change the quantity represented. The same reasoning applies when ten tens become one hundred. Thus, carrying reorganises the total without adding or removing any value.

The basic operation assumed here is the ability to add single-digit numbers without drawing and counting their dots. Typically, an algorithm relies on basic steps that we assume we can perform directly. Stating this assumption helps explain what work the procedure is actually replacing.

How do the two methods compare?

Suppose counting takes one second per dot. Suppose instead that adding two digits with a carry takes 15 seconds. These assumptions allow the time needed for the two methods to be compared. They are conditions of the comparison, rather than fixed speeds for every person.

The distinction is between the value of a number and the number of digits used to write it. Counting dots follows the quantity represented. Column addition follows the written places, with one extra column to process when another digit is added.

In the comparison of three-digit, four-digit, and five-digit numbers, the dot-counting work grows by factors of ten and one hundred, while column addition gains only one or two columns. The benefit comes from changing the representation and the operations, while keeping the meaning of addition.

This suggests a question for other problems: can a method that examines many individual values be replaced by one that works with a much shorter description? Finding a greatest common divisor provides another setting in which to investigate this question.

How can an algorithm find all the divisors of a number?

A divisor, or factor, of a positive whole number is a positive whole number that divides it exactly, leaving no remainder. The remainder is the amount left after taking away whole multiples of the divisor. A remainder of zero means exact divisibility.

Let n be the positive whole number whose divisors are required, and let j be the possible divisor currently being checked. Each possible divisor lies between 1 and n, including both ends. Testing these candidates systematically gives a direct procedure.

How is the divisor list built?

A list is a sequence of values. Square brackets enclose its entries, and [ ] denotes an empty list. The name list-of-divisors identifies the list being built. The notation divisors(n) denotes the resulting list of divisors of n.

1. Start with list-of-divisors empty.
2. Check each value of j from 1 through n in increasing order.
3. If j divides n exactly, append it, meaning add it at the end of the list.
4. If j does not divide n, leave the list unchanged and continue checking.

Worked example 2. Execute the divisor-list procedure for 18.

Answer: The successful checks are 1, 2, 3, 6, 9, and 18. They build the list successively as [1], [1, 2], [1, 2, 3], [1, 2, 3, 6], [1, 2, 3, 6, 9], and [1, 2, 3, 6, 9, 18]. Other candidates leave the list unchanged.

For example, checking 4 and 5 leaves [1, 2, 3] unchanged. Checking 7 and 8 leaves [1, 2, 3, 6] unchanged. The final list is in increasing order, meaning each successive entry is larger, because the candidates were examined in that order.

This algorithm assumes that a divisibility test can be performed as a basic step. It also illustrates why names matter: j identifies the current candidate, while list-of-divisors identifies information that must remain available throughout the procedure.

How do divisor lists give the greatest common divisor?

A common divisor divides both numbers exactly. Their greatest common divisor, abbreviated gcd, is the largest such number. The same quantity is called the highest common factor, abbreviated hcf. Let m and n denote the two positive whole numbers; gcd(m, n) denotes their greatest common divisor.

Break the problem into smaller tasks: find the divisors of m, find the divisors of n, and identify the largest shared entry. This uses the divisor-finding procedure as a component of a larger algorithm, instead of developing every operation again.

1. Compute divisors(m), and name this list divisors-of-m.
2. Compute divisors(n), and name this list divisors-of-n.
3. Create an empty list named common-divisors.
4. For each entry x in divisors-of-m, check whether x also occurs in divisors-of-n. Here x means the entry currently being examined. Append it if it occurs in both.
5. Report the rightmost entry in common-divisors as gcd(m, n).

Worked example 3. Find gcd(375, 825) using the divisor lists below.

Answer: The shared entries are [1, 3, 5, 15, 25, 75]. The entries 125 and 375 from the first list do not occur in the second. The greatest shared entry is 75, so gcd(375, 825) = 75.

Property: The final shared entry is greatest

Because the first list is scanned in increasing order, the shared entries are also appended in increasing order. Therefore, its rightmost entry is the greatest common divisor. The list cannot be empty, because 1 divides every positive whole number.

The same procedure gives gcd(54000, 81000) = 27000. Long divisor lists make casual inspection difficult, so systematic comparison matters. The answer depends on both the divisibility checks and the order in which the accepted entries are recorded.

How do data structures help us improve the scanning algorithm?

A data structure organises information so that an algorithm can use it effectively. Lists are examples. The divisor lists contain intermediate values, meaning information computed along the way rather than just the final answer. These intermediate values are typically more complicated than single numbers.

Giving them names makes instructions concise and allows later steps to refer to earlier results. However, storing every intermediate list is not necessarily required. Examine what the answer needs, then remove work and stored information that do not contribute to that answer.

What can a combined scan remove?

The separate scans examine m + n candidate positions altogether. Define max(m, n) as the larger of the two numbers and min(m, n) as the smaller. One combined scan can examine each j from 1 through max(m, n), testing divisibility into both numbers.

This reduces the number of candidate values visited to max(m, n). It does not mean that a candidate needs just one divisibility test: divisibility into m and into n are separate checks. The two lists can also be replaced by one list containing only shared divisors.

Property: A common divisor cannot exceed the smaller number

Any common divisor must divide the smaller positive number, so it cannot be larger than that number. Consequently, scan only from 1 through min(m, n). Whenever a candidate divides both inputs, append it directly to the common-divisors list.

Finally, even that list can be removed. Use a single quantity named most-recent-common-divisor. Initialise it to 1, then check the candidates from 2 through min(m, n). Replace its value whenever a candidate divides both numbers.

Because the scan proceeds upwards, every replacement is a larger common divisor. At the end, the stored value is the largest one encountered. Each refinement preserves what is being computed while reducing scanning, comparison, or storage work in the original procedure.

How can we trace a scan and judge its remaining limitations?

Worked example 4. Use the single-value scan to find gcd(6, 12).

Answer: The smaller number is 6. Start most-recent-common-divisor at 1. Checking 2 changes it to 2; checking 3 changes it to 3. The candidates 4 and 5 do not divide 6, so it stays 3. Checking 6 changes it to 6. Thus gcd(6, 12) = 6.

A trace records the successive changes made while executing an algorithm. It must show unsuccessful checks as well as successful ones when explaining why the stored value changes or remains unchanged. The scan ends only after all required candidates have been considered.

Why does the order of checking matter?

If divisor lists are generated by checking downwards, their entries occur in decreasing order. A shared list built in that order has its greatest entry first. Similarly, a downward scan for common divisors can stop at its first successful check, because larger candidates have already been rejected.

The upward single-value scan remains limited by the smaller input’s value. Initialising at 1 avoids a separate test for that known common divisor, but the remaining values still need checking. Removing lists therefore does not remove the need for a potentially long sequence of tests.

Efficiency analysis asks how this work grows with the input. As in dot counting, moving from three-digit to four-digit values gives the scale comparison of ten times as much scanning, and moving to five digits gives a factor of one hundred.

A stronger improvement needs a different idea: replace the original gcd problem with another involving smaller numbers, while proving that both problems have exactly the same common divisors. That is the central idea behind the subtraction method.

Why does Euclid’s subtraction algorithm preserve the gcd?

Assume m ≥ n, where ≥ means “greater than or equal to”. The key result is gcd(m, n) = gcd(n, m − n). Here the minus sign indicates subtraction. Replacing the pair in this way preserves its common divisors.

How is the result justified in both directions?

Let d be a positive common divisor of m and n. Write m = ad and n = bd, where a and b are the whole-number multipliers expressing the two numbers as multiples of d. Then m − n = (a − b)d, so d divides the difference.

Conversely, suppose d divides n and m − n. Write n = xd and m − n = yd, where x and y are the corresponding whole-number multipliers. Adding gives m = (x + y)d. Hence d divides m as well as n.

Both directions are necessary: they show that the two pairs have the same set of common divisors, rather than merely sharing some divisors. Their greatest common divisor must therefore also be the same.

Two horizontal bars are partitioned into blocks labelled d. The upper bar is marked m. Beneath the lower bar, a dashed vertical division separates lengths labelled n and m − n. The blocks show how the same divisor measures these lengths.

See Fig. 11.1 in your NCERT textbook

How does the algorithm stop?

If m is smaller than n, exchange the two inputs. If n = 0, report m. Otherwise, replace the pair by n and m − n and repeat. The sign <, used to write m < n, means “less than”.

Worked example 5. Apply subtraction to 375 and 825, exchanging their order whenever needed.

Answer: In larger-first order, the successive pairs are (825, 375), (450, 375), (375, 75), (300, 75), (225, 75), (150, 75), (75, 75), and (75, 0). Seven subtractions lead to the answer 75. Parentheses here group the two current inputs.

The stopping rule is gcd(m, 0) = m for positive m. For instance, reducing gcd(23, 23) gives gcd(23, 0), whose answer is 23. This rule supplies a definite endpoint instead of continuing to subtract after zero appears.

How does the remainder method improve on repeated subtraction?

Repeated subtraction is not yet the desired improvement in every case. Starting with 99 and 2 repeatedly removes 2, passing through 97, 95, 93, and further smaller values. The procedure eventually reaches pairs (2, 1), (1, 1), and (1, 0), giving the answer 1.

More generally, let k be a positive whole number. The expression 2k + 1 represents an odd number, meaning a whole number not divisible by 2. Subtraction for gcd(2k + 1, 2) requires about k reductions, so its work follows the number’s value rather than its digit count.

What does the notation mod mean?

The expression m mod n means the remainder when m is divided by positive n. Repeatedly subtracting n until the remaining value is smaller than n produces this same remainder. A division can therefore replace many subtraction steps.

Worked example 6. Find 17 mod 5 and 33 mod 7.

Answer: Since 17 = 3 × 5 + 2, its remainder on division by 5 is 2. Since 33 = 4 × 7 + 5, its remainder on division by 7 is 5. The symbol × means multiplication.

The improved reduction is gcd(m, n) = gcd(n, m mod n). The stopping rule is unchanged: if the second input is zero, report the first. Test for zero before attempting division, because the remainder operation requires a non-zero divisor.

Worked example 7. Find gcd(99, 2) by the remainder method.

Answer: Dividing 99 by 2 leaves 1, so reduce to gcd(2, 1). Dividing 2 by 1 leaves 0, so reduce to gcd(1, 0). Report 1. Only two reductions are needed.

The same two-reduction pattern works for gcd(2k + 1, 2): an odd number leaves remainder 1 on division by 2, and division by 1 then leaves zero. This gives a direct comparison with the much longer subtraction procedure on the same form of input.

How do long division, justification, and history connect these algorithms?

Āryabhaṭa’s division algorithm uses successive divisions with remainders. Indian treatises such as the Āryabhaṭīya of 499 CE describe the long-division method for finding the gcd using Indian place-value numerals. CE means Common Era, the dating system used here.

How are successive divisions recorded?

Worked example 8. Find gcd(825, 375) by division.

Answer: Write 825 = 2 × 375 + 75, then 375 = 5 × 75 + 0. These divisions reduce the problem to gcd(375, 75), then gcd(75, 0). The answer is 75.

Worked example 9. Find gcd(60, 16) by division.

Answer: Write 60 = 3 × 16 + 12, then 16 = 1 × 12 + 4, then 12 = 3 × 4 + 0. The successive problems are gcd(16, 12), gcd(12, 4), and gcd(4, 0). The answer is 4.

Three worked layouts show the divisions for the pairs 99 and 2, 825 and 375, and 60 and 16. Each links a non-zero remainder to the next division. Arrows labelled gcd identify the final divisors 1, 75, and 4.

Reference: NCERT Class 9, page 49

Why does division preserve the answer?

Write m = qn + r, where q is the quotient, the number of whole copies of n in m, and r is the remainder. A divisor of both m and n divides r = m − qn. A divisor of n and r divides m = qn + r.

Thus the two pairs have the same common divisors. It can be shown that the number of reductions is proportional to the number of digits in m and n. Here proportional describes how the required reductions grow in relation to the input’s digit count.

Where did the word algorithm come from?

Euclid recorded the subtraction method in Elements. Historians believe that other Greek mathematicians knew it before him, but he was the first to put it in writing. Keep the distinction between recording a method and being its first user.

The word algorithm comes through Latin forms of the name Al-Khwārizmī, whose account of Indian numerals and arithmetic helped spread those methods. The word’s meaning broadened from an Indian method of arithmetic to a systematic procedure for solving a class of problems.

Glossary

• Algorithm — A precisely described sequence of steps for solving a problem using operations that can be performed.
• Execution — Carrying out an algorithm’s instructions in their specified order, including repetitions and conditional actions.
• Input — The starting information supplied to an algorithm so that it can compute the required answer.
• Carry — A group transferred into the next higher place when a column total reaches ten.
• Divisor — A positive whole number that divides another positive whole number exactly, without leaving a remainder.
• Common divisor — A positive whole number that divides each of the two numbers being considered exactly.
• Greatest common divisor — The largest positive whole number that divides both given numbers, also called their highest common factor.
• List — A sequence of values whose entries can be examined and extended during an algorithm.
• Data structure — A way of organising information so that an algorithm can store and use it effectively.
• Intermediate value — Information computed during a procedure and kept available for use by its later steps.
• Remainder — The amount left after subtracting the largest possible whole multiple of a positive divisor.
• Quotient — The number of whole copies of the divisor removed from the number during division.
• Correctness — The requirement that an algorithm’s instructions lead to the answer the problem asks for.
• Efficiency — How much work an algorithm requires, considered through its steps as the input grows.
• Stopping condition — A specified situation in which the algorithm reports its answer instead of continuing its reductions.

Common errors and misconceptions

• Misconception: A column total of exactly 10 needs no carry. Correct: Write 0 in that column and carry 1 into the next place.
• Misconception: The final carry can be discarded. Correct: If 1 remains after the last column, it must become the answer’s new leftmost digit.
• Misconception: The rightmost common divisor is greatest regardless of list order. Correct: This conclusion depends on building the list in increasing order.
• Misconception: Combining scans makes each candidate require just one divisibility test. Correct: A combined scan still checks divisibility into each input as needed.
• Misconception: Removing divisor lists makes scanning depend only on the input’s digit count. Correct: The upward scan still examines candidates through the smaller number’s value.
• Misconception: Subtraction always needs few reductions. Correct: For an odd number 2k + 1 paired with 2, it needs about k reductions.
• Misconception: The zero remainder is the gcd. Correct: When the second input becomes zero, the first input is the gcd.
• Misconception: A proof in one direction establishes the gcd reduction. Correct: Show that each pair’s common divisors also divide both members of the other pair.

Exam-style questions with model answers

Q1. What is an algorithm, and what does it mean to execute one? [2 marks]

1. An algorithm is a precisely described, step-by-step procedure for solving a problem using basic operations.
2. To execute it is to carry out those instructions in order, following any repetitions and conditions specified.

Q2. Add 473 and 695 using place-value columns. Show the units, tens, hundreds, and final carry. [4 marks]

1. Align matching places. The units column gives 3 + 5 = 8, so write 8 in the units place without a carry.
2. The tens column gives 7 + 9 = 16. Write 6 in the tens place and carry 1.
3. The hundreds column gives 4 + 6 + 1 = 11. Write 1 in the hundreds place and carry 1.
4. Place the remaining carry at the left of the answer. Therefore, the sum is 1168.

Q3. Describe the divisor-list algorithm and use it to find every positive divisor of 18. Explain the order of the final list. [3 marks]

1. Start with an empty list. Check each positive whole number from 1 through 18, testing whether it divides 18 exactly.
2. Append a candidate only when the division leaves no remainder. The successful candidates produce [1, 2, 3, 6, 9, 18].
3. The list is in increasing order because candidates are examined from smallest to largest and each accepted candidate is added at the end.

Q4. The divisor lists of 375 and 825 are [1, 3, 5, 15, 25, 75, 125, 375] and [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. Explain the comparison algorithm, obtain the common-divisor list, and find the gcd. [5 marks]

1. Start with an empty list for common divisors. The supplied divisor lists are already arranged in increasing order, so their entries can be checked systematically.
2. Read each entry in the list for 375 and test whether that same entry appears in the supplied list for 825.
3. Append each successful entry to the common list. This gives [1, 3, 5, 15, 25, 75], in the order encountered.
4. Reject 125 and 375 because neither occurs in the second list. They divide the first input but are not common divisors.
5. The common list retains increasing order, so its rightmost entry is its greatest member. Therefore, the greatest common divisor of 375 and 825 is 75.

Q5. Find gcd(6, 12) by scanning from 2 through the smaller input, keeping only the most recent common divisor. Explain the initial value and each change. [4 marks]

1. Initialise the stored common divisor to 1, since 1 divides both numbers. The smaller input is 6, so check candidates through 6.
2. The candidate 2 divides both numbers, so update the stored value to 2. The candidate 3 also divides both, so update it to 3.
3. Neither 4 nor 5 divides 6. Consequently, neither can be a common divisor, and the stored value remains 3.
4. The candidate 6 divides both 6 and 12. Update to 6 and stop after this final candidate. Therefore gcd(6, 12) = 6.

Q6. For positive whole numbers m and n with m greater than n, prove that gcd(m, n) = gcd(n, m − n). Here gcd denotes greatest common divisor. [5 marks]

1. Let d be any positive common divisor of m and n. There are positive whole numbers a and b such that m = ad and n = bd.
2. Subtracting these expressions gives m − n = (a − b)d. Therefore d divides the difference as well as n, so it is common to the new pair.
3. Conversely, let d divide both n and m − n. Write n = xd and m − n = yd, where x and y are positive whole-number multipliers.
4. Adding gives m = n + (m − n) = (x + y)d. Hence d divides m as well as n, so it is common to the original pair.
5. The two directions establish identical sets of common divisors. Their greatest elements are consequently equal, giving gcd(m, n) = gcd(n, m − n).

Q7. Use successive divisions with remainders to find gcd(60, 16). Show all divisions and explain the stopping rule. [4 marks]

1. Divide 60 by 16: 60 = 3 × 16 + 12. The remainder is 12, so replace the original problem by gcd(16, 12).
2. Divide 16 by 12: 16 = 1 × 12 + 4. The remainder is 4, so continue with gcd(12, 4).
3. Divide 12 by 4: 12 = 3 × 4 + 0. The next pair is therefore 4 and 0.
4. The stopping rule reports the first number when the second is zero. Thus gcd(60, 16) = 4.

Q8. Compare subtraction and remainder reduction for gcd(99, 2). Show the remainder calculation and explain why it avoids many subtractions. [3 marks]

1. Subtraction repeatedly removes 2 from 99, passing through 97, 95, 93, and further smaller values before reaching the final gcd.
2. Division gives 99 = 49 × 2 + 1, so the remainder method moves directly to gcd(2, 1). Next, 2 = 2 × 1 + 0.
3. The final pair is 1 and 0, so the answer is 1. Only two reductions are needed because division combines repeated subtractions into one remainder calculation.

Key takeaways

• An algorithm needs precise instructions, executable basic steps, and a justification that its procedure computes the required answer.
• Column addition groups quantities by place value, and carrying transfers groups of ten without changing the total represented.
• Checking possible divisors in increasing order produces an increasing list, making the final common entry the greatest.
• Names and data structures keep intermediate information available, but improving an algorithm can remove lists that the answer does not require.
• A common divisor cannot exceed the smaller positive input, which limits the candidates required by a direct scan.
• Euclid’s subtraction reduction preserves the complete set of common divisors, but repeated subtraction can still take many steps.
• The remainder method replaces many subtractions with division and stops when the second input becomes zero.
• To compare efficiency meaningfully, distinguish the numerical value of an input from the number of digits used to represent it.

Test yourself

Why should whole-number addition align matching place-value columns?

It ensures units are added to units, tens to tens, and corresponding larger places to one another.

What should happen when an addition column totals exactly 10?

Write 0 in that column and carry 1 into the next column on the left.

What list results from checking every positive divisor of 18?

The final divisor list is [1, 2, 3, 6, 9, 18], arranged in increasing order.

Why is a list of common divisors of two positive whole numbers non-empty?

The number 1 divides every positive whole number, so it belongs to both divisor lists.

How can a gcd scan avoid storing a list of all common divisors?

Start a stored value at 1 and replace it whenever an upward scan finds a larger common divisor.

What does 33 mod 7 mean, and what is its value?

It means the remainder when 33 is divided by 7. Since 33 = 4 × 7 + 5, its value is 5.

What are the two remainder reductions starting from gcd(99, 2)?

Reduce first to gcd(2, 1), then to gcd(1, 0). The stopping rule reports the answer 1.

Why does reaching gcd(75, 0) give 75 rather than zero?

When the second input is zero, the gcd algorithm reports the first input, which is 75 here.