The Art of Computer Programming/Algorithms/Exercises
Answers for Exercises for Section 1.1
[edit | edit source]This page is part of The Art of Computer Programming
Section 1.1 Exercises
1. [10] The text showed how to interchange the values of variables m and n, using the replacement notation, by setting t ← m, m ← n, n ← t. Show how the values of four variables (a, b, c, d) can be rearranged to (b, c, d, a) by a sequence of replacements. In other words, the new value of a is the original value of b, etc. Try to use the minimum number of replacements.
My solution:
temp ← a a ← b b ← c c ← d d ← temp
Knuth’s solution: Same
2. [15] Prove that m is always greater than n at the beginning of step E1, except possibly the first time this step occurs.
My solution: The first time this step occurs n and m are the input values, so there it is possible that m is greater than n. After the first time this step occurs, m will be the value of n, and n will be the value of r (the remainder of m divided by n). Since the remainder of m divided by n will always be less than n, m (which is the previous value of n) is always greater than n (which is the remainder r).
Knuth’s Solution: Basically the same. After the first time, the values of the variables m and n are the previous values of n and r, respectively; and n > r.
3. [20] Change Algorithm E (for the sake of efficiency) so that all trivial replacement operations such as set m to n are avoided. Write this new algorithm in the style of Algorithm E, and call it Algorithm F.
My Solution: Here is my thinking on this one: In algorithm E, the value of m is not needed after finding the remainder of m divided by n. So instead of saving the remainder (step 1) in variable r, it can overwrite the value of m. Step 2 then had to be changed since 1) the remainder is now stored in variable m, and 2) the answer if the remainder is zero, is in variable n. The reduction (step E3) was replaced with steps F3 and F4 that reverse the division and save the remainder in variable n (with the corresponding changes in checking if the remainder is zero.) Then we can go back to step F1 since the remainder is now back in n.
Algorithm F (Euclid’s algorithm with no trivial replacements) Given two positive integers m and n, find their greatest common divisor, that is, the largest integer that evenly divides both m and n.
F1. [Find remainder] Divide m by n and let m be the remainder. (0 ≤ m ≤ n) F2. [Is it zero?] If m = 0, the algorithm terminates; n is the answer. F3. [Find remainder] Divide n by m and let n be the remainder. (0 ≤ n ≤ m) F4. [Is it zero?] If n = 0, the algorithm terminates; m is the answer, else go back to step F1.
Knuth’s solution: Same, just worded differently. Algorithm F (Euclid’s algorithm) Given two positive integers m and n, find their greatest common divisor.
F1. [Remainder m / n] Divide m by n and let m be the remainder. F2. [Is it zero?] If m = 0, the algorithm terminates with answer n. F3. [Remainder n / m] Divide n by m and let n be the remainder. F4. [Is it zero?] If n = 0, the algorithm terminates with answer m, otherwise go back to step F1.
4. [16] What is the greatest common divisor of 2166 and 6099?
Solution using the initial definition of algorithm E:
m = 2166, n = 6099, r = 2166 m = 6099, n = 2166, r = 1767 m = 2166, n = 1767, r = 399 m = 1767, n = 399, r = 171 m = 399, n = 171, r = 57 m = 171, n = 57, r = 0 Answer is 57
5. [12] Show that the “Procedure for Reading This Set of Books” that appears in the preface actually fails to be a genuine algorithm on three of out five counts! Also mention some differences in format between it and Algorithm E.
My Solution: It does not meet the guidelines for finiteness, definiteness, and effectiveness. Some of the differences between it and Algorithm E is that algorithm E terminates, it only used mathematical steps, and the result of performing the algorithm is clearly defined.
The algorithm is not finite since it never terminates so it does not satisfy the finiteness. The algorithm has steps that are not precisely defined. For example, how does one determine if the subject of the chapter is interesting (step 5), how tired do you have to be before you should sleep (step 14). Since it has zero inputs, it satisfies the input condition. The output is specified in step 12 – work exercises so it satisfies the output condition. I am guessing that this algorithm is not effective – for example, step 9 asks if you are mathematically inclined, but there is no effective operation given to determine this.
Knuth’s solution: Not finite nor definite nor effective, perhaps no output; in format, no letter is give before step numbers, no summary phrase appears, and there is no “|”.
Analysis: I got the first part right at least. But I did not even answer the correct question in the second part – I missed the “difference in format” part of the question.
6. [20] What is T5, the average number of times step E1 is performed when n = 5?
My solution: Using my solution to exercise 2 above, n will decrease by at least on each time through step E1, and the remainder of m divided by n will be at most 4. So the most times that E1 will be executed is 5 times and the average number of times step E1 is performed is 5 / 2 or 2.5
Knuth’s solution: Trying Algorithm E with n = 5 and m = 1, 2, 3, 4, 5, we find that step E1 is executed 2, 3, 4, 3, 1 times, respectively. So the average is 2.6 - T5.
Analysis: Note to self: Answers to questions that Knuth pose need to be preciously figured out, the answer is exact not just about. Oh well. Now I have to figure out Knuth’s solution.
m = 1, n = 5, r = 1 m = 5, n = 1, r = 0 answer is 1 and E1 was executed 2 times
m = 2, n = 5, r = 2 m = 5, n = 2, r = 1 m = 2, n = 1, r = 0 answer is 1 and E1 was executed 3 times
m = 3, n = 5, r = 3 m = 5, n = 3, r = 2 m = 3, n = 2, r = 1 m = 2, n = 1, r = 0 answer is 1 and E1 was executed 4 times
m = 4, n = 5, r = 4 m = 5, n = 4, r = 1 m = 4, n = 1, r = 0 answer is 1 and E1 was executed 3 times
m = 5, n = 5, r = 0 answer is 5 and E1 was executed 1 time
Average = (2 + 3 + 4 + 3 +1) / 5 = 13 / 5 = 2.6
7. [M21] Suppose that m is known and n is allowed to range over all positive integers; let Um be the average number of times that step E1 is executed in Algorithm E. Show that Um is well defined. Is Um in any way related to Tm?
My Solution: No clue. In order to figure out the M questions, I think that I will 1) try to figure it out, but do not spend a lot of time on it, 2) if I have no clue; I am going straight to Knuth’s solution and then spend the time trying to understand it. Maybe this is a cop out, but I think I will see how this method goes.
Knuth’s solution: In all but a finite number of cases, n > m. And when n > m, the first iteration of Algorithm E merely exchanges these numbers, so Um = Tm + 1.
Analysis: My first question is about the finite number. This is because m is known and there are only m values that are less than or equal to m, so there are in fact, a finite number of cases, n > m. Now, when n > m, the remainder of m divided by n will always be m since m is divisible by n zero times. So the first step of E1 will swap m and n when n > m.
I did not see the difference right away between Um and Tm, but here is what I get: Um is the average number of times step E1 is performed when m is fixed and n varies. Tm, is the average number of times step E1 is performed when n is fixed and m varies.
So when m is fixed and n > m, a swap is made between n and m and now n is fixed so Um = Tm + 1, but if m is fixed and m > n than there is no swap and Um = Tm. I guess Knuth opted not to include this since there are only a finite number of cases when this occurs.