🌐 All Subjects 🔬 Science 🌍 Social Science 📐 Mathematics 📖 English 🪶 हिन्दी
← Back to Chapter 11 Exercises

⚙️ Chapter 11: The World of Algorithms • Exercise Set 11.2

Verified step-by-step solutions for your class notes.

Exercise Set 11.1 5Exercise Set 11.2 3Exercise Set 11.3 2End-of-Chapter Exercises 5All Exercises 15
Q1

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.

Answer:
(i) Algorithm for elements in List 1 not in List 2:
1. Start with an empty list called 'difference-list'.
2. For each number x in List 1:
    If x does not appear in List 2, add x to 'difference-list'.
3. Report 'difference-list'.

(ii) Algorithm for elements in List 2 not in List 1:
1. Start with an empty list called 'difference-list'.
2. For each number y in List 2:
    If y does not appear in List 1, add y to 'difference-list'.
3. Report 'difference-list'.

Q2

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

Answer:
Algorithm to find lcm(m, n):
1. Set a variable 'multiple' to the value of the larger number between m and n.
2. Check if 'multiple' is divisible by the smaller number.
3. If it is divisible, report 'multiple' as the lcm.
4. If it is not divisible, add the larger number to 'multiple' and repeat Step 2.

Q3

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?

Answer:
(i) We only need to examine numbers from 1 up to the square root of n (i.e., $\sqrt{n}$). For every divisor $d \le \sqrt{n}$, its pair is $n/d$.
(ii) The original gcd algorithm assumes the generated divisor lists are in strictly increasing order to simply pick the "rightmost" element at the end. If we append both $d$ and $n/d$ at the same time, the list won't be strictly increasing unless we sort it afterwards. If we sort it, the algorithm works perfectly; if not, we must modify the last step to search the entire common-divisors list for the maximum value rather than just taking the rightmost element.