12 Jun 2022
Section 1.1 defines the syntax and method for documenting the algorithms that will be presented in the book.
I think the methods presented are to be utilized within the larger suite of projects and requirement definition writing that is undertaken professionally. In fact, I would say the key takeaway is what I will call the algorithm syntax.
The text begins with a bit of history and etymology of the word algorithm itself. After wandering through the history Knuth arrives at the modern definition:
By 1950, the word algorithm was most frequently associated with Euclid’s algorithm, a process for find the greatest common divisor of two numbers that appears in Euclid’s Elements (Book 7, Propositions 1 ans 2).
Euclid’s Algorithm, titled as Algorithm E, is then presented in textual and flowchart forms. I think this is important to mention because the format of the algorithm description is the style that will be used to describe all of the algorithms for the rest of the book.
Algorithm E (Euclid’s algorithm). Given two positive integers m and n, find their greatest common divisor, that is, the largest positive integer that evenly divides both m and n.
E1. [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 ≤ r < n)
E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
E3. [Reduce.] Set m ← n, n ← r, and go back to step E1.
Each algorithm is identified by a letter, in the case of Euclid’s algorithm, the letter E. Each step in the algorithm is identified by the algorithm’s letter followed by a number. Each step is further identified by a phrase the sums up the main activity or purpose of the step. This phrase will appear in any flowchart of the algorithm.
When referring to the algorithm within a section only the letter is used. When referring to an algorithm in another section the section number will be prefixed. For this example, Euclid’s algorithm, referred to as E in this section, would be referred to as Algorithm 1.1E from other chapters.
Knuth designed this style to help describe an algorithm as text. Today we rely upon too many visual artifacts to express ourselves. During the 1990s we went through the diagramming wars with Booch, Jacaboson, and Rumbagh, until we arrived at UML. Try tossing a UML diagram out there these days and see where that gets you. Descriptive text is timeless.
After defining how to represent an algorithm, the text moves on to define the features of an algorithm. It is only 1 page and a half of the book but I think it is important to call attention to it. This book is is called “Fundamental Algorithms” so I have a gut feeling that algorithms, and their representation, are going to play a big part of my learning.
The section of algorithms closes with a mathematical discussion. I got to the computational method part that discussed the quadruple (Q,I,Ω, f) where Q is a set containing subset I and Ω … and then it all fades into math. Kuth references The Theory of Algorithms [Trudy Mat. Inst. Nauk 42 (1954), 1-376] as a source I am sure I will never venture a look at. If you check out the link you find a $130 textbook. That is cheap in the realm of textbooks but not something I will ever be interested in.
Even reading, then writing about it in this post is enough.
The exercises are 9 exercises with the most difficult being a level M30. Referring back the notes, this means that it is a moderately hard mathematically oriented problem.
Questions 1-6 were easy to determine the answers with Q6 actually taken time to work out. It was not complex but you just need to run through the algorithm.
Question 7, 8, and 9 dive into the realm of math. ‘nuf said.
< back