Important Questions Class 9 Maths Chapter 11 Algorithms

Important Questions Class 9 Maths Chapter 11 Algorithms

The World of Algorithms is Chapter 11 of the new Class 9 Maths textbook Ganita Manjari (Part 2). An algorithm is a list of clear steps that we follow to solve a problem. We already use algorithms when we add numbers column by column or find the HCF of two numbers. In this chapter, you learn to write such steps carefully, check that they work for every case, and make them faster.

This page has 12 important questions from Algorithms with simple, step-by-step answers prepared by Extramarks experts. The questions cover the column addition algorithm and the carry, the meaning of m mod n, Euclid’s algorithm for the gcd (HCF), checking whether a number is prime, finding divisors in pairs, finding the LCM, and comparing two sorted lists. Try writing the steps yourself before you read each answer.

Q1. What is an algorithm? Write any three qualities of a good algorithm.

Answer: An algorithm is a finite list of clear, step-by-step instructions that takes an input and gives the correct output for a problem. For example, the steps we follow to add two numbers column by column form an algorithm.

Qualities of a good algorithm:

1. Every step is clear and exact, so there is no confusion about what to do next.

2. It stops after a finite number of steps.

3. It gives the correct answer for every valid input, not just for a few examples.

Q2. Write the algorithm for adding two numbers column by column. Use it to add 4785 and 3648.

Answer: Algorithm:

Step 1: Write the two numbers one below the other so that the digits line up from the right (ones under ones, tens under tens, and so on). Set carry = 0.

Step 2: Start with the rightmost column.

Step 3: Add the two digits in the column and the carry. If a number has no digit in that column, take its digit as 0.

Step 4: If the sum is 10 or more, write the ones digit of the sum below the column and set carry = 1. Otherwise, write the sum and set carry = 0.

Step 5: Move one column to the left and repeat Steps 3 and 4 until all columns are added.

Step 6: If the carry is 1 at the end, write 1 at the extreme left.

Adding 4785 and 3648:

So, 4785 + 3648 = 8433.

Q3. In the column addition algorithm, why must we line up the numbers from the right? Why can the carry never be more than 1 when we add two numbers?

Answer: We line up the numbers from the right so that digits with the same place value are added together: ones with ones, tens with tens, and so on. Numbers can have different lengths, but they always end at the ones place on the right.

The largest digit is 9. So the largest sum in any column is 9 + 9 + 1 (carry) = 19. Since 19 is less than 20, the carry to the next column can be at most 1.

Q4. What goes wrong if we leave out the last step (writing the final carry) of the addition algorithm? Does the algorithm also work when we add a 5-digit number and a 3-digit number?

Answer: Without the last step, the final carry is lost and the answer is wrong. Example: 785 + 648. The columns give 3 (carry 1), 3 (carry 1) and 4 (carry 1). If we stop there, we get 433, but the correct answer is 1433. The last step writes the final carry 1 on the left.

Yes, the algorithm works for numbers of different lengths, because in Step 3 a missing digit is taken as 0. Example: 52316 + 845 = 53161.

Q5. What does m mod n mean? Find (i) 47 mod 5 (ii) 100 mod 7 (iii) 36 mod 9.

Answer: m mod n is the remainder when m is divided by n.

(i) 47 = 5 × 9 + 2, so 47 mod 5 = 2.

(ii) 100 = 7 × 14 + 2, so 100 mod 7 = 2.

(iii) 36 = 9 × 4 + 0, so 36 mod 9 = 0. A remainder of 0 means 9 divides 36 exactly.

Q6. Write the improved version of Euclid’s algorithm to find gcd(m, n), where m ≥ n. Use it to find gcd(252, 105).

Answer: Algorithm:

Step 1: If n = 0, the answer is m. Stop.

Step 2: Otherwise, find r = m mod n.

Step 3: Replace the pair (m, n) by (n, r) and go back to Step 1.

Finding gcd(252, 105):

So, gcd(252, 105) = 21. (Check: 252 = 21 × 12 and 105 = 21 × 5.)

Q7. Find gcd(84, 36) using Euclid’s original method of repeated subtraction. Then find it using the mod version and explain why the mod version is faster.

Answer: Repeated subtraction: keep replacing the larger number by (larger – smaller).

(84, 36) → (48, 36) → (12, 36) → (12, 24) → (12, 12) → (12, 0). So, gcd(84, 36) = 12.

Mod version: 84 mod 36 = 12, so (84, 36) → (36, 12). Then 36 mod 12 = 0, so (36, 12) → (12, 0). Again, gcd = 12.

The mod version is faster because one mod step does many subtractions at once. Here, subtracting 36 from 84 two times is done in a single step: 84 mod 36 = 12. For large numbers, this saves a lot of steps.

Q8. Assume m ≥ n and let r = m mod n. Show that a number d divides both m and n if and only if d divides both n and r. Why does this prove that Euclid’s algorithm gives the gcd?

Answer: When m is divided by n, we get m = qn + r, where q is the quotient and r is the remainder.

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

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

So the pairs (m, n) and (n, r) have exactly the same common divisors, and therefore the same greatest common divisor. Each step of Euclid’s algorithm replaces (m, n) by (n, r) without changing the gcd. The numbers keep getting smaller, so the remainder finally becomes 0, and gcd(g, 0) = g. Hence the last non-zero number is the gcd.

Q9. Write an algorithm prime(n) to check whether a number n (n ≥ 2) is prime. Explain why we only need to check divisors up to √n. Use it to check 97 and 91.

Answer: Algorithm prime(n):

Step 1: Start with d = 2.

Step 2: While d × d ≤ n: if n mod d = 0, output “n is not prime” and stop; otherwise increase d by 1.

Step 3: If no such d is found, output “n is prime”.

Why up to √n: divisors come in pairs (d, n ÷ d). In every pair, one number is at most √n. So if n has a divisor other than 1 and n, it must have one that is at most √n.

Check 97: √97 is a little less than 10, so we check d = 2 to 9. 97 mod 2 = 1, mod 3 = 1, mod 4 = 1, mod 5 = 2, mod 6 = 1, mod 7 = 6, mod 8 = 1, mod 9 = 7. No remainder is 0, so 97 is prime.

Check 91: 91 mod 2 = 1, mod 3 = 1, mod 4 = 3, mod 5 = 1, mod 6 = 1, mod 7 = 0. So 91 is not prime (91 = 7 × 13).

Q10. Divisors occur in pairs. Find all the divisors of 36 by checking numbers only from 1 to 6. Why does 36 have an odd number of divisors?

Answer: Check each number d from 1 to 6 (because 6 × 6 = 36). If d divides 36, we also get its partner 36 ÷ d.

1 → (1, 36); 2 → (2, 18); 3 → (3, 12); 4 → (4, 9); 5 does not divide 36; 6 → (6, 6).

So the divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36. That is 9 divisors.

The number of divisors is odd because 36 is a perfect square: in the pair (6, 6), the divisor 6 pairs with itself and is counted only once.

Q11. Describe an algorithm to find the least common multiple (LCM) of two numbers. Use it to find lcm(12, 18).

Answer: Method 1 (checking multiples):

Step 1: Let k be the larger number.

Step 2: If k is divisible by the smaller number, output k and stop.

Step 3: Otherwise, add the larger number to k and go back to Step 2.

For 12 and 18: k = 18 (18 mod 12 = 6, not 0) → k = 36 (36 mod 12 = 0). So lcm(12, 18) = 36.

Method 2 (using the gcd): lcm(m, n) = (m × n) ÷ gcd(m, n). Here gcd(12, 18) = 6, so lcm(12, 18) = (12 × 18) ÷ 6 = 216 ÷ 6 = 36.

Q12. List 1 = 2, 5, 8, 11, 14 and List 2 = 3, 5, 9, 11, 15 are both in increasing order. Write an algorithm to find the numbers of List 1 that are not present in List 2, and apply it.

Answer: Algorithm: Place a pointer i at the first number of List 1 and a pointer j at the first number of List 2. Repeat until i goes past the end of List 1:

1. If j has gone past the end of List 2, or the number at i is smaller than the number at j, then the number at i is not in List 2. Write it down and move i one place forward.

2. If the number at i equals the number at j, it is in both lists. Move both i and j one place forward.

3. If the number at i is greater than the number at j, move j one place forward.

Applying the algorithm:

The numbers in List 1 that are not in List 2 are 2, 8 and 14. Because both lists are in increasing order, each list is read only once, which makes the algorithm fast.

Related Study Material on Extramarks

• Important Questions for Class 9 Maths Chapter 1 The Use of Coordinates
• Important Questions for Class 9 Maths Chapter 2 Introduction to Linear Polynomials
• Important Questions for Class 9 Maths Chapter 3 The World of Numbers
• Important Questions for Class 9 Maths Chapter 4 Exploring Algebraic Identities
• Important Questions for Class 9 Maths Chapter 5 I'm Up and Down, and Round and Round
• Important Questions for Class 9 Maths Chapter 6 Measuring Space: Perimeter and Area
• Important Questions for Class 9 Maths Chapter 7 Introduction to Probability
• Important Questions for Class 9 Maths Chapter 8 Sequences and Progressions
• Important Questions for Class 9 Maths Chapter 9 Propositions
• Important Questions for Class 9 Maths Chapter 10 Data
• Important Questions for Class 9 Maths Chapter 12 Quadrilaterals
• Important Questions for Class 9 Maths Chapter 13 Two Variables, One Line
• Important Questions for Class 9 Maths Chapter 14 Math of Space: Surface Area and Volume