Exercises for the week 5 exercise session¶

Exercise 1¶

You have a bag full of gold coins. You know that one coin is fake, and that the fake coin is heavier than others (which all have the same weight). All coins look indentical, but you have scales that you can use to compare the weight of two sets of coins (which set is heavier or are they of equal weight). Write an algorithm in pseudocode to find the fake coin. Would recursion speed up the solution? How?

Exercise 2¶

In this problem we will use the following array an example: A[12, 14, 5, 3, 7, 20, 16, 9], index i goes from 1 to 8. The goal in this problem is to write pseudocode for a natural mergesort algorithm, in which the elements of some array A[1..n] are put in order from smallest to largest. To understand how a natural mergesort works, one must understand what a decreasing inversion is and what a run is. In an array, which we want to be sorted in increasing order, there is a decreasing inversion at location i when A[i] > A[i+1]. A run is some subarray, in which all the elements are in increasing order. The end of a run always occurs at a decreasing inversion. For example the above array can be broken into 5 runs as follows:

run    run elements
1   [12,14]
2   [5]
3   [3, 7, 20]
4   [16]
5   [9]

In a natural mergesort, we first merge runs 1 and 2, then runs 3 and 4, then runs 5 and 6 and so on, until we have reached the final run. After this merging is done we will have (roughly) half the runs remaining that we started with. We again merge the new runs: runs 1 and 2, runs 3 and 4 and so on. We continue merging the runs until there is only one run left. A description of how natural mergesort works is given in algorithm NATMERGESORT:

NATMERGESORT(A)
1. Start from A[1] find the locations of the decreasing
inversions.  Based on these locations find the start and
end of all the runs.
2. Merge runs 1 and 2, runs 3 and 4, runs 5 and 6 and so
on until no more runs are left to be merged.
3. Repeat step 2, until only one run remains.

Using algorithm NATMERGESORT on the above array, would produce the results given in the following table:

stage  step  runs formed
  1   1  [12,14], [5], [3, 7, 20], [16], [9]
  2   2  [5, 12,14], [3, 7, 16, 20], [9]
  3   2  [3, 5, 7, 12,14, 16, 20], [9]
  4   2  [3, 5, 7, 9, 12, 14, 16, 20]

Task 1: Write pseudocode that implements algorithm NATMERGESORT.

Task 2: In step 1 of NATMERGESORT, we search for a decreasing inversion so that each run we form is in increasing order. However, there is nothing to prevent a run from being in decreasing order. For example, if we arranged the above starting array into runs of either increasing or decreasing order, then we could obtain the following runs:

run   run elements  run type
1   [12, 14]    increasing
2   [5, 3]      decreasing
3   [7, 20]     increasing
4   [16, 9]     decreasing

Now to merge two adjacent runs, we have to know what their ordering is. Write a new version of NATMERGESORT that takes into account both increasing and decreasing runs.