Algorithm Primer

An algorithm is simply a sequence of precise instructions to solve a problem.  Precise means that there should be no ambiguity to any instruction or which instruction is next.

An example of an algorithm is Zeller’s Algorithm which is used to work out which day of the week a date is

Zeller’s Algorithm                                        Example      15/05/1991

Let Day number = D                                                        D = 15

Month number = M                                                         M = 5

and Year = Y                                                                  Y = 1991

If M is 1 or 2 add 12 to M and subtract 1 from Y.

Let C be the first 2 digits of Y                                          C = 19

and Y’ be the last 2 digits of Y                                        Y’ = 91

Add together the integer parts of

(2.6M5.39),(Y’4) and (C4), then                             7+22+4+15

add on D and Y’ and subtract 2C                                    +9138=101

{Note: Integer part of 2.3 = 2 and 6.7 = 6

1.7= 2 and 3.1 = 4}

Find the remainder when this quantity is divided by 7        1017=14r3

If the remainder is 0 – Sunday, 1 – Monday etc.

Communicating an Algorithm

We can communicate algorithms by ordinary language as above, by pseudo-code (stylised English), computer languages or flow charts.

Let’s take the example of finding the real roots of the quadratic equation

Ax2 + Bx + C = 0  (assume A0)

Using the equation

Using pseudo-code we could write

calc ; note its value;

if this is negative    [no real roots – stop]

else                       [calc root of value

calc (B+root) (2A)

calc (Broot) (2A) – stop].

For programmable calculators we could write

Casio Graphic                                                       Texas TI-81

?A                                                                     :Input A

?B                                                                     :Input B

?C                                                                     :Input C

D                                                    : D

(B+D) (2A)                                                     : (B+D) (2A)

:Pause

(BD) (2A)                                                     (BD) (2A)

{Note: These assume real roots}

In BBC Basic we could write

10      Input “A,B,C”;A,B,C

20      D=B*B4*A*C

30      IF D<0 THEN PRINT “No real roots”: STOP

40      PRINT (B+SQR(D))/(2*A)

50      PRINT (BSQR(D))/(2*A)

Using a flow chart we diagrammatically represent the sequence of steps in an algorithm.

Three types of boxes are common

  1. The start stop box
  2. The instruction box
  3. The question box

Russian Peasant’s Algorithm

Example

Write down side by side the two numbers to be multiplied           163    24

Repeatedly [beneath the LHS number, write down the number    81      48

which is half the number above, ignoring remainders, beneath     40      96

the RHS number write down the number doubled] until you        20     192

reach 1 on the LHS.                                                                  10     384

5       768

2     1536

1     3072

Delete those rows where the number in the LHS is a multiple

of 2.  Add up the numbers left on the RHS                                163      24

81      48

40      96

20     192

10     384

5       768

2     1536

1     3072

This number is the answer                                                                3912

There’s a great demonstration of the Russian Peasants algorithm on the BBC learning websites, and if you’re lucky a couple of explanations on the BBC iPlayer archive.  For many maths lessons for children and adult learners it’s a great resource.  If you’re having trouble accessing from outside the UK then this BBC iPlayer DNS option works great and allows people to access all UK media sites without restrictions.

Another alternative is to use a resource which supplies residential IP addresses, although these aren’t specifically designed for streaming video they work pretty well.  There’s an example of them in this post ATC proxies explained be aware that they can be quite expensive though,