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 Number | Action | A | B |
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 | ╱
8→2
|
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. | ╱
6→4 | 2 |
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:
INPUT
to pick some numbers
and PRINT
to write a number are primitives. Primitives
may be different in different situations. A cooking robot
might start already knowing how to setOvenTemperature
.
GOTO
arrows
looping back to repeat some steps).
A
and B
.
B←B-A
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.
= |
Memory:
name = value
defines (or redefines) a variable
like a or b . |
while |
Control:
while condition repeats
a block of code until a condition becomes false. |
if else |
Control:
if condition runs a block of
code only if a condition is true;
directly after that block,
else denotes
a second block of code to be run
if the condition is false.
|
is and isnt |
Arithmetic:
x is y tests whether
x and y are equal,
and x isnt y tests inequality.
|
< and > |
Arithmetic:
x < y tests whether
x is less than y ,
and x > y tests if
x is greater. |
+ -
* / |
Arithmetic: these symbols are used for ordinary arithmetic. |
write |
Primitive: write x is a predefined
function that writes x
to the Pencil Code screen. |
# |
Comment: The hash starts a comment (for people) that the computer ignores. |
Questions: Exploring Two Ways To Write Algorithms
a
, f
,
and n
, and put commands like f←1
and n←1
and
n←n+1
in boxes.