Algorithms

Version 2¹

What is an algorithm?

In the beginning of the course, I explained the algorithm as meaning a plan or procedure for solving a problem. Now it is time to be a little more exact, to understand the term in the sense that computer scientists study algorithms.

1. An algorithm is a step by step procedure. Howewver, we've learned in our study of scratch that sequence is only one of the three ways of putting steps together: we also have conditional and repetition control structures.

2. The steps of an algorithm are so clear, definite, and precise that a machine could execute them: they are mechanical steps.
   • Human beings can also execute algorithms. The first computers were people.
   • What counts as a "mechanical" step depends on the "machine" that is used. In Scratch, for example, simple steps include:
     • storing a value in a variable
     • asking a question and waiting for an answer
     • putting the pen down
     • changing the color of a sprite
     • playing a sound. These operations are in Scratch's "instruction set", but we would not expect them to be part of the instruction set of every computer.
       In general, a step in an algorithm can be anything the machine already "knows" how to do.

Example

The factorial function: fact(n) = n! = 1 × 2 × ... × n. For example, 5! = 1 × 2 × 3 × 4 × 5 = 120.

Here's an algorithm for computing n factorial:

1. Input n
2. Set product to 1
3. Set m (the multiplier) to 2
4. Repeat until m > n:
   1. set product to m × product
   2. change m by +1
5. Output product

Comments

• The algorithm is expressed in English. Some technical terms, like set and change, were borrowed from Scratch, because we are familiar with Scratch. But I could have expressed them differently, for example:

  • 4a. replace product with m × product
  • 4b. add 1 to m

• We human beings can execute the algorithm. Let's do that. Use pencil and paper or chalklboard to keep track of the state of variables.

• We could not "run the algorithm" on an electronic computer. We must first translate it into a programming language; we can then run the resulting program. A programming language is a formal language which can be "understood" by the computer; thus it can execute a program.

  Examples:

  • Scratch (image of script)
  • Python
  • C
  • Java

  Each of these programs is a little different from the others, because they are expressed in different languages. But they all express the same idea, or algorithm.

• Students interested in learning more about programming may take INFO I210, Information Infrastructure I, in the fall, followed by INFO I211, Information Infrastructure II, in the spring.

What do computer scientists want to know about algorithms?

Given an algorithm which is claimed to solve some kind of problem, a computer scientists will generally want to know two things about it:

1. Is it correct? For obvious reasons. Lots of programs are buggy. Some computer programs are among the most complex systems made by human ingenuity. If we can prove an algorithm is correct, we eliminate one source of bugs.

2. How efficient is it? How many processing steps, or how much memory, or now much network throughput, does it require?

   • Sorting has been extensively studied, because so much computer time (about 33%) is spent sorting data. There are numerous sorting algorithms; some are considerably more efficient than others.

     Sorting races, anyone?

     • Sorting algorithms: a race!
     • Another sorting algorithms race

Summary

An algorithm is a step-by-step process for solving a problem.

• It has specified inputs and outputs.
• Steps are specified precisely and in detail.
• Every step is "mechanically" executable; i.e., it does not require imagination or creativity.
• It is usually desirable for an algorithm to come to an end: to always find an answer and stop.
• Other interesting properties of algorithms include correctness and efficiency.
• Algorithms are not programs, except for human computers. But they are the conceptual basis for programs for electronic computers.

Incidentally

The word algorithm comes to us from the Persian mathematician al-Khwarizmi, who, around 825 A.D., wrote a book on Calculation with Hindu Numerals. It was translated into Latin in the 12th century, with the title Liber Algoritmi de numero Indorum. Algoritmi was the Latinized form of the author's name, but but came to mean the subject of his book.

Gregory Weber