Algorithms

00000000
⋮
11111111
“Begin at the beginning,” the King said, very gravely,
“and go on till you come to the end: then stop.”
— LEWIS CARROLL, Alice in Wonderland (1865)

The Word Algorithm and Some Related Terms

People like to sample. Scientists do it. Investors do it. Costco members do it. Singles do it. We like to try a little bit of this and a little bit of that. The problem isn’t that we’re too lazy to examine everything or too fickle to stick with one thing. Rather, there are simply too many choices much of the time. It’s often impossible to examine all our options. When there’s a lot at stake, we hesitate before putting all our eggs in one basket, if we do so at all. Diversify and sampling provide comfort and sense of protection against a bad choice.

Sample № 1.
The Art of Computer Programming, Vol. 1
by Donald E. Knuth
Addison-Wesley (1968)
2nd Edition (1973)

The following excerpts are from pages 4-6 of Volume 1 of The Art of Computer Programming, subtitled Fundamental Algorithms. They’re organized in the form of an HTML description list (a <dl> element) composed of terms (<dt> elements) and corresponding descriptions (<dd> elements). A list is an example of a basic data structure. Trees and tables are other examples. Many people who study computer science tend to think of algorithms and data structures as two separate but closely related concepts. We’ll see, however, that not everyone adheres to this doctrine of separatism.

algorithm
The modern meaning for algorithm is quite similar to that of recipe, process, technique, procedure, routine, except that the word “algorithm” connotes something just a little bit different. Besides merely being a finite set of rules which gives a sequence of operations for solving a specific type of problem, an algorithm has five important features:
  1. Finiteness. An algorithm must always terminate after a finite number of steps. ...
  2. Definiteness. Each step of an algorithm must be precisely defined; ...
  3. Input. An algorithm has zero or more inputs, ...
  4. Output. An algorithm has one or more outputs, ...
  5. Effectiveness. An algorithm is also generally expected to be effective. This means that all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using pencil and paper. ...
computational method
A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a “computational method.”
program
An expression of a computational method in a computer language is called a program.
programming language
To get around the difficulty of a reader not understanding exactly what the author intended, formally defined programming languages or computer languages are designed for specifying algorithms, in which every statement has a very definite meaning.
Sample № 2.
Data Structures and Algorithms
by Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman
Addison-Wesley (1983)
Reprinted with corrections (1987)

Aho, Hopcroft and Ullman describe the notion of an algorithm on page 2 of Data Structures and Algorithms, the textbook I used over twenty years ago in CS 251 at Purdue University. They write:
Once we have a suitable model for our problem, we can attempt to find a solution in terms of that model. Our initial goal is to find a solution in the form of an algorithm, which is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite amount of time. ... In an algorithm instructions can be executed any number of times, provided the instructions themselves indicate repetition. However, we require that, no matter what the input values may be, an algorithm terminate after executing a finite number of instructions.
Sample № 3.
Introduction to Algorithms
by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
The MIT Press, McGraw-Hill (1985)

On page 1 of their classic textbook on algorithms, Cormen, Leiserson, and Rivest describe an algorithm as follows.

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

We can also view an algorithm as a tool for solving a well-specified computational-problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

Sample № 4.
Structure and Interpretation of Computer Programs
by Harold Abelson and Gerald Jay Sussman with Julie Sussman
Foreword by Alan J. Perlis
The MIT Press, McGraw-Hill
2nd Edition (1996)

Before we move on, let’s enjoy something a little different — something a bit more spirited than the previous examples. This snippet comes from Structure and Interpretation of Computer Programs, a nice copy of which I recently acquired via Amazon for about $20. (The book I received has an interesting sticker on the back. The words CAL TECH TEXTBOOK appear at the top; that and the price at the bottom of the sticker make me feel good about my investment: $127.25!) On page 1, we encounter this colorful paragraph:

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of our computer with our spells.

It’s not exactly Harry Potter, but the authors score points in my book for their primitive joie de codage.

Consensus

