An algorithm is a set of instructions for solving a problem using a series of well-defined steps. Computers are algorithm-running machines. Yet algorithms predate computers.
Exercise: Follow Euclid's Algorithm on Paper
On the left is a picture from Wikipedia that shows an ancient algorithm, described around 300BC by Greek mathematician Euclid in his book Στοιχεία. It calculates the greatest common divisor of two numbers. In this flow chart, each step of the algorithm is a box connected to others by arrows.
|Step 1||INPUT A, B: let's pick 6 and 8.||6||8|
|Step 2||Is B = 0? No, so go to step 3.||6||8|
|Step 3||Is A > B? No, so go to step 4.||6||8|
|Step 4||Redefine B to B - A, which is 8 - 6 = 2.||6|
|Step 5||Loop back to step 2.||6||2|
|Is B = 0? No, so go to step 3.||6||2|
|Step 3 again||Is A > B? Yes, so go to step 6.||6||2|
|Step 6||Redefine A to A - B, which is 6 - 2 = 4.|
|Step 7||Loop back to step 2.||4||2|
|Step 2 again||Is B = 0? No, so go to step 3.||4||2|
|Step 3 again||Is A > B?|
What is printed? ______________________________
Four Types of Building Blocks for Algorithms
All algorithms use similar building blocks, no matter how they are written. They use:
INPUTto pick some numbers and
GOTOarrows looping back to repeat some steps).
Here is Euclid's algorithm written in CoffeeScript. This program can be run on pencilcode.net:
a = 6 # store one number in a b = 8 # store another number in b while b isnt 0 # repeat the indented lines as long as b isn't zero: if a > b # if a is greater than b, then do this: a = a - b # replace a with the difference (a - b) else # otherwise (if a is not greter than b): b = b - a # replace b with the difference (b - a) write a # after the loop is done, the answer is a
How to Read an Algorithm in a Programming Language
When reading a programming languge, it is important to learn the special language keywords. The following table explains some of the special words in a CoffeeScript program that are for Memory, Control, Arithmetic, and Primitive functions.
||Arithmetic: these symbols are used for ordinary arithmetic.|
||Comment: The hash starts a comment (for people) that the computer ignores.|
Questions: Exploring Two Ways To Write Algorithms
n, and put commands like