Exercises - 1.1 Algorithms

Exercises 5, 7 and 9 are marked as valuable.

1. [10] Show how the values of the variables $(a,b,c,d)$ can be rearranged to $(b,c,d,a)$ by a sequence of variable assignments.
2. [15] Prove that $m$ is always greater than $n$ at the beginning of step E1, except possibly the first time this step occurs.
3. [20] Change Algorithm E (for the sake of efficiency) so that all trivial replacements such as "$m\leftarrow n$" are avoided. Call this Algorithm F.
4. [16] What is the greatest common divisor of 2166 and 6099?
5. [12] Show that the “Procedure for Reading This Set of Books” fails to be a genuine algorithm on three of the five counts. Solution
6. [20] What is $T_5$, the average number of times step E1 is performed when $n=5$?
7. [HM21] Let $U_m$ be the average number of times that step E1 is performed if $m$ is known and $n$ is allowed to range over all positive integers. Show that $U_m$ is well defined. Is $U_m$ in any way related to $T_m$?
8. [M25] Give an “effective” formal algorithm for computing the greatest common divisor of positive integers $m$ and $n$, by specifying ${\theta }_j$, ${\varphi }_j$, $a_j$, $b_j$. Let the input be represented by the string $a^m{b}^n$, that is, $m$ $a$‘s followed by $n$ $b$‘s.
9. [M30] Suppose that $C_1=(Q_1,I_1,{\Omega }_1,f_1)$ and $C_2=(Q_2,I_2,{\Omega }_2,f_2)$ are computational methods. Formulate a set-theoretic definition for the concept ”$C_2$ is a representation of $C_1$” or ”$C_2$ simulates $C_1$“. This is to mean intuitively that any computation sequence of $C_1$ is mimicked by $C_2$, except that $C_2$ might take more steps in which to do the computation and it might retain more information in its states.