Activity Sheet 1

Manager

name:

Recorder

name:

Speaker

name:

Section 1.1

1. For two positive numbers \(m\), \(n\), assuming \(m > n\), the greatest common divisor of \(m\) and \(n\) is the same as the greatest common divisor of \(n\) and \(m-n\). Use this idea to devise an algorithm for computing the greatest common divisor of two numbers.
2. Write an algorithm that takes as input a shorted array of integers, and another integer. It has to place the new integer in the appropriate place in the array, to maintain the sorted property. You must create and return a new array rather than change the given array.
3. (Book problem 1.1.5) Design an algorithm that given two lists each with numbers sorted from smallest to largest, possibly with repetitions, returns a list of the common numbers (possibly repeated if the lists had some number multiple times). Imagine that you can write your results in a variable length array (so do not worry about having enough space in the resulting array). You can only access the lists by starting from the list start and each time moving to the next element, and you can check if the list is empty.