Chapter-11 The World of Algorithms

Exercise Set 11.1

Question 1

Question: 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?

Solution:
Yes, following the addition algorithm step-by-step yields the correct result.

Example: Add 4587 and 3659.

Step 1: Align the digits by their place values (Units, Tens, Hundreds, Thousands).
Step 2: Add units column: 7 + 9 = 16. Write down 6 in the units place and carry over 1 to the tens place.
Step 3: Add tens column with carry: 8 + 5 + 1 = 14. Write down 4 in the tens place and carry over 1 to the hundreds place.
Step 4: Add hundreds column with carry: 5 + 6 + 1 = 12. Write down 2 in the hundreds place and carry over 1 to the thousands place.
Step 5: Add thousands column with carry: 4 + 3 + 1 = 8. Write down 8 in the thousands place.

Result: 4587 + 3659 = 8246. By executing each step as prescribed without skipping or assuming extraneous operations, we obtain the correct sum.

Question 2

Question: What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?

Solution:
Yes, the algorithm handles this situation correctly, provided we align the numbers by place values from right to left (units to units, tens to tens, etc.).

Explanation:

When adding a 5-digit number (e.g., 12345) and a 3-digit number (e.g., 678), the 3-digit number has implicit leading zeros in the thousands and ten-thousands places (00678).
The algorithm processes columns starting from the rightmost (units) column and moves leftward. Once the 3-digit number runs out of explicitly written digits, its higher place values are treated as 0.
Thus, the step-by-step addition correctly completes through all 5 digit positions.

Question 3

Question: Why is it important to align the columns from right to left?

Solution:
Aligning columns from right to left ensures that digits representing the same place value (units with units, tens with tens, hundreds with hundreds) are added together.

Reasoning:

Our positional numeral system (base-10) assigns values based on position relative to the units digit ($10^0, 10^1, 10^2$, etc.).
If alignment were done from left to right, a digit in the thousands place of one number might align with a digit in the hundreds or tens place of another, leading to incorrect addition across different power-of-10 weights.

Question 4

Question: In Step 3, why cannot the value of carry be more than 1?

Solution:
The value of carry cannot exceed 1 when adding two single decimal digits along with a maximum previous carry of 1.

Mathematical Proof:

The maximum single digit in base 10 is 9.
When adding two single digits plus a maximum possible carry of 1 from the preceding position: Maximum Sum = 9 + 9 + 1 = 19.
In 19, the units value written down is 9, and the tens value carried over to the next column is 1.
Since 19 is less than 20, the carry to the next column can never be 2 or greater.

Question 5

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

Solution:
The fifth step handles the final carry generated from the leftmost (most significant) column addition. If this step is omitted, any final carry value of 1 will be lost, resulting in an incorrect lower sum.

Example where the algorithm works correctly without Step 5:
Add 1234 and 2341. Sum of thousands digits: 1 + 2 = 3 (no carry generated). Result = 3575. Since no final carry is produced, omitting Step 5 does not affect the output.
Example where the algorithm FAILS to work without Step 5:
Add 6000 and 5000. Sum of thousands digits: 6 + 5 = 11. Without Step 5, we write 1 in the thousands place and drop the carry 1. The output would incorrectly be 1000 instead of 11000.

Exercise Set 11.2

Question 1

Question: Suppose List 1 and List 2 are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in List 1 that are not present in List 2.
(ii) Write an algorithm to find elements in List 2 that are not present in List 1.

Solution:

(i) Algorithm to find elements in List 1 not present in List 2:

Initialize two pointers, i = 0 (for List 1) and j = 0 (for List 2). Create an empty list Result.
While i < length(List 1) and j < length(List 2):
a. If List 1[i] == List 2[j]: Increment both i and j (i = i + 1, j = j + 1).
b. Else if List 1[i] < List 2[j]: Append List 1[i] to Result. Increment i (i = i + 1).
c. Else (List 1[i] > List 2[j]): Increment j (j = j + 1).
While i < length(List 1): Append List 1[i] to Result. Increment i (i = i + 1).
Return Result.

(ii) Algorithm to find elements in List 2 not present in List 1:

Initialize two pointers, i = 0 (for List 1) and j = 0 (for List 2). Create an empty list Result.
While i < length(List 1) and j < length(List 2):
a. If List 1[i] == List 2[j]: Increment both i and j (i = i + 1, j = j + 1).
b. Else if List 2[j] < List 1[i]: Append List 2[j] to Result. Increment j (j = j + 1).
c. Else (List 2[j] > List 1[i]): Increment i (i = i + 1).
While j < length(List 2): Append List 2[j] to Result. Increment j (j = j + 1).
Return Result.

Question 2

Question: Describe an algorithm to compute the least common multiple (lcm) of two numbers.

Solution:

Algorithm 1: Using Greatest Common Divisor (Euclidean Method)

Input two positive integers a and b.
Compute gcd(a, b) using Euclid’s algorithm:
- While b != 0: Set temp = b; Set b = a mod b; Set a = temp.
- The value of a is gcd(a, b).
Calculate LCM using the identity: LCM(a, b) = (a * b) / gcd(a, b).
Output LCM.

Algorithm 2: Direct Multiples Checking Method