“When I use a word,” Humpty Dumpty said, in rather a scornful tone,
“it means just what I choose it to mean—neither more nor less.”
— LEWIS CARROLL, Through the Looking-Glass (1872)

The sampling presented above might lead one to believe that computer scientists tend to agree, for the most part, about what an algorithm is. And that might be a fair characterization of the current state of affairs. But if we dig a little deeper, we can find examples of some interesting differences of opinion or uses of the word.

In 1985, Knuth presented a keynote address to an international symposium on Algorithms in Modern Mathematics and Computer Science. Reproduced in Chapter 4 of Selected Papers on Computer Science (a book that “assembles under one roof all the things [Knuth has] written about computer science for people who aren’t necessarily specialists in the subject”), the address begins

My purpose in this paper is to stimulate discussion about a philosophical question that has been on my mind for a long time: What rôle does the notion of an algorithm actually play in the mathematical sciences?

For many years I have been convinced that computer science is primarily the study of algorithms. My colleagues don’t all agree with me, but it turns out that the source of their disagreement is simply that my definition of algorithms is much broader than theirs: I tend to think of algorithms as encompassing the whole range of concepts dealing with well-defined processes, including the structure of data that is being acted upon as well as the structure of the sequence of operations being performed; some other people think of algorithms merely as miscellaneous methods for the solution of particular problems, analogous to individual theorems in mathematics.

And as Chapter 0 of Selected Papers on Computer Science, Knuth reproduces a letter he wrote that was originally published in Communications of the ACM 9 (1966), 654. It begins
EDITOR:

The letter by Dr. Huber defines “algorithm” in terms of programming languages. I would like to take a slightly different point of view, in which algorithms are concepts that have existence apart from any programming language. To me the word algorithm denotes an abstract method for computing some output from some input, while a program is an embodiment of a computational method in some language. ...

Of course, if I’m pinned down and asked to explain more precisely what I mean by these remarks, I am forced to admit that I don’t know any way to define any particular algorithm except in a programming language. Perhaps the set of all concepts should be regarded as a formal language of some sort. But I believe that algorithms were present long before Turing et al. formulated them, just as the concept of the number “two” was in existence long before the writers of first grade textbooks and other mathematical logicians gave it a certain precise definition.

An Abstract Concept in Search of Concrete Instances

Half the battle is knowing what problem to solve.
— AHO, HOPCROFT, and ULLMAN (1983, 1987)

Regardless of how one defines the word algorithm, a definition by itself only goes so far. Defining some closely related terms doesn’t entirely fill the gap either. It’s like trying to describe a hammer compared to seeing one. Furthermore, we haven't given much thought to to notion of nails or anything else we might want to apply a hammer (algorithm) to. Even if we described the notion of a nail (a problem) or the act of hammering (problem solving) in detail, what we’d really like to see is an actual hammer hitting an actual nail or some other concrete object. Moreover, there’s no substitute for striking something with a hammer oneself!

In other words, what we need now are some good examples of actual problems and actual algorithms that solve them, perhaps with a so-called data structure or two thrown in for good measure.

Examples of Problems, Procedures, and Algorithms

Procedure S (shampoo).
given we want your money,
  1. If you’re broke,
    then Work (Work is Good).
  2. If you Need shampoo
    (YOU DO!), Buy ours.
  3. Lather.
  4. Rinse.
  5. Go to step 1.
Educators, generals, dieticians, psychologists, and parents program.
Armies, students, and some societies are programmed.
— ALAN J. PERLIS,
Structure and Interpretation of Computer Programs (1984)
Any algorithm that routes every packet along a shortest path
to its destination can be considered to be a greedy algorithm.
— F. THOMSON LEIGHTON,
Introduction to Parallel Algorithms and Architectures (1992)
Many persons who are not conversant with mathematical studies
imagine that because the business of [Babbage’s Analytical Engine] is to
give its results in numerical notation, the nature of its processes must
consequently be arithmetical and numerical, rather than algebraical and
analytical. This is an error. The engine can arrange and combine its
numerical quantities exactly as if they were letters or any other general
symbols; and in fact it might bring out its results in algebraical notation
were provisions made accordingly.
— ADA AUGUSTA, Countess of Lovelace (1844)
quoted in The Art of Computer Programming, Vol. 1 (1968)

