1.1 exercises

14. swap a and b, a and c, a and d (3 × 3 steps of replacement) TODO see if we can cut the 9 replacements down even further by exploiting unnecessary temp variable calls

t ← a b ← a a ← t t ← b c ← b b ← t t ← c d ← c c ← t

1.1 answer book

t ← a (save a state) a ← b, b ← c, c ← d, d ← t

1.1 q2

In step 3, we know that m ← n and n ← r, so it is sufficient to prove that r < n. we have m = an + r where a is the largest number that satisfies the equation. For sake of contradiction, suppose that r ≥ n, this implies r = n + b where b ≥ 0  ⟹ m = an + n + b  ⟹ m = (a + 1)n + b which is a contradiction, we assumed that a is the largest number that satisies the equation of that form.

1.1 q3

TODO wrong, it requires 3 is zero checks and 3 remainder checks, see answerbook The [[the_euclidean_algorithm___11_06_2022__090230167|Steps]] is as follows.

3. [Interchange] Set $m \leftarrow \left\lfloor \frac{m}{n} \right\rfloor, n \leftarrow m \% n$
4. [Is it zero?] If n = 0, the algorithm terminates; m is the [[gcd___11_06_2022__09023058|gcd___11_06_2022__09023058]] and go back to step 1.

1.1 q4.

6099/2166 = 2 r 1767 (6099 - 4332) .. 1767, 399 .. 399, 171 .. 171, 57 .. 57

1.1 q5

1. No finiteness, no terminating condition
2. Definiteness “Is section interesting?” “are you mathematically inclined?” (possibly)
3. No output

1.1 q6

The average number of times the step E1 will be computed with n ← 5. TODO plug in m = 1, 2, 3, 4, 5 and then find average.

1.1. q7

The number of times an algorithm executes E1 is well defined as we know that E1 is deterministic and finite. We then divide by n and take a limit for the set of ℝ. $\lim_{n \to \infty} \frac{\text{ The number of times E1 is executed }}{n}$ This in unambiguous, in other words well defined.

With step E0, U_m and T_n are the same.

Without it there would be a step involving the switch of the two. U_m = T_n + 1 where m < n U_m = T_n otherwise.

answerbook

In all but a finite number of cases, n > m. In this caase, the first iteration of Algorithm E merely exchanges these numbers; so U_m = T_m + 1

1.1 q8

TODO We are given.

f((m, n)) = (m, n, 0, 1); f((n)) = (n);

f((m, n, r, 1)) = (m, min (m, n), |m − n|, 2);

f((m, n, r, 2)) = (n) if r = 0, (m, n, r, 3) otherwise ;

f((m, n, p, 3)) = (n, p, p, 1)

answerbook

Let A = {a, b, c}, N = 5. The algorithm will terminate with the string a^gcd(m, n)

1.1 q9

backlinks

• index_of_files.pd
• taocp_exercises