What is an Algorithm?

Do this on pencilcode.net

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.

  1. Follow Euclid's ancient algorithm by studying this table and filling out the rest:

Step NumberActionAB
Step 1 INPUT A, B: let's pick 6 and 8. 68
Step 2 Is B = 0? No, so go to step 3. 68
Step 3 Is A > B? No, so go to step 4. 68
Step 4 Redefine B to B - A, which is 8 - 6 = 2. 6
8
→2
Step 5 Loop back to step 2. 62
Step 2 again  Is B = 0? No, so go to step 3. 62
Step 3 again Is A > B? Yes, so go to step 6. 62
Step 6 Redefine A to A - B, which is 6 - 2 = 4.
6
→4
2
Step 7 Loop back to step 2. 42
Step 2 again Is B = 0? No, so go to step 3. 42
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:

  1. Primitive functions that are not broken into substeps. Here, 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.
  2. Control flow defining "what is next" in a way that allows choices (arrows coming out of diamond boxes) and repetition (GOTO arrows looping back to repeat some steps).
  3. Memory to store and use bits of information such as the variables A and B.
  4. Arithmetic operations using math like 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

  1. On paper, draw a flow chart for an algorithm to compute the factorial of a, a!=1×2×3×...×a.
  2. On paper, write your algorithm for a! using the listed CoffeeScript keywords.
  3. The arrows in the flowchart for Euclid's algorithm never cross. Using the listed CoffeeScript keywords, can you write a "spaghetti code" program whose flowchart requires crossing arrows no matter how it is drawn? Explain.