Capt. Horatio T.P. Webb

ALGORITHMS & CHUNKING Last Updated 8AM 2/25/2015

Algorithm:

• a procedure or formula for solving a problem. The word derives from the name of the mathematician, Mohammed ibn-Musa al-Khwarizmi, who was part of the royal court in Baghdad and who lived from about 780 to 850

• 'Algorithm' stems from the name of a Latin translation of a book written by al-Khwarizmi, a Persian mathematician, astronomer and geographer,. Al-Khwarizmi wrote a book titled On the Calculation with Hindu Numerals in about 825 AD, and was principally responsible for spreading the Indian system of numeration throughout the Middle East and Europe. It was translated into Latin as Algoritmi de numero Indorum (in English, "Al-Khwarizmi on the Hindu Art of Reckoning"). The term "Algoritmi" in the title of the book led to the term "algorithm".

• Turing (1936-1937) The discussion starts with a person (a human computer) and ends with a machine (a mechanical computer):

  "Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book....

  I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite....

  The behaviour of the computer at any moment is determined by the symbols which he is observing, and his 'state of mind' at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite...

  Let us imagine that the operations performed by the computer to be split up into 'simple operations' which are so elementary that it is not easy to imagine them further divided."

  Turing's reduction yields the following:

  "The simple operations must therefore include:

  1. Changes of the symbol on one of the observed squares
  2. Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

  It may be that some of these change necessarily invoke a change of state of mind. The most general single operation must therefore be taken to be one of the following:

  1. A possible change (a) of symbol together with a possible change of state of mind.
  2. A possible change (b) of observed squares, together with a possible change of state of mind

  We may now construct a machine to do the work of this computer."

• Rogers (1987): "There is a computing agent, usually human, which can react to the instructions and carry out the computations"

• Minksy (1967): "But we will also maintain, with Turing . . . that any procedure which could "naturally" be called effective, can in fact be realized by a (simple) machine. Although this may seem extreme, the arguments . . . in its favor are hard to refute".

• Gurevich (2000):"...Turing's informal argument in favor of his thesis justifies a stronger thesis: every algorithm can be simulated by a Turing machine ... according to Savage [1987], an algorithm is a computational process defined by a Turing machine".

• Knuth -- fast algorithms (1973): "In practice we not only want algorithms, we want good algorithms ... one criterion of goodness is the length of time taken to perform the algorithm ... other criteria are the adaptability of the algorithm to computers, its simplicity and elegance, etc."

• Rogers (1987): "Any classical mathematical algorithm, for example, can be described in a finite number of English words"

• Stone (1973): "there must be, ...a procedure that a robot [i.e., computer] can follow in order to determine precisely how to obey the instruction." Stone adds finiteness of the process, and definiteness (having no ambiguity in the instructions) to this definition.

The Structure Theorem (1966)

by Corrado Bohm and Giuseppe Jacopini. All algorithms are constructed using only three constructs:

1. Executing one subprogram, and then another subprogram (sequence)[SEQUENTIALS]
2. Executing one of two subprograms according to the value of a boolean expression (selection) [IF-THEN-ELSE]
3. Executing a subprogram until a boolean expression is true (iteration) {LOOPS]

Nassi Schneiderman Diagrams (1972)

by Isaac Nassi and Ben Shneiderman (graduate students in computer science at SUNY - Stoney Brook)

See this wikipedia article

or this by Schneiderman

Examples of everyday Algorithms (Lists-Of-Things-To-Do -- LOTTD)

• A Biscuit Recipe

  

• Baby Sweater Knitting Instructions

  Sample was knit with approximately 140gm of crepe spun baby wool (yardage unknown) on 3.25mm needles and would fit a small new-born.
  Gauge of sample: 13sts and 28 rows to 5cm over garter st.

  Use Number 3 Needles/2 ply yarn
  Original pattern was knit on size 3 needles, of 3 play baby yarn and looks like it may fit new-born to three months. To make it bigger, just use appropriate yarn you want (such as knitting
  worsted) and then use the suggested needles and gauge for THAT yarn. Knitting worsted on size 7 comes out bigger - maybe 6 to 9 months size

  Pattern:
  Cast on 60 stitches.
  Knit two rows on these 60 stitches.
  Row 1 - Knit 50 stitches, wrap and turn

  Row 2 - Pull yarn to back, slip one stitch (as if to purl) from left needle onto right needle, knit to other end (count this as the bottom).

  Row 3 - Knit complete 60 stitches to top or neck edge.

  Row 4 - Knit from neck edge to bottom edge;  then go back to Row 1.

  Continue these short rows until you have 30-35 ridges depending on size you want).

  Then knit 35 stitches and place on a stitch holder.  Knit 15 stitches, keeping last 10 stitches same as before for yoke.

  Knit down 25 stitches (including stitches for yoke), turn and cast on 30 stitches for sleeve.

  Work 10 stitches at cuff edge same as yoke (Knit 45, slip one stitch from left needle onto right needle; turn and knit to other end).

  When you have 25 ridges on cuff edge, bind off the 30 stitches you put on for sleeve.

  Slip the 35 stitches from holder and make back, same as front, always keeping the yoke the same.

  When you have 65 ridges on the bottom of the back (don't forget to adjust the number of ridges if you previously adjusted them on the front) , Knit 35 stitches and put on a holder.

  Make other sleeve.

  Make other front.

  Neck  edge - pick up with # 1 needle at neck about 92 stitches.  K2, P2 for 4 rows. Next row - K4, K2 tog across row to end.  Knit one row.  Then bind off.

  Make 2 small chains (no longer than 12cm) and attach at neck edges to form tie.

• Assemble a workout machine

  

Chunking (modularization)

Once an algorithm is complete and is expressed as (a) a list of verbs (instructions) or (b) drawn with a Nassi-Schneiderman diagram (a stack of boxes), the entire algorithm represents a "procedure to perform some action". If we think about the list in its entirety it can be called:

• a "module"
• a "procedure"
• a "program"
• a "function" (in programming languages such a FORTRAN, BASIC and C and others)
• a "method" (in more modern object oriented programming languages such a C++, C#, or Java)
• a "routine" (or a subroutine in the original FORTAN programming language)

All of these "chunks" or lists of instructions are purposeful -- i.e., they do "something". If we were to devise a "name" for what the actions of performing the chunks accomplishes, the name should ALWAYS be a verb. This indicates that if we do what the list (module, procedure, program, function, method or routine) says, doing it is a verb not a noun. Performing the items on the list represents some action -- a verb.

For example, the name for the biscuit recipe above could be "make_biscuits" or "bake_biscuits" NOT biscuits. Biscuits (the noun) is what we get when we are finished performing the verbs on the list for "making_biscuits" or "baking_biscuits".

You will notice that any button or switch that we interact with in the real world always has a label on it which is a "verb":

• ON (turn it on)
• OFF (turn it off)
• REWIND
• PLAY;
• FF (go forward fast)
• PAUSE (wait)

It is the same with programming ideas. Each "chunk of code" performs some action (a verb), thus its name should be a verb.

What would you think would happen if you pressed a button that had labels that are nouns:

• PLANK
• BUCKET
• FRED
• TREE

One might wonder what would happen if you pressed such buttons.

Our purpose here might seem to be just one of clarity. That is true. But more importantly, the "chunking" of instructions is the ONLY way we can deal with complexity.