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.
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.
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:
The algorithm is expressed in English. Some technical terms, like
change, were borrowed from Scratch, because we are familiar with Scratch. But I could have expressed them differently, for example:
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.
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.
Given an algorithm which is claimed to solve some kind of problem, a computer scientists will generally want to know two things about it:
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.
How efficient is it? How many processing steps, or how much memory, or now much network throughput, does it require?
An algorithm is a step-by-step process for solving a problem.
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.