Chapter 11: The World of Algorithms

Two-Pointer Linear Scan Algorithms:

Because both lists are sorted in increasing order, we do not need to compare every element of List 1 with every element of List 2. We can scan both lists simultaneously in a single pass (like merging sorted decks of cards).

1. (i) Algorithm: Elements in List 1 not in List 2 (Difference: List 1 − List 2):
   • Step 1: Start with an empty list result = [ ].
   • Step 2: Set index pointers i = 1 (for List 1) and j = 1 (for List 2).
   • Step 3: While i ≤ length(List 1) and j ≤ length(List 2):
     – If List 1[i] < List 2[j]: append List 1[i] to result, and increment i by 1.
     – If List 1[i] == List 2[j]: increment i by 1 and increment j by 1 (it is present in both).
     – If List 1[i] > List 2[j]: increment j by 1.
   • Step 4: If List 2 is exhausted but List 1 has remaining elements: append all remaining elements of List 1 to result.
   • Step 5: Output result.
2. (ii) Algorithm: Elements in List 2 not in List 1 (Difference: List 2 − List 1):
   Apply the exact same algorithm with the roles of List 1 and List 2 swapped (or whenever List 2[j] < List 1[i], append List 2[j] to result and increment j; if List 1 ends first, append all remaining elements of List 2).

Two Algorithmic Approaches for LCM:

1. Method 1 — Using the Fundamental GCD Relationship (Most Efficient):
   For any two positive integers m and n:
   lcm(m, n) × gcd(m, n) = m × n &implies lcm(m, n) = (m × n) / gcd(m, n)
   Algorithm:
   • Step 1: Compute g = gcd(m, n) using Åryabhaṭa’s / Euclid’s division algorithm.
   • Step 2: Divide m by g to get q = m / g (dividing first prevents integer overflow with large numbers).
   • Step 3: Compute lcm = q × n.
   • Step 4: Return lcm.
2. Method 2 — Multiples Scan Algorithm (From First Principles):
   • Step 1: Set multiple = max(m, n).
   • Step 2: While multiple mod min(m, n) ≠ 0:
     – multiple = multiple + max(m, n)
   • Step 3: Report multiple as lcm(m, n).
   Example for lcm(6, 8): Scan 8 (not div by 6), 16 (not div by 6), 24 (divisible by 6!). lcm = 24.

Step-by-step Solution:

1. (i) How many numbers must be examined?
   • For every divisor d ≤ √n, there is a paired divisor (n/d) ≥ √n.
   • If both factors were strictly greater than √n, their product would exceed n (since √n × √n = n), which is impossible.
   • Therefore, every factor pair has at least one member ≤ √n. We only need to examine integers from 1 up to ⌊√n⌋.
   • Count of numbers examined: exactly ⌊√n⌋ numbers (for n = 10,000, instead of 10,000 checks, we only do 100 checks!).
2. (ii) Will our GCD algorithm still work?
   • In our first GCD algorithm (Section 11.2.3), Step 5 reports the rightmost element of common-divisors, assuming the list is in strictly increasing order.
   • If we discover divisors in pairs and append them as found — e.g. for 18: [1, 18, 2, 9, 3, 6] — the list is no longer sorted in increasing order.
   • Modification required: The GCD algorithm will work correctly if we either:
     (a) Sort the list of common divisors before reading the last element, or
     (b) Maintain a variable max_common and update it with the largest common divisor found, or
     (c) Insert the paired divisors from the right end of the list.

Step-by-step Analysis of Reverse Divisor Scan:

1. Algorithm Modification:
   • Step 2 changes from “For each j in 1, 2, …, n” to “For each j in n, n−1, n−2, …, 1”.
   • Each time j divides n, j is added to list-of-divisors.
2. Consequences:
   • Output Order: The list will be generated in strictly descending order (e.g. divisors(18) = [18, 9, 6, 3, 2, 1]).
   • Number of Checks: The total number of checks remains exactly n, so scanning backwards does not reduce the workload if all divisors are needed.

Early Termination Breakthrough:

1. The Backward Scan Procedure:
   We start k at min(m, n) and count downwards: k = min(m, n), min(m, n) − 1, min(m, n) − 2, …, down to 1.
2. What happens when we find a divisor?
   Because we are scanning from the largest possible divisor downwards, the very first number k that divides both m and n is guaranteed to be the GREATEST common divisor!
3. Immediate Termination:
   We can stop immediately and return k without testing any of the remaining numbers!
   • Best case: If n divides m, the first check (k = n) succeeds, and the algorithm terminates in just 1 step!
   • Example: gcd(50, 100). The first check tests k = 50. Since 50 divides 100, it halts in 1 step! (The forward algorithm would have performed 50 steps).

Step-by-step Division by Remainder for All Four Pairs:

1. (i) gcd(375, 825):
   • 825 ÷ 375 = 2 with remainder 75 &implies 825 = 375 × 2 + 75
   • 375 ÷ 75 = 5 with remainder 0 &implies 375 = 75 × 5 + 0
   gcd(375, 825) = 75
2. (ii) gcd(51000, 81000):
   • 81,000 = 51,000 × 1 + 30,000
   • 51,000 = 30,000 × 1 + 21,000
   • 30,000 = 21,000 × 1 + 9,000
   • 21,000 = 9,000 × 2 + 3,000
   • 9,000 = 3,000 × 3 + 0
   gcd(51000, 81000) = 3,000
3. (iii) gcd(1789287, 237656):
   • 1,789,287 = 237,656 × 7 + 125,695
   • 237,656 = 125,695 × 1 + 111,961
   • 125,695 = 111,961 × 1 + 13,734
   • 111,961 = 13,734 × 8 + 2,089
   • 13,734 = 2,089 × 6 + 1,200
   • 2,089 = 1,200 × 1 + 889
   • 1,200 = 889 × 1 + 311
   • 889 = 311 × 2 + 267
   • 311 = 267 × 1 + 44
   • 267 = 44 × 6 + 3
   • 44 = 3 × 14 + 2
   • 3 = 2 × 1 + 1
   • 2 = 1 × 2 + 0
   gcd(1789287, 237656) = 1 (The numbers are coprime!)
4. (iv) gcd(2587392, 157656):
   • 2,587,392 = 157,656 × 16 + 64,896
   • 157,656 = 64,896 × 2 + 27,864
   • 64,896 = 27,864 × 2 + 9,168
   • 27,864 = 9,168 × 3 + 360
   • 9,168 = 360 × 25 + 168
   • 360 = 168 × 2 + 24
   • 168 = 24 × 7 + 0
   gcd(2587392, 157656) = 24

Mathematical Proof (Bidirectional “If and only if”):

By the division algorithm, dividing m by n gives a quotient q and remainder r = m mod n such that:
m = qn + r  ⇔  r = m − qn

1. Forward Direction (⇒): If d divides m and d divides n, then d divides both n and (m mod n):
   • Since d divides m and n, there exist integers a and b such that m = ad and n = bd.
   • Substituting into r: r = m − qn = ad − q(bd) = (a − qb)d.
   • Since (a − qb) is an integer, d divides r (which is m mod n).
   • Therefore, d divides both n and m mod n.
2. Reverse Direction (⇐): If d divides n and d divides (m mod n), then d divides both m and n:
   • Let r = m mod n. Since d divides n and r, there exist integers b and c such that n = bd and r = cd.
   • Substituting into m: m = qn + r = q(bd) + cd = (qb + c)d.
   • Since (qb + c) is an integer, d divides m.
   • Therefore, d divides both m and n.

Formulation of prime(n):

1. Method 1 — Using the Hint with divisors(n):
   • Step 1: If n ≤ 1, report False (1 is not prime by definition).
   • Step 2: Compute L = divisors(n) using the earlier divisor algorithm.
   • Step 3: If length(L) == 2 (meaning its only divisors are [1, n]), report True.
   • Step 4: Otherwise, report False.
2. Method 2 — Direct Optimized Algorithm (O(√(n)) trial division):
   • Step 1: If n ≤ 1, return False.
   • Step 2: If n == 2, return True.
   • Step 3: If n mod 2 == 0, return False.
   • Step 4: For each odd integer j from 3 up to ⌊√n⌋:
     – If n mod j == 0, return False (composite).
   • Step 5: Return True (prime).

Algorithm primedivisors(n):

1. Step 1: Start with an empty list prime-divisors = [ ].
2. Step 2: Compute all-divisors = divisors(n).
3. Step 3: For each number d in all-divisors:
   – Check if prime(d) is True.
   – If True, append d to prime-divisors.
4. Step 4: Return prime-divisors.

Step-by-step Solution:

1. Algorithm to Compute Prime Factorisation of n:
   • Step 1: Set temp = n, d = 2, and start with an empty mapping factors = { }.
   • Step 2: While d × d ≤ temp:
     – count = 0
     – While temp mod d == 0:
         count = count + 1
         temp = temp / d
     – If count > 0: record factor d with exponent count (e.g. factors[d] = count).
     – d = d + 1
   • Step 3: If temp > 1: record factors[temp] = 1.
   • Step 4: Return factors.
2. (i) Representing 180 = 2² × 3² × 5¹:
   • Representation A (Key-Value Dictionary / Map): {2: 2, 3: 2, 5: 1} where keys are prime bases and values are exponents.
   • Representation B (List of Pairs): [(2, 2), (3, 2), (5, 1)].
   • Representation C (Expanded prime multiset): [2, 2, 3, 3, 5].
3. (ii) Comparing Prime Factorisations of m and n:
   • Align all primes appearing in either factorisation, assigning exponent 0 to any prime missing in one of the numbers.
   • To find GCD: Take the minimum exponent for each prime:
   gcd(m, n) = ∏ p_i^{min(exp_m, exp_n)}
   • To find LCM: Take the maximum exponent for each prime:
   lcm(m, n) = ∏ p_i^{max(exp_m, exp_n)}
   • Example: 180 = 2² × 3² × 5¹ and 75 = 2⁰ × 3¹ × 5²:
     – gcd = 2^min(2,0) × 3^min(2,1) × 5^min(1,2) = 2⁰ × 3¹ × 5¹ = 15.
     – lcm = 2^max(2,0) × 3^max(2,1) × 5^max(1,2) = 2² × 3² × 5² = 900.