The World of Algorithms (Class 9): Notes और MCQ Practice

आसान भाषा में

Algorithm किसी भी problem को solve करने का एक step-by-step procedure (नियमबद्ध तरीका) होता है। जैसे numbers को dots गिनने के बजाय right-to-left column method से add करना। Algorithms हमारे काम को systematically organize करते हैं ताकि calculation बहुत तेज़ी से और कम steps में पूरी हो सके।

Important Points & Definitions

• Algorithm: किसी problem का exact result पाने की step-by-step precise विधि।
• Data Structure: Information को organize करने का structure (जैसे List, उदा. [1, 2, 3]), जो intermediate values को store करने और algorithm को efficient बनाने के काम आता है।
• Divisors & GCD: $n$ के divisors हमेशा 1 और $n$ के बीच होते हैं। Common divisors में सबसे बड़ा number GCD (Greatest Common Divisor) होता है।
• Refined Scan for GCD: Common divisor ढूँढने के लिए 1 से $\min(m, n)$ तक scan करके most-recent-common-divisor track किया जाता है।
• Euclid’s Subtraction Algorithm: यदि $m \ge n$, तो $\gcd(m, n) = \gcd(n, m - n)$। जब $n = 0$ हो, तो answer $m$ होता है।
• Āryabhaṭa’s Division Algorithm: Repeated subtraction की जगह remainder (mod) का उपयोग: $\gcd(m, n) = \gcd(n, m \bmod n)$। यह steps की संख्या बहुत घटा देता है।

Memory Tricks

1. Right to Left, Carry is Kept: Addition हमेशा rightmost column से शुरू करें; दो single digits के जोड़ में carry कभी भी 1 से ज़्यादा नहीं हो सकता।
2. Euclid Minus, Āryabhaṭa Modulo: याद रखें Euclid घटाव ($m - n$) करते हैं, जबकि Āryabhaṭa remainder ($m \bmod n$) से तेज़ी लाते हैं!

Common Mistakes

1. Base Case भूलना: Euclid या division algorithm में loop तब रुकता है जब दूसरा number $0$ बन जाए; answer $\gcd(m, 0) = m$ होता है, $0$ नहीं!
2. Order Reverse न करना: यदि $m < n$ हो, तो subtraction या modulo करने से पहले numbers को reverse करके $\gcd(n, m)$ बनाना ज़रूरी है।

The World of Algorithms

1. Chapter in Short

This chapter introduces the fundamental idea of an algorithm—a precise, step-by-step method for solving a problem. Using basic arithmetic, it compares slow methods (like counting dots) with efficient column-by-column addition based on place value. It then explores different ways to find the Greatest Common Divisor (GCD) of two numbers, progressing from listing all divisors and using lists (data structures) to more refined algorithms. Finally, it contrasts Euclid's subtraction algorithm with the much faster Āryabhaṭa's division algorithm, which uses remainders (mod) to drastically cut down the number of calculation steps.

2. Key Concepts Explained Simply

What is an Algorithm?

An algorithm is a step-by-step recipe or set of precise instructions to solve a problem or calculate an answer.

• Everyday Example: Making a cup of tea. If you do not follow the exact order (boiling water, adding tea leaves, straining), you will not get the correct result. Similarly, mathematical algorithms require following exact steps without doing anything that is not specified.

Efficiency: Value vs. Number of Digits

• When we add numbers by counting dots, adding larger numbers takes far too long. If a number grows from 3 digits to 4 digits, there are 10 times as many dots.
• But when using the Indian base-ten place-value system (adding digit by digit from right to left with a carry), moving from a 3-digit number to a 4-digit number requires only one extra column of addition, taking just seconds instead of hours.

What is a Data Structure?

When an algorithm runs, it needs names to store intermediate answers (like j or list-of-divisors). A list (written using square brackets, e.g., [1, 2, 3, 6]) is an example of a data structure. Data structures organize information so an algorithm can use it efficiently.

Finding the Greatest Common Divisor (GCD)

The GCD (or HCF) is the largest number that divides two given numbers completely.

• Method 1 (Listing Divisors): Find all divisors of m, find all divisors of n, collect the common ones into a list, and pick the rightmost (largest) number.
• Method 2 (Single scan up to min(m, n)): A common divisor cannot be larger than the smaller of the two numbers. We scan numbers from 1 to min(m, n).
• Method 3 (No lists): Keep a single variable most-recent-common-divisor. Start at 1. Test each number up to min(m, n). Whenever a number divides both, update the variable. The final value is the GCD.

Euclid's Subtraction Algorithm

Euclid observed that if a number d divides both m and n, it must also divide their difference m − n.

• Tiling Idea: If blocks of size d can perfectly "tile" lengths m and n, they can also tile the remaining length m − n.
• Therefore: gcd(m, n) = gcd(n, m − n) (when m ≥ n).
• When we reach gcd(m, 0), the answer is m.
• Limitation: For numbers like gcd(99, 2), repeated subtraction takes many steps (proportional to the size of the number).

Āryabhaṭa's Division Algorithm

Found in Indian treatises like Āryabhaṭa's Āryabhaṭīya (499 CE), this method uses repeated division by remainder instead of slow, repeated subtraction.

• Instead of reducing gcd(m, n) to gcd(n, m − n), we reduce it to gcd(n, m mod n), where m mod n is the remainder when m is divided by n.
• This solves problems like gcd(99, 2) in just 2 reduction steps!

3. Important Definitions, Facts, and Dates

• Algorithm: A step-by-step procedure to arrive at an answer, described by writing down the steps as precisely as possible.
• Executing an Algorithm: Running through the steps of an algorithm one by one.
• Data Structure: A way of organizing information (such as a list) to help make an algorithm more efficient.
• List Notation: An ordered collection written inside square brackets, e.g., [1, 2, 3, 6, 9, 18].
• m mod n: The remainder obtained when m is divided by n (for example, 17 mod 5 = 2 and 33 mod 7 = 5).
• Euclid: Greek mathematician who recorded the subtraction GCD algorithm in his famous work Elements.
• Āryabhaṭa (499 CE): Indian mathematician whose work Āryabhaṭīya describes the efficient "long division" / remainder method for finding GCD using Indian place-value numerals.
• Stopping Condition for GCD Reductions: When the second number becomes 0, i.e., gcd(m, 0) = m.

4. Solved Examples

Example 1: Finding the Divisors of a Number

Problem: Execute the algorithm to find all divisors of 18.

Solution:

1. Start with an empty list-of-divisors = [ ].
2. Test each number j from 1 to 18:

• j = 1: divides 18 → [1]
• j = 2: divides 18 → [1, 2]
• j = 3: divides 18 → [1, 2, 3]
• j = 4, 5: do not divide 18 → unchanged
• j = 6: divides 18 → [1, 2, 3, 6]
• j = 7, 8: do not divide 18 → unchanged
• j = 9: divides 18 → [1, 2, 3, 6, 9]
• j = 10 to 17: do not divide 18 → unchanged
• j = 18: divides 18 → [1, 2, 3, 6, 9, 18]

Answer: divisors(18) = [1, 2, 3, 6, 9, 18].

Example 2: Finding GCD Using most-recent-common-divisor

Problem: Find gcd(6, 12) without maintaining lists.

Solution:

1. Find min(6, 12) = 6.
2. Set most-recent-common-divisor = 1.
3. Scan k from 2 to 6:

• k = 2: divides both 6 and 12 → update to 2.
• k = 3: divides both 6 and 12 → update to 3.
• k = 4: does not divide 6 → remains 3.
• k = 5: does not divide 6 → remains 3.
• k = 6: divides both 6 and 12 → update to 6.

1. Scan complete.

Answer: gcd(6, 12) = 6.

Example 3: Euclid's Subtraction Algorithm

Problem: Find gcd(225, 75) using Euclid's subtraction steps.

Solution:

• Step 1: m = 225, n = 75. Since m ≥ n, reduce to gcd(n, m − n) = gcd(75, 225 − 75) = gcd(75, 150).
• Step 2: Since 75 < 150, reverse the numbers → gcd(150, 75).
• Step 3: Reduce to gcd(75, 150 − 75) = gcd(75, 75).
• Step 4: Reduce to gcd(75, 75 − 75) = gcd(75, 0).
• Step 5: Since n = 0, report m.

Answer: gcd(225, 75) = 75.

Example 4: Comparing Euclid's vs. Āryabhaṭa's Algorithm on gcd(99, 2)

Problem: Show how many reduction steps Āryabhaṭa's division algorithm takes for gcd(99, 2) compared to repeated subtraction.

Solution:

• Euclid's subtraction algorithm: Subtracts 2 repeatedly: gcd(97, 2), gcd(95, 2), ..., gcd(3, 2), gcd(2, 1), gcd(1, 1), gcd(1, 0). This takes about 49 to 50 reduction steps (proportional to the number's value).
• Āryabhaṭa's division algorithm:

1. m = 99, n = 2. Reduce to gcd(n, m mod n) = gcd(2, 99 mod 2) = gcd(2, 1) (since 99 divided by 2 leaves remainder 1).
2. Reduce to gcd(1, 2 mod 1) = gcd(1, 0) (since 2 divided by 1 leaves remainder 0).
3. Since n = 0, report m = 1.

Answer: It takes only 2 reduction steps to find gcd(99, 2) = 1.

5. Common Mistakes and Quick Revision Points

• Forgetting to Align from Right to Left: In digit-by-digit addition, digits must be aligned from right to left so that units add to units, tens to tens, and hundreds to hundreds.
• Carry Value Limit: In adding two numbers, the carry from any column can never be more than 1 (maximum single-digit addition is 9 + 9 + 1 = 19).
• Forgetting to Reverse in GCD Algorithms: When using Euclid's or Āryabhaṭa's algorithm, always ensure m ≥ n. If m < n, first reverse them to gcd(n, m).
• Stopping Condition: Do not stop when numbers become equal; continue until the second number becomes 0 (gcd(m, 0) = m).
• Remainder Concept: Remember that m mod n is the remainder, not the quotient. For example, 17 mod 5 = 2, not 3.