Algorithm

---

This post summarizes what I’ve learned from The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.) by Donald E. Knuth (1997), Chapter 1 Section 1 [p. 1-9]. The exercises, algorithms and some answers discussed are drawn from this book.

---

Algorithms are similar to recipes or routines. However, rather than being executed by a person, algorithms are executed by a computer. Recipes and algorithms are quite similar in a sense that they both consist of finite sequence of operations designed to solve a problem. The key distinctions between recipes and algorithms are outlined by the following five features:

Finiteness:

The sequence of operations must be finite and must eventually solve the problem.

Definiteness:

Each step of an algorithm must be precisely defined

Input:

There can be zero or many inputs.

Output:

An algorithm must produce at least one output, which is the result of the problem the algorithm is trying to solve.

Effectiveness:

The operations should be simple enough to be performed with just pen and paper and should have a finite length.

When an algorithm lacks finiteness, it is referred to as a computational method. One can define computation methods in terms of set theory.

Note that Definition 1 does not address the feature of effectiveness. To restrict the method to elementary operations, we impose additional constraints on . For example: let be a set of finite letters and be the set of all strings on . Let and be the set of all , where and . Let with , and let with . If , we say that occurs in if for some strings . Lastly, let , integers , for any , and defined by

After doing the exercises, it seems clear what some of the notations represent. The positive integer indicates which rule should be executed when a string from the -th rule does not occur in . Furthermore, it seems that refers to the next step to be executed when a string is replaced by a string in . At , the algorithm terminates and the output is .

One example of an algorithm is the Euclid’s algorithm for finding the greatest common divisor.

Let us try this algorithm by hand. Let and , then we exchange because otherwise the reminder is zero, which is not their greatest common divisor. Then the reminder of is , since . Then we set and , which has zero remainder because . Therefore, the greatest common divisor of 122 and 10 is 2. Note that in Algorithm 1 step E4, we don’t go back to E1, since always after the first step. This is proven in the Exercise 2.

As a remark about Algorithm 1, the notations that is used here will be used for other posts as well. The notation means that we replace the current value of with the current value . We are not using since will mean something that can be checked. The exchange notation can also be done by introducing an auxiliary variable, say . Indeed, is equivalent to . Lastly, the order of assignments is important. For instance is different than . Indeed, the latter means , which is equivalent to .

Exercises

1. [10] To rearrange to , we can do .

2. [15] The positive integer is always greater than at the beginning of step E1, except possibly the first time this step occurs. Indeed, after it occurs for the first time, we have , where . After that, as long as , we replace by and by . Since , we have that after the first step.

3. [20] We can change Algorithm E so that the replacement operations, such as , are avoided. Consider the example and . According to Algorithm E, we have , which has a remainder . Instead of replacing , we can set and compute . Then, has a remainder . Because , in Algorithm E, we compute . Because , we can this time set and therefore we are computing the remainder of , which is . Lastly, if we set , the remainder of is zero. Set , then is the output. In the above procedure, we do not use . To summarize, we have the following updated algorithm:
   
   Algorithm 2. Let , find their greatest common divisor, that is , the largest positive integer such that it divides both and .
   F1. [Ensure .] If , exchange .
   F2. [Find remainder.] Divide by . Assign the remainder to , i.e. .
   F3. [Is it zero?] If , the output is .
   F4. [Find remainder.] Divide by . Assign the remainder to , i.e. .
   F5. [Is it zero?] If , the output is . Repeat to F2. There is no need to go back to F1, since always after the first exchange as proven in Exercise 2.

4. [16] The remainder of is . Then, the remainder of is . Then, the remainder of is . Then, the remainder of is . Lastly, the remainder of is zero. Therefore, the greatest common divisor of and is .

5. [12] The "Procedure for Reading This Set of Books" is not an algorithm because it is not definite, effective and does not have an output. An example of why definiteness is lacking is in step 15, where it is not clearly defined where or for how long to sleep. Regarding the format difference with Algorithm 1, there is no letter in front of each step, and there is no short summary after each number.

6. [20] Let be the average number of times step E2 (without executing E1) is performed. Let , then we need to compute the number of times steps E2 is performed for since in step E2, only the remainder is relevant. Writing out how many times E2 is performed for yields .

7. [HM21] Suppose is known and is allowed to range over all positive integers. Let be the average number of times step E2 is executed in Algorithm 1. The average is well-defined because the positive integer keeps being reduced until the remainder is zero, at which point the algorithm terminates. Therefore will not be . Regarding the relation of with , consider the case is fixed. Writing out the execution of step E2, we will notice that for , the number of times step E2 is executed increases by 1 compared to when is fixed. Therefore . To confirm this, we compute the number of steps manually for . First, for , the number of times step E2 is executed are respectively. Then, for every such that , the number of times step E2 is executed are . Suppose we do this many times, then

8. [M25] The goal of this part of the exercise, is to rewrite the Algorithm 1 without step E1 into an "effective" formal algorithm. The given input is , and the question is, how should we define and ? There is a hint that states to start with . However, we do not see how the hint is related to the input. After looking at the answers and doing some research on the internet, we still don’t see how the hint is suppose to help. Though, it clarifies how the algorithm proposed in the answer is suppose to mimic Euclid’s algorithm.

   The idea is to adjust the input, such that the output is . To do this, there are sets of rules that we need to specify. These rules contain simple operations such that removing, adding and replacing strings. The rule can be represented in terms of strings, by removing ’s and ’s until either of them disappears, depending on whether or . For instance can be programmed by removing both and until remains, and therefore the answer is .

   Now, how about ? We connect this substitution with the answer as follows: there needs to be a record of how much we subtract from . This is because we will use this number again to compute . To do this, for instance, if and , then we remove ’s three times, and ’s will disappear. We then add a new letter , since we do removal operations three times and we are left with . If and , then we are left with . To ensure that there is a loop and the string is of the form , we can replace all ’s by ’s and all ’s by ’s.

   In summary, we perform the following algorithm with the input . Let and . Define

9. [M30] Suppose and are computational methods. The goal is to formulate a set-theoretic definition for the concept " is a representation of ". Somehow, there should be functions that translate objects from to . In this exercise, we tried to understand how the answer sheet explain one approach to solve this problem.

   First let us discuss the inputs and the outputs. The inputs in should be the inputs of as well. Though they must be embedded in their computational states. To formalize this, let and . These functions must satisfy the constraint for . As for the outputs, we must ensure that the outputs of corresponds to the outputs of , and vice versa. That is, if and only if . In other words, a computational state in is the outputs of the algorithm if and only if its translation via are outputs in .

   Now how about the computational rules? Well, when translating a textbook algorithm into a computer program, we sometimes need several steps to convert the abstract rules into a form that a computer can execute. These rules in , should translate the rules in . Let , we require that for some .

   Therefore, is a representation of if and only if there exists , , and , such that
   a) , where ;
   b) , where ;
   c) where .

   When reading this definition, one might wonder why the functions are not specified to be surjective, injective or bijective. For both of the functions, it might be because some states in may not have an exact counterpart in , or the computational states in approximate the computational states in . For instance, it is not possible to represent irrational numbers such as and in a computer. This is because computers can only store numbers using finite-length strings.