CBSE Class 9 Maths Ganita Manjari Part 2 Ch 11 The World of Algorithms MCQs with Answers Set 01

Answer: (b) a systematic step-by-step procedure for solving a problem

Explanation:
1. An algorithm is a sequence of precise steps that solves every problem of a given kind.
2. (a) usually takes one step, not many; (c) is trial and improvement; (d) is a justification, not the procedure itself.

Teacher's Note:
1. Stress 'systematic' and 'step-by-step'.
2. Each step must be followable without guessing.

Answer: (d) digits in the same column must stand for the same place value

Explanation:
1. The method adds units to units, tens to tens and so on.
2. Aligning from the right puts digits of equal place value in the same column.

Teacher's Note:
1. Place value is the real reason.
2. (c) is a situation where alignment matters, not the reason itself.

Answer: (a) 1

Explanation:
1. The largest column total is 9 + 9 + 1 = 19.
2. 19 contains only one ten, so the carry out is at most 1.

Teacher's Note:
1. This is why the algorithm needs only two cases: total < 10 or ≥ 10.
2. Show the worst case 9 + 9 + 1.

Answer: (c) [1, 2, 3, 4, 6, 8, 12, 24]

Explanation:
1. The algorithm tests j = 1, 2, …, 24 and keeps every j that divides 24.
2. It keeps 1, 2, 3, 4, 6, 8, 12 and 24. Both 1 and 24 itself are always included.

Teacher's Note:
1. 1 and n are always divisors of n.
2. Check each option for missing entries.

Answer: (b) 6 entries

Explanation:
1. divisors(48) = [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]; divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60].
2. Common: [1, 2, 3, 4, 6, 12], which has 6 entries. The last one, 12, is the gcd.

Teacher's Note:
1. Write both lists fully before comparing.
2. The rightmost common entry is the gcd.

Answer: (a) the candidates are tested in the order 1, 2, 3, …, n

Explanation:
1. Candidates are tested in increasing order, and each divisor found is added at the end.
2. So each new entry is larger than all earlier ones. No sorting step exists.

Teacher's Note:
1. The order is a free by-product of the scan.
2. Reversing the scan would reverse the list.

Answer: (c) gcd(n, m − n)

Explanation:
1. Euclid's reduction: gcd(m, n) = gcd(n, m − n) when m ≥ n.
2. The new pair uses smaller numbers, which is what makes it useful.

Teacher's Note:
1. Keep n, replace m by m − n.
2. The other options are common mis-rememberings.

Answer: (d) m mod n

Explanation:
1. Subtracting n from m again and again until you cannot leaves the remainder m mod n.
2. One division does the work of many subtractions: gcd(m, n) = gcd(n, m mod n).
3. It is the remainder, not the quotient m ÷ n, that is needed.

Teacher's Note:
1. Division = repeated subtraction done in one go.
2. Remainder, not quotient.

Answer: (b) 2

Explanation:
1. gcd(56, 42) → gcd(42, 14) → gcd(14, 0).
2. Two reductions; the algorithm then stops and reports 14.

Teacher's Note:
1. Count arrows, not problems.
2. 14 is the answer, not the step count.

Answer: (c) n = 0, and the answer reported is m

Explanation:
1. Both stop at gcd(m, 0) and report m.
2. Every number divides 0, so the common divisors of m and 0 are just the divisors of m; the greatest is m.

Teacher's Note:
1. The stopping rule is shared by both algorithms.
2. gcd(23, 23) → gcd(23, 0) shows why.

Answer: (a) the name of the mathematician Al-Khwārizmī

Explanation:
1. The Latin translation of Al-Khwārizmī's work began 'Algoritmi…', from the Latin form of his name.
2. It became algorismus → algorism → algorithm.

Teacher's Note:
1. The word honours a person, not a language.
2. His book spread Indian arithmetic to Europe.

Answer: (d) the Indian place-value system and the Indian procedures for the four operations

Explanation:
1. The title means 'The Book of Al-Khwārizmī on Indian Numerals'.
2. It explained Indian place-value numerals and the Indian methods for +, −, × and ÷.

Teacher's Note:
1. The Arabic original is lost; only the Latin survives.
2. A key route of Indian mathematics into Europe.

Answer: (b) 1

Explanation:
1. It must start at a value that is certainly a common divisor.
2. 1 divides every number, so 1 is always safe.
3. The scan then tries k = 2, 3, …, min(m, n) and replaces the value when a larger common divisor appears.

Teacher's Note:
1. A safe starting value keeps the algorithm correct even if nothing larger is found.
2. Coprime pairs report 1.

Answer: (c) no common divisor of m and n can be larger than the smaller of the two

Explanation:
1. A divisor never exceeds the number it divides.
2. So a common divisor cannot exceed the smaller number.
3. (a) is false: the gcd may equal the smaller number.

Teacher's Note:
1. Candidates beyond min(m, n) are certain to fail.
2. Example: gcd(12, 24) = 12 = min.

Answer: (a) the pair m, n and the pair n, m − n have exactly the same common divisors

Explanation:
1. If d divides m and n, it divides m − n. If d divides n and m − n, it divides their sum m.
2. So both pairs have the same common divisors, hence the same greatest one.
3. (c) is only half of the argument.

Teacher's Note:
1. The justification must work in both directions.
2. Same set of common divisors ⇒ same gcd.

Answer: (c) about 50 reduction steps

Explanation:
1. Each reduction subtracts just 2: gcd(2, 97), gcd(2, 95), …
2. With 99 = 2k + 1, k = 49, about k reductions are needed (running it gives 51).

Teacher's Note:
1. The step count follows the value 99, not its 2 digits.
2. This weakness motivates Āryabhaṭa's method.

Answer: (b) 2 reduction steps

Explanation:
1. gcd(99, 2) → gcd(2, 1) → gcd(1, 0).
2. Two reductions instead of about fifty.

Teacher's Note:
1. One division replaces a whole run of subtractions.
2. Compare 2 vs 51 steps.

Answer: (d) the rightmost element of the list of common divisors

Explanation:
1. The list of common divisors is in increasing order.
2. Its largest entry is the rightmost one, which is the gcd.
3. The first entry would always be 1.

Teacher's Note:
1. Rightmost = largest in an increasing list.
2. Link to 'greatest' in gcd.

Answer: (a) if j divides n, add j to the list-of-divisors

Explanation:
1. A conditional step acts only when a condition holds, here 'if j divides n'.
2. (c) is the repeated step, (b) the initialisation and (d) the output.

Teacher's Note:
1. Conditional ⇒ look for 'if'.
2. Repeated ⇒ look for 'for each'.

Answer: (c) max(m, n)

Explanation:
1. Two scans test 1…m and 1…n: m + n candidates.
2. One scan of 1…max(m, n), checking both numbers, covers them all.
3. min(m, n) is the next refinement, when only common divisors are wanted.

Teacher's Note:
1. Each refinement cuts the work further.
2. Keep the sequence: m + n → max → min.

Answer: (b) a data structure

Explanation:
1. A data structure organises the values an algorithm keeps track of.
2. The chapter's example is the list, kept in ascending order.

Teacher's Note:
1. Lists are the chapter's only data structure.
2. More data structures come in later grades.

Answer: (d) add two single-digit numbers together with a carry

Explanation:
1. Every algorithm rests on basic steps assumed to be available.
2. Column addition assumes single-digit addition (with a carry) can be done directly.

Teacher's Note:
1. Basic steps mark where an algorithm's explanation stops.
2. Dot-counting is what the algorithm avoids.

Answer: (a) Step 5, which writes the leftover carry to the left of the bottom row

Explanation:
1. The columns give 4, 3 and 3, and the hundreds column leaves a carry of 1 with no digits left.
2. Step 5 writes that final 1 to the left, turning 334 into 1334.

Teacher's Note:
1. Without Step 5 the answer would be 1000 too small.
2. The final carry needs its own step.

Answer: (c) 100

Explanation:
1. The work is proportional to the value of the smaller number.
2. A 3-digit number is about \( 10^3 \) and a 5-digit number about \( 10^5 \): a factor of 100.

Teacher's Note:
1. Two extra digits ⇒ a hundredfold more work.
2. Work tied to value grows very fast.

Answer: (d) √n

Explanation:
1. Divisors pair as (d, n ÷ d), and in each pair the smaller one is at most √n.
2. Testing up to √n finds one member of each pair; the partner is written down directly.
3. For 36: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), found by testing up to 6.

Teacher's Note:
1. If both members exceeded √n, their product would exceed n.
2. Big saving: 10 000 → 100 tests.

Answer: (b) It must be the fastest possible procedure for the problem.

Explanation:
1. The chapter gives several correct gcd algorithms, each faster than the last.
2. So being an algorithm does not require being the fastest.
3. Repeated steps, conditional steps and justification are genuine features.

Teacher's Note:
1. Correct and efficient are separate qualities.
2. Improvement is part of the algorithm story.

Answer: (c) 3

Explanation:
1. gcd(96, 36) → gcd(36, 24) → gcd(24, 12) → gcd(12, 0).
2. Three arrows, so three reductions. It reports 12.

Teacher's Note:
1. Count the arrows between problems.
2. Four problems but three steps.

Answer: (a) the number of digits used to write the two numbers

Explanation:
1. Each division cuts the numbers down sharply rather than removing a fixed amount.
2. So the step count grows with the number of digits, not the size.
3. This matches the goal set by column addition.

Teacher's Note:
1. Digits grow slowly; values grow fast.
2. The proof is left to later grades.

Answer: (d) run through its steps one by one for a particular input

Explanation:
1. Executing = carrying out the steps on specific data, tracking the named values.
2. (a) is justifying and (b) is analysing, which are different activities.

Teacher's Note:
1. Execute, justify, analyse: three distinct words.
2. Example: divisors(18) growing to [1, 2, 3, 6, 9, 18].

Answer: (b) build the list of common multiples and report its leftmost element

Explanation:
1. For the lcm we need common multiples, and we want the least one.
2. In an increasing list the least entry is the leftmost.

Teacher's Note:
1. gcd: greatest common divisor → rightmost.
2. lcm: least common multiple → leftmost.