Input two positive integers a and b.
Set max_val = max(a, b).
Set lcm = max_val.
While lcm mod a != 0 or lcm mod b != 0: lcm = lcm + max_val.
Return lcm.

Question 3

Question: Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
(i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n?
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?

Solution:

(i) Number of elements to examine:

We only need to examine numbers up to floor(sqrt(n)).
Reasoning: For any divisor d of n, n = d * k. If d > sqrt(n), then k < sqrt(n). Thus, every divisor greater than sqrt(n) is paired with a unique divisor smaller than sqrt(n).
Therefore, checking integers from 1 up to sqrt(n) is sufficient to generate all divisor pairs (d, n / d).

(ii) Applicability to GCD Algorithm:

Yes, the GCD algorithm will still work correctly.
Reasoning: By scanning up to sqrt(m) and sqrt(n), we can generate the complete set of divisors for both numbers by taking each pair (d, n/d). Once all divisors are obtained, finding the largest common divisor yields the exact same GCD.

Exercise Set 11.3

Question 1

Question: How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?

Solution:

Change in procedure: Instead of starting the loop at 1 and incrementing up to n, the loop starts at n and decrements down to 1.
Efficiency benefit: If the goal is to find the largest proper divisor or to find the GCD directly, iterating in reverse allows us to terminate as soon as the first common divisor is encountered, which is guaranteed to be the greatest.
Overall list output: If generating the full list of divisors, iterating from n down to 1 produces the divisors in descending order rather than ascending order.

Question 2

Question: What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?

Solution:

Operation: We set d = min(m, n) and check if d divides both m and n.
Key Advantage: The VERY FIRST value of d that divides both m and n is guaranteed to be the Greatest Common Divisor (GCD).
Termination: As soon as such a d is found, the algorithm can immediately stop and return d.
Comparison: This eliminates the need to collect all common divisors first and then search for the maximum among them, making it significantly faster in practice.

End-of-Chapter Exercises

Question 1

Question: Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375, 825)
(ii) gcd(51000, 81000)
(iii) gcd(1789287, 237656)
(iv) gcd(2587392, 157656)

Solution:

(i) gcd(375, 825):

Step 1: 825 mod 375 = 75 (825 = 375 * 2 + 75)
Step 2: 375 mod 75 = 0 (375 = 75 * 5 + 0)
gcd(375, 825) = 75.

(ii) gcd(51000, 81000):

Step 1: 81000 mod 51000 = 30000
Step 2: 51000 mod 30000 = 21000
Step 3: 30000 mod 21000 = 9000
Step 4: 21000 mod 9000 = 3000
Step 5: 9000 mod 3000 = 0
gcd(51000, 81000) = 3000.

(iii) gcd(1789287, 237656):

1789287 mod 237656 = 125695
237656 mod 125695 = 111961
125695 mod 111961 = 13734
111961 mod 13734 = 2089
13734 mod 2089 = 1200
2089 mod 1200 = 889
1200 mod 889 = 311
889 mod 311 = 267
311 mod 267 = 44
267 mod 44 = 3
44 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
gcd(1789287, 237656) = 1.

(iv) gcd(2587392, 157656):

2587392 mod 157656 = 64896
157656 mod 64896 = 27864
64896 mod 27864 = 9168
27864 mod 9168 = 360
9168 mod 360 = 168
360 mod 168 = 24
168 mod 24 = 0
gcd(2587392, 157656) = 24.

Question 2

Question: Assume that m >= n. Verify that d divides m and n if and only if d divides both n and m mod n.

Solution:
Proof: By Division Algorithm, m = q * n + r, where r = m mod n and 0 <= r < n.

Forward direction (=>): Suppose d divides both m and n. Then m = k1 * d and n = k2 * d. Since r = m – q * n, r = k1 * d – q * (k2 * d) = d * (k1 – q * k2). Thus, d divides r.
Reverse direction (<=): Suppose d divides both n and r. Then n = k2 * d and r = k3 * d. Since m = q * n + r, m = q * (k2 * d) + k3 * d = d * (q * k2 + k3). Thus, d divides m.

Question 3

Question: Write an algorithm prime(n) to check if n is prime.

Solution:

Input integer n.
If n <= 1, return False.
For i from 2 to floor(sqrt(n)):
- If n mod i == 0, return False.
Return True.

Question 4

Question: Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.

Solution:

Input integer n.
Initialize an empty list prime_list.
Compute all divisors of n and store them in div_list = divisors(n).
For each element d in div_list:

Call prime(d). If True, append d to prime_list.

Return prime_list.

Question 5

Question: Write an algorithm to compute the prime factorisation of a number. (i) The prime factorisation of 180 is $2^2 \times 3^2 \times 5^1$. How would you represent this? (ii) How would you compare factorisations?

Solution:
Algorithm:

Input n. Set factors = {}. Set d = 2.
While n > 1 and $d^2$ <= n:

count = 0. While n mod d == 0: count++, n = n / d.
If count > 0: Add (d: count) to factors.
d++.

If n > 1: Add (n: 1) to factors.
Return factors.

(i) Representation: As a dictionary: {2: 2, 3: 2, 5: 1}.
(ii) GCD Comparison: For each prime common to both factorisations, take the minimum exponent. Multiply these prime powers to find the GCD.