Q1. What is an algorithm?
Answer:
An algorithm is a systematic, step-by-step procedure used to solve a problem and arrive at an answer. Each step should be described as precisely as possible.
Q2. What is the main advantage of using an algorithm for addition?
Answer:
An algorithm makes addition much faster than counting objects individually. It allows us to add numbers by working with their digits, starting from the rightmost column.
Q3. Why are digits aligned from right to left when adding numbers?
Answer:
Digits are aligned from right to left so that units, tens, hundreds, and other place values fall into their correct columns. This ensures that digits with the same place value are added together.
Q4. What is a carry in the addition algorithm?
Answer:
A carry is the value transferred to the next column on the left when the sum of digits in a column is 10 or more. It is included while adding the digits in the next column.
Q5. What is meant by executing an algorithm?
Answer:
Executing an algorithm means carrying out its steps one by one in the specified order to obtain the result.
Q6. What are the divisors of a number?
Answer:
The divisors of a number are the numbers that divide it exactly, leaving no remainder. For example, the divisors of 18 are 1, 2, 3, 6, 9, and 18.
Q7. What is the greatest common divisor (GCD) of two numbers?
Answer:
The greatest common divisor (GCD), also called the highest common factor (HCF), is the largest number that divides both given numbers exactly.
Q8. What is a list in an algorithm?
Answer:
A list is a sequence of values arranged in a particular order. In the chapter, lists are used to store divisors and common divisors of numbers.
Q9. What is a data structure?
Answer:
A data structure is a way of organising information so that it can be used efficiently in an algorithm. A list of numbers arranged in ascending order is an example of a data structure.
Q10. Why is it important to justify an algorithm?
Answer:
It is important to justify an algorithm to show that the steps actually produce the correct result. We must explain why the method works, rather than simply assume that its answer is correct.
Q11. Explain the step-by-step algorithm for adding two numbers.
Answer:
The algorithm for adding two numbers follows these steps:
1. Write the numbers one below the other, aligning their digits from right to left.
2. Add the rightmost digits and write the result below them.
3. If the sum is 10 or more, write the units digit and carry 1 to the next column.
4. Continue adding each column from right to left, including any carry.
5. After adding all the columns, write any remaining carry to the left of the result.
This method provides a systematic and efficient way to add numbers.
Q12. Explain the algorithm for finding all the divisors of a number n.
Answer:
To find the divisors of a number n, first create an empty list called list-of-divisors. Then check every number j from 1 to n. If j divides n exactly, add j to the list. Continue this process until all numbers from 1 to n have been checked. The final list contains all the divisors in increasing order.
Q13. Find all the divisors of 18 using the method described in the chapter.
Answer:
We check every number from 1 to 18 to determine whether it divides 18 exactly.
- 1, 2, and 3 divide 18 exactly.
- 4 and 5 do not divide 18 exactly.
- 6 divides 18 exactly.
- 7 and 8 do not divide 18 exactly.
- 9 divides 18 exactly.
- Numbers from 10 to 17 do not divide 18 exactly.
- 18 divides itself exactly.
Therefore, the divisors of 18 are:
1,2,3,6,9,18
Q14. Explain the first algorithm for finding the GCD of two numbers.
Answer:
The first GCD algorithm uses the lists of divisors of both numbers.
1. Find all the divisors of the first number m.
2. Find all the divisors of the second number n.
3. Create an empty list of common divisors.
4. Check each divisor of m to see whether it also appears in the divisor list of n. Add the common divisors to the new list.
5. Since the list is in increasing order, its rightmost element is the GCD.
This algorithm finds the greatest common divisor by comparing the divisors of both numbers.
Q15. Find the GCD of 375 and 825 using the common-divisor method.
Answer:
The divisors of 375 are:
1,3,5,15,25,75,125,375
The divisors of 825 are:
1,3,5,11,15,25,33,55,75,165,275,825
The common divisors are:
1,3,5,15,25,75
The greatest number in this list is 75.
Therefore,
gcd(375, 825) = 75
Q16. How can the original GCD algorithm be improved by combining the scans?
Answer:
In the original algorithm, the divisors of m and n are found separately, requiring us to check m + n possible divisors. We can improve the method by checking each number j from 1 to max (m, n) only once. If j divides m, we add it to the divisor list of m. If it divides n, we add it to the divisor list of n. This reduces the number of possible divisors checked from m + n to max (m, n).
Q17. How can we find common divisors without creating separate lists of divisors?
Answer:
We can directly check the numbers from 1 to min(m,n), because a common divisor cannot be greater than the smaller of the two numbers. For each number, we check whether it divides both m and n. If it divides both exactly, it is a common divisor. This avoids creating separate lists of divisors before finding the common divisors.
Q18. Explain how the GCD algorithm can be improved by removing the list of common divisors.
Answer:
We do not need to store every common divisor because only the greatest one is required. We begin by setting most-recent-common-divisor to 1, since 1 always divides both numbers. Then we check each number k from 2 to min(m,n). Whenever k divides both numbers exactly, we update the stored value to k. Since the numbers are checked in increasing order, the final stored value is the GCD.
Q19. What is the main limitation of the basic GCD algorithms?
Answer:
The basic GCD algorithms examine every number up to the smaller of the two given numbers. As the numbers become larger, the number of steps increases considerably. For example, moving from a three-digit number to a four-digit number can require checking ten times as many values. Therefore, these algorithms become inefficient for very large numbers.
Q20. State and explain the main idea behind Euclid’s subtraction algorithm.
Answer:
The GCD remains unchanged when the smaller number is subtracted from the larger number and the problem is reduced to finding the GCD of the smaller number and the difference. This process is repeated until the second number becomes zero. At that point, the first number is the GCD.
Q21. Why does Euclid’s subtraction algorithm give the correct GCD?
Answer:
Every common divisor of m and n also divides m-n, because the difference of two multiples of the same number is also a multiple of that number. Conversely, any number that divides both n and m-n also divides m, because m=n+(m-n). Therefore, the common divisors remain unchanged, and the GCD is preserved at every step.
Q22. Write the steps of Euclid’s subtraction algorithm for finding the GCD of two numbers.
Answer:
Euclid’s subtraction algorithm follows these steps:
- If m<n, reverse the numbers and work with gcd(n,m).
- If n=0, report m as the answer.
- Otherwise, reduce the problem to gcd(n,m-n).
- Repeat the process until the second number becomes zero.
The first number at the stopping point is the required GCD.
Q23. What is the main difference between Euclid’s subtraction algorithm and Āryabhaṭa’s division algorithm?
Answer:
Euclid’s subtraction algorithm repeatedly subtracts the smaller number from the larger number. This can require many steps when the difference between the numbers is small. Āryabhaṭa’s division algorithm improves the method by using division and the remainder instead of repeated subtraction. It reduces the problem from gcd(m,n) to gcd(n,m bmod n),making the process more efficient.
Q24. Explain Āryabhaṭa’s division algorithm for finding the GCD.
Answer:
Āryabhaṭa’s division algorithm uses the remainder obtained when one number is divided by another.
1. If m<n, reverse the numbers.
2. If n=0, the GCD is m.
3. Otherwise, replace gcd(m,n) with gcd(n,m bmod n).
4. Repeat the process until the second number becomes zero.
This algorithm uses repeated division by remainders instead of repeated subtraction. It is more efficient and requires a number of reductions proportional to the number of digits in the numbers.
Q25. Explain the historical origin of the word “algorithm” as described in the chapter.
Answer:
The Persian mathematician Al-Khwārizmī (780–850 CE) studied Indian mathematics and wrote a treatise around 820 CE explaining the Indian place-value number system and arithmetic operations. A Latin translation of his work helped spread Indian arithmetic through medieval Europe. His name became associated with these methods, and the Latin form of his name, Algoritmi, gave rise to the word algorismus. Over time, this developed into the word “algorithm,” which now means a well-defined, step-by-step procedure for solving a class of problems.
Leave a Reply