Making and Following Algorithms

  1. Jenny's stepmother requires her to fetch exactly $7$ liters of water from the nearby river. She gives Jenny two buckets that hold $3$ and $5$ liters respectively. The buckets are not transparent and they have no level indicator markings. So the only operations Jenny can do are fill an entire bucket with water from the river, pour all water from a bucket back into the river, pour water from one of the buckets to another one until the first bucket is empty or the second bucket is full. Jenny doesn’t know what to do and needs your help. Write an algorithm that she can follow that will help her complete her task.

  2. Consider the following algorithm, written in pseudo-code:

    Let A = 2
    Let N = 5
    Let R = 1
    While N > 0, repeat the following two steps
         Let R = R * A
         Let N = N - 1
    Print the value of R
    1. Walk through this algorithm, recording the values of A, N, and R after each step.

    2. What does this algorithm accomplish? You may want to try other initial values for A and N (e.g. $A=3$, $N=2$ or $A=3$, $N=3$); look at the final values of A, N and R; and find a pattern. How does R relate to A and N?

  3. Apply the Extended Euclidean Algorithm to find linear combinations of the following pairs of numbers that equal the greatest common divisors of those numbers:

    1. $a=19789$, $b=23548$
    2. $a=31875$, $b=8387$
    3. $a=22241739$, $b=19848039$