Chapter 11 Exercise 11.2 Question 1 Solution : List 1 and List 2 are lists of numbers in increasing order. (i) Write an algorithm to find the elements of List 1 that are not in List 2. (ii) Write an algorithm to find the elements of List 2 that are not in List 1.
Solution:
Part (i) · Algorithm: only-in-first(List 1, List 2)
(1) Start with an empty list called only-in-first.
(2) For each number x in List 1: if x does not appear in List 2, add x to the end of only-in-first.
(3) Report only-in-first.
Execute it on divisors of 375 and 825
Take List 1 = divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375] and List 2 = divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825].
| x from List 1 | Appears in List 2? | only-in-first becomes |
|---|---|---|
| 1 | yes | [ ] |
| 3 | yes | [ ] |
| 5 | yes | [ ] |
| 15 | yes | [ ] |
| 25 | yes | [ ] |
| 75 | yes | [ ] |
| 125 | no | [125] |
| 375 | no | [125, 375] |
The answer for part (i) is [125, 375].
Part (ii) · Swap the roles of the two lists
(1) Start with an empty list called only-in-second.
(2) For each number y in List 2: if y does not appear in List 1, add y to the end of only-in-second.
(3) Report only-in-second.
On the same lists, the numbers 11, 33, 55, 165, 275 and 825 are not in List 1, and the others (1, 3, 5, 15, 25, 75) are.
only-in-second = [11, 33, 55, 165, 275, 825]
A faster way using the increasing order
Because both lists are increasing, we can walk along both lists once with a marker on each, instead of searching all of List 2 for every x.
(1) Put marker a on the first number of List 1 and marker b on the first number of List 2.
(2) If the numbers under the markers are equal, move both markers one step.
(3) If the number under a is smaller, it cannot be in List 2, so add it to only-in-first and move a.
(4) If the number under b is smaller, move b.
(5) When List 1 ends, stop. Report only-in-first.
(i) Elements of List 1 not in List 2: [125, 375]. (ii) Elements of List 2 not in List 1: [11, 33, 55, 165, 275, 825].