PROBLEM № 1
The Fox-Chicken-Grain Puzzle

“I've got one word for you: Trebuchet!”

Algorithm FCG1 (fox, chicken, grain puzzle, method 1). Given a man, a boat, a fox, a chicken, and a sack of grain, all on one side of a river, the problem is getting the man, the fox, the chicken, and the sack of grain to the other side of the river without anything being eaten in the process. The boat can only hold the man and one other object. The boat cannot cross the river without the man. If the fox and the chicken are left alone together, the fox will eat the chicken. If the chicken and the grain are left alone together, the chicken will eat the grain. Let side A denote the side of the river every object is on to begin with, and let side B denote the side of the river every object should be on when the algorithm terminates.

  1. The man and the chicken cross from side A to side B. (The fox and grain are left alone together.)
  2. The man crosses back to side A by himself.
  3. The man and the grain cross from side A to side B in the boat.
  4. The man and the chicken cross back to side A. (The chicken cannot be left alone with the grain.)
  5. The man and the fox cross from side A to side B in the boat.
  6. The man crosses back to side A by himself. (The fox and the grain are left alone together.)
  7. The man and the chicken cross from side A to side B in the boat. The algorithm terminates. ∎

Procedure FCG2 (fox, chicken, grain puzzle, method 2). Assume the same rules, preconditions, and labels (i.e. side A and side B) as those of Algorithm FCG1.

  1. If any object is not on side B, then the man assesses the situation and acts as follows; otherwise, the procedure terminates. ∎
    1. If every object is on side A, then the man crosses the river with the chicken. (The chicken cannot be left alone with either the grain or the fox.)
    2. Otherwise, if the man, the fox, and the chicken are on the same side of the river, then the man flips a coin: if the result is heads, then the man and the fox cross the river together; if the result is tails, then the man and the chicken cross the river. (The fox and the chicken cannot be left alone together. The man knows this, but he’s doesn’t know much else. He’s not innovative, and inefficiency doesn’t bother him. He’s a proud union man.)
    3. Otherwise, if the man, the chicken, and the grain are on the same side of the river, then the man flips a coin: if the result is heads, then the man and the chicken cross the river together; if the result is tails, then the man and the grain cross the river together. (The man knows that the chicken and the grain cannot be left alone together.)
    4. Otherwise, if the man, the fox, and the grain are on side A, then the man flips a coin: if the result is heads, then the man and the fox cross the river together; if the result is tails, then the man and the grain cross the river together. (The man knows he needs to get every object to side B and can only take one thing with him in the boat at a time. He doesn’t care whether the fox or the grain gets there first.)
    5. Otherwise, if the man and the fox are on side A, then the man and the fox cross the river together.
    6. Otherwise, if the man and the chicken are on side A, then the man and the chicken cross the river together.
    7. Otherwise, if the man and the grain are on side A, then the man takes the grain across the river.
    8. Otherwise, if any object is on side A, then the man crosses the river alone. (The man can see that there’s still work to be done, and he knows he’d better not be caught doing nothing.)
  2. Go to step 1.

ALGORITHMS AND MATH

As the previous two procedures for solving the Fox-Chicken-Grain problem demonstrate, the notion of an algorithm is not limited to procedures for computing answers to numerical problems. On the other hand, although it’s not the sort of problem most of us associate with numerical computation, the Fox-Chicken-Grain problem is intimately related to branches of mathematics that deal primarily with logic.

In the preface to Volume 1 of The Art of Computer Programming, Knuth writes:

I wish to show that the connection between computers and mathematics is far deeper and more intimate than these traditional relationships would imply. The construction of a computer program from a set of basic instructions is very similar to the construction of a mathematical proof from a set of axioms.
Indeed, algorithms per se — apart form the computer programs that instantiate them — must be constructed very carefully with close attention paid to the underlying logic on which their effectiveness depends. (As we inch our way toward practical quantum computing devices and algorithms, math becomes even more obviously relevant, due to the critical role that probability plays in quantum mechanics and, therefore, algorithms for quantum computers.)

Of course, many algorithms are directly related to numbers, and many of them are very interesting and clever. In 9 Algorithms that Changed the Future: The Ingenious Ideas that Drive Today’s Computers (Princeton University Press, 2012), John MacCormick explains the concept of an algorithm by way of a solution to a numerical problem that we are all very familiar with.

So far, I’ve been talking about great “ideas” of computer science, but computer scientists describe many of their important ideas as “algorithms.” So what’s the difference between an idea and an algorithm? What, indeed, is an algorithm? The simplest answer to this question is to say that an algorithm is a precise recipe that specifies the exact sequence of steps required to solve a problem. A great example of this is an algorithm we all learn as children in school: the algorithm for adding two large numbers together. [...] The algorithm involves a sequence of steps that starts off something like this: “First, add the first two digits of the two numbers together, write down the final digit of the result, and carry any other digits into the next column on the left; second, add the digits in the next column together, add on any carried digits from the previous example...”—and so on.

Euclid’s Algorithm is a procedure for finding the greatest common divisor (GCD) of two numbers. Variations of this now famous algorithm are often used as exemplars of an algorithm and appear in all sorts of places — on Wikipedia, in textbooks, on standardized tests, etc. Euclid’s Algorithm is the first algorithm that Knuth presents in Volume 1 of The Art of Computer Programming. And Knuth tells us that by the 1950s the very word algorithm was mostly frequently associated with “Euclid’s Algorithm.”

As much as I like repetition and highlighting Good Stuff, I think we should look at just about anything except another GCD algorithm here. Let’s instead consider a numerical problem that’s simple, less frequently exhibited (in the context of explaining the notion of an algorithm, at least), and very relevant to computer programming. Let’s consider the problem of converting a number expressed in binary (base 2) to one of its hexadecimal (base 16) equivalents. (Hexadecimal numbers are usually expressed using a combination of the numeric digits 0-9 and the alphabetical letters a-f or A-F; there’s more than one common way of representing hexadecimal numbers that contain one or more letters, because it makes no difference whether uppercase or lowercase letters are used. The hexadecimal numbers A1 and a1 are both equivalent to the decimal number 161, for example.)

PROBLEM № 2
Converting Binary to Hexadecimal

Algorithm BTH1 (binary to hexadecimal, method 1).

Given a possibly empty sequence b of n binary digits representing a non-negative integer, produce a sequence h of hexadecimal digits that represents the same number. (Initially, n is greater than or equal to zero, and h is empty.)

  1. Divide n by 4 and let r be the remainder. (The value of r will be 0, 1, 2, or 3.)
  2. Add (4 — r) leading zeros to the left-hand side of b and increase the value of n by (4 − r). (Now n will be a multiple of 4.)
  3. If the value of n is zero, then set h ← ‘0’ (the decimal digit 0).
  4. If n is zero, then the value of h is the answer. The algorithm terminates. ∎
  5. Remove the four least significant digits from the right-hand side of b and decrease n by 4. Let x refer to the sequence of four digits removed from b.
  6. Using the following table, find the hexadecimal digit corresponding to x and add that digit to the left-hand side of h.
    The 16 hexadecimal digits and their decimal and binary equivalents are

    hexdecbin hexdecbin
    0=00=0000 8=08=1000
    1=01=0001 9=09=1001
    2=02=0010 a=10=1010
    3=03=0011 b=11=1011
    4=04=0100 c=12=1100
    5=05=0101 d=13=1101
    6=06=0110 e=14=1110
    7=07=0111 f=15=1111
  7. Go to step 4.

Exercises

It is difficult, if not impossible, for anyone to learn a subject purely by reading about it, without applying the information to specific problems and thereby forcing himself to think about what has been read. Furthermore, we all learn best the things that we have discovered for ourselves.
— DONALD E. KNUTH, The Art of Computer Programming (1973)
FIRST SET
  1. nulla

    1. Read “A Life with Books” (pp. 98-101) in C.S. Lewis: His Life & Thoughts by Terry Glaspey.
    2. At the end of 1999, the volumes that comprise The Art of Computer Programming (TAOCP) were named among the best twelve physical-science monographs of the century by American Scientist (source: https://www-cs-faculty.stanford.edu/~knuth/taocp.html). What were the other 11 books?
    3. Does your library own a copy of The Art of Computer Programming?
    4. Make a list of some books you think your library should purchase. Find out who makes the purchasing decisions and try to get the library to purchase one of the books on your list. Were you successful? Why do you think you succeeded or failed? Here are some suggestions:
      • Ask politely.
      • Explain why you are asking. (Be persuasive.)
      • Compose a letter and send it.
      • If the library does purchase a book for you, write a thank-you letter and mail it, and be sure to borrow the book and read some of it!
      • Compose your letters on paper and mail or hand-deliver them. (Sign your name neatly using a nice pen.)
      • Use TEX to compose your letters.
    5. Donald Ervin Knuth created a book about verses of the Bible. What is the title of the book? Who helped him create the book? How and why did Knuth use sampling to produce the book? What did Knuth learn in the process? (See https://www.webofstories.com/play/donald.knuth/72.)
    6. Have fun.
    7. Read Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter and Giant Brains; or, Machines that Think by Edmund C. Berkeley.
    8. Read I am a Strange Loop by Douglas Hofstadter.
    9. Read I am a Strange Loop by Douglas Hofstadter.
    10. Read The Juggling Act: Bringing Balance to Your Faith, Family, and Work by Pat Gelsinger.
    11. Knuth and Karlin
      1. In 2018, the Valley Catholic High School library acquired copies of The Art of Computer Programming by Donald E. Knuth (the box set includes Volumes 1-3 and volume 4A), Concrete Mathematics: A Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, and Game Theory, Alive by Anna R. Karlin and Yuval Peres. What are some ways in which these three books are related to each other? (See appendix C of Concrete Mathematics.) What familial relationship exists between one of the authors of Game Theory, Alive and a teacher at Valley Catholic High School?
      2. Evan Cohn1 wrote a book called Advice for a Daughter. Who is Evan Cohn? (Hint: Ask Mrs. Karlin.) Buy a copy of Evan’s e-book (for $.99 on Amazon) and read it.
    12. Look up the word autodidact in a dictionary.
    13. Who was Mr. Cohn’s and Mrs. Karlin’s Ph.D. adviser? Who wrote the book Mathematical Theory of Computation?
    14. Ponder the following excerpt (retrieved in September, 2018) from the English Wikipedia article Autodidacticism.
      For many professions or for personal knowledge, however, formal education is not so necessary today due to the easier availability of free information on the Internet. Whereas in the past, one of the main benefits of going to college was to gain access to their superior libraries, today access to facts and books is available online. Financial analyst and author Peter Schiff, for one, says, “Never before in history has it been so easy to be self-educated.”


Books are a triviality. Life alone is great.
— THOMAS CARLYLE, Journal (1839)
quoted in The Art of Computer Programming, Vol. 1 (1968)
SECOND SET
  1. Describe the concept of a data structure. Sample the literature and cite your sources.

    A Partial Answer

  2. What is an algorithm? Use your own words. Don’t refer to any sources as you are composing your answer. If you’ve very recently read what someone else wrote or listened to what someone else said about the meaning of an algorithm, then do something else for a while to take your mind off other people’s words before attempting this exercise.
  3. Make a list of some problems that you are familiar with that can be solved using algorithms. Choose one of the problems on your list. Use English to define two algorithms that solve the problem in different ways. Use the examples of algorithms provided above as a guide for composing your algorithms. See section 1.1 of TAOCP for more examples and details.
  4. Is the definition of an algorithm that Knuth gives in section 1.1 of The Art of Computer Programming consistent with or in conflict with his statement “I tend to think of algorithms as encompassing the whole range of concepts dealing with well-defined processes, including the structure of data that is being acted upon as well as the structure of the sequence of operations being performed”?

    An Answer

  5. In what ways does Procedure S (shampoo) fail to be a genuine algorithm according to the definition of an algorithm that Knuth presents in section 1.1 of TAOCP? (See exercise 5 at the end of section 1.1 of TAOCP.)
  6. Compose an algorithm called Algorithm FCG3 that is very similar to Algorithm FCG1 but different. (See exercise 3 for notes about style.)
  7. Analyze Algorithm FCG1 and Procedure FCG2. Consider all possible ways of applying the algorithm or procedure to solve the puzzle and the probabilities that they would be applied in practice. When using the algorithm or procedure to solve the puzzle:
    1. Was is the minimum number of times the man will cross the river?
    2. What is the maximum number of times the man will cross the river?
    3. What is the average number of times the man will cross the river? What is the standard deviation (the square root of the variance)? Note: This question is easy to answer in the case of Algorithm FCG1 and significantly more difficult in the case of Procedure FCG2. Don’t worry if you’re stumped by the harder case.

      A Partial Solution

  8. Using paper, pencil and a coin, trace one execution of Algorithm FCG1 and one execution of Procedure FCG2. After performing each step, note the step number and which side of the river the man, the fox, the chicken, and the grain are on.
  9. Perform Procedure FCG2 ten times. After each execution of the algorithm, record the number of times the man crossed the river. Analyze the results using the metrics described in exercise 7.
  10. Create a program (use any programming language you like) that implements Procedure FCG2 and outputs the number of times the man crossed the river. Write another program that runs the first program some number of times (the number of times being an input to the program) and produces as output an analysis (as described in exercise 7) of the results. Use your program to perform Procedure FCG2 1 million times. What were the results?

    An Answer

  11. Learn how to evaluate the JavaScript expression
    (Math.floor(Math.random() * 1000)).toString(2);
    and evaluate it ten times. Record the string of 1s and 0s produced each time and use Algorithm BTH1 to convert the strings to hexadecimal.
  12. Using English, compose an algorithm that is equivalent to the algorithm implemented by the expression provided in exercise 11. (See exercise 3 for notes about style.)
  13. Learn how to evaluate a Java expression that is equivalent to the JavaScript expression in exercise 11. Write a Java program that evaluates the expression and prints the result. (There are many online and print resources you can use to learn how to program using the Java programming language. A very good one is the book Computer Science: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne. Who was Robert Sedgewick’s Ph.D. adviser?)
  14. Describe an algorithm for converting a string of 1s and 0s from binary to hexadecimal that is different from Algorithm BTH1. Call your algorithm BTH2.
  15. Compare Algorithm BTH1 with the algorithm you created in exercise 14 (BTH2).

I believe that the creation of a great puzzle or a great pattern is a scholarly achievement of great merit, an important contribution to world culture, even though the author of such a breakthrough is often an amateur who has no academic credentials.
— DONALD E. KNUTH, Selected Papers on Fun & Games (2011)

FOOTNOTE

  1. In response to a shameless advertisement of an early draft of this page, I received the following message from Evan Cohn about Zohar Manna.
    From: er
Subject: Re: Chapter 1 (Fascicle 1): Algorithms
Date: Mon, 03 Sep 2018 08:36:10 -0800

A prof of mine from Stanford (Zohar Mann [sic]) died the other day.  A student of his wrote...

(Zohar) continued his graduate studies in Computer Science at Carnegie-Mellon University
in Pittsburgh, Pennsylvania, under the guidance of Robert W Floyd and Alan J. Perlis, where
he obtained his Ph.D. in 1968. Going backwards, we find that his advisor,

Alan J. Perlis, was a student of <---- who you quote sometimes...
Philip Franklin, who was a student of
Oswald Veblen, who was a student of
Eliakim Hastings Moore, who was a student of
Hubert Anson Newton, who was a student of Michel Chasles, who was a student of
Simeon Denis Poisson, who was a student of
Joseph Louis Lagrange, who was an unofficial student of
Leonhard Euler, who was a student of
Johann Bernoulli, who was a student of his brother,
Jacob Bernoulli, who was an autodidact.