The World of Algorithms

In this chapter, what is an algorithm?

1. aA quick guess that is checked against the answer later
2. bA list of values kept in increasing order
3. cA step-by-step procedure to arrive at an answer
4. dA single formula that gives the answer in one step

We move from adding two 3-digit numbers to adding two 5-digit numbers. How does the work change for counting dots and for the digit-by-digit algorithm?

1. aAbout 2 times as many dots to count, but 100 more columns to add
2. bAbout 100 times as many dots to count, but only 2 more columns to add
3. cAbout 100 times as many dots to count, and 100 times as many columns to add
4. dAbout 10 times as many dots to count, and 2 more columns to add

The algorithm to find the divisors of \(n\) starts with an empty list-of-divisors and checks each \(j = 1, 2, 3, \ldots, n\). For \(n = 18\), what is the list-of-divisors just after \(j = 8\) has been checked?

1. a\([1, 2, 3, 6]\)
2. b\([1, 2, 3]\)
3. c\([1, 2, 3, 6, 9]\)
4. d\([1, 2, 3, 6, 9, 18]\)

In the first algorithm for \(\gcd(m, n)\), the answer is reported as the rightmost element of the list common-divisors. Why is the rightmost element the greatest common divisor?

1. aThe rightmost element is always the smaller of \(m\) and \(n\)
2. bEvery list of common divisors ends with the larger of \(m\) and \(n\)
3. cThe divisor lists are built in increasing order, so the list of common divisors is also in increasing order
4. dThe list of common divisors always has exactly two elements

The first gcd algorithm checks 1 to \(m\) for the divisors of \(m\), and then 1 to \(n\) for the divisors of \(n\). An improved version checks each \(j\) from 1 to \(\min(m, n)\) to see if \(j\) divides both. For \(m = 36\) and \(n = 90\), how many numbers does each version check?

1. a3240 in the first, 36 in the improved version
2. b126 in the first, 90 in the improved version
3. c90 in the first, 36 in the improved version
4. d126 in the first, 36 in the improved version

To find \(\gcd(12, 18)\), most-recent-common-divisor is set to 1, and then each \(k\) from 2 to \(\min(12, 18)\) is checked. How many times is most-recent-common-divisor updated during the scan?

1. a3
2. b5
3. c4
4. d6

Using Euclid’s subtraction algorithm, the first reduction of \(\gcd(91, 35)\) gives which problem?

1. a\(\gcd(91, 56)\)
2. b\(\gcd(35, 21)\)
3. c\(\gcd(56, 21)\)
4. d\(\gcd(35, 56)\)

According to the chapter, the number of reductions needed in Āryabhaṭa’s division algorithm is proportional to:

1. athe value of the smaller of \(m\) and \(n\)
2. bthe number of digits in \(m\) and \(n\)
3. cthe number of divisors of \(m\) and \(n\)
4. dthe value of \(m + n\)

Euclid’s subtraction algorithm (Step 1: if \(m < n\), reverse; Step 2: if \(n = 0\), report \(m\); Step 3: reduce \(\gcd(m, n)\) to \(\gcd(n, m - n)\)) is used to find \(\gcd(28, 12)\). How many times is Step 3 used before the answer is reported?

1. a7
2. b4
3. c5
4. d2

Āryabhaṭa’s division algorithm reduces \(\gcd(m, n)\) to \(\gcd(n, m \text{ mod } n)\), where \(m \ge n\). Which fact justifies this step?

1. a\(m \text{ mod } n\) is always equal to \(m - n\)
2. bA number \(d\) divides both \(m\) and \(n\) exactly when \(d\) divides both \(n\) and \(m \text{ mod } n\)
3. cEvery divisor of \(m\) also divides \(m \text{ mod } n\)
4. d\(m \text{ mod } n\) is always a divisor of both \(m\) and \(n\)

Assertion (A): When two numbers are added column by column, the carry passed to the next column is never more than 1.

Reason (R): In any column, the sum of two digits and a carry of at most 1 is at most \(9 + 9 + 1 = 19\).

1. aBoth A and R are true, and R is the correct explanation for A
2. bBoth A and R are true, but R is NOT the correct explanation for A
3. cA is true, but R is false
4. dA is false, but R is true

Assertion (A): Euclid’s subtraction algorithm finds \(\gcd(99, 2)\) after only two reductions.

Reason (R): If \(d\) divides both \(m\) and \(n\), then \(d\) also divides \(m - n\).

1. aBoth A and R are true, and R is the correct explanation for A
2. bBoth A and R are true, but R is NOT the correct explanation for A
3. cA is true, but R is false
4. dA is false, but R is true

Assertion (A): The word ‘algorithm’ traces back to Algoritmi, the Latin form of Al-Khwārizmī’s name.

Reason (R): Āryabhaṭa’s Āryabhaṭīya (499 CE) contains the ‘long division’ method for finding the gcd.

1. aBoth A and R are true, and R is the correct explanation for A
2. bBoth A and R are true, but R is NOT the correct explanation for A
3. cA is true, but R is false
4. dA is false, but R is true

1. I. I. The addition algorithm assumes that we know how to add single-digit numbers without counting them out.
2. II. II. Adding digit by digit works because each number is grouped into units, tens, hundreds, … and each group is added separately.
3. III. III. Once an algorithm gives the correct answer for one example, we need not justify that it is correct.

Which of the statements above about the addition algorithm is/are correct?

1. aOnly I and III
2. bOnly II and III
3. cI, II and III
4. dOnly I and II

1. I. I. Even in the version without lists, we examine all numbers from 1 to \(\min(m, n)\).
2. II. II. Each refinement changes what is being computed, so a refined algorithm may give a different gcd from the first one.
3. III. III. If the smaller number goes from 3 digits to 4 digits, about 10 times as many values must be scanned.

Which of the statements above about the scanning algorithms for gcd is/are correct?

1. aOnly I and II
2. bOnly II and III
3. cOnly I and III
4. dI, II and III

1. I. I. Al-Khwārizmī learnt Sanskrit and, around 820 CE, wrote a treatise on the Indian place value system and the Indian procedures for the four fundamental operations.
2. II. II. Al-Khwārizmī’s original treatise survives, but its 12th-century Latin translation has been lost.

Which of the statements above about Al-Khwārizmī is/are correct?

1. aOnly I
2. bBoth I and II
3. cNeither I nor II
4. dOnly II

Match each expression in List I with its value in List II:

1. a(i)-R, (ii)-P, (iii)-S, (iv)-Q
2. b(i)-P, (ii)-R, (iii)-S, (iv)-Q
3. c(i)-R, (ii)-P, (iii)-Q, (iv)-S
4. d(i)-S, (ii)-P, (iii)-R, (iv)-Q

Match each part of the divisors algorithm in List I with its description in List II:

1. a(i)-Q, (ii)-S, (iii)-R, (iv)-P
2. b(i)-Q, (ii)-R, (iii)-S, (iv)-P
3. c(i)-P, (ii)-R, (iii)-S, (iv)-Q
4. d(i)-Q, (ii)-R, (iii)-P, (iv)-S

Kabir has to add 3347 and 2729. Counting dots, he can count one dot per second. Column by column, he takes 15 seconds to add two digits with a carry. About how long would each method take him?

1. aAbout 45 seconds by columns; about 10 minutes by counting dots
2. bAbout 15 seconds by columns; over 1 hour 40 minutes by counting dots
3. cAbout 1 minute by columns; about 10 minutes by counting dots
4. dAbout 1 minute by columns; over 1 hour 40 minutes by counting dots

A tailor has two ribbons, 84 cm and 60 cm long. She wants to cut both into pieces of the same length, as long as possible, with nothing left over. She uses Āryabhaṭa’s division algorithm, reducing \(\gcd(m, n)\) to \(\gcd(n, m \text{ mod } n)\). What length does she get, and after how many reductions?

1. a12 cm, after 2 reductions
2. b6 cm, after 3 reductions
3. c12 cm, after 3 reductions
4. d24 cm, after 2 reductions