Executing Algorithms cont.

Observations - Repetition

Again, note that some instructions are executed repeatedly.

Look again at the first algorithm:

  1. Draw a box, label the box A, write the number 1 in box A
  2. Draw a line that values may be written on, label the line Output
  3. If the number in box A is less than or equal to 5 then do the next instruction, otherwise do instruction 7
  4. Write the number in box A on the line labeled Output
  5. Replace the number in box A with the number that is one more than the number currently in box A
  6. Go back and do instruction 3 again
  7. You are done

Instructions 4 and 5 are executed repeatedly.

Instructions 3 and 6 control the repetition.

Observations - Counting

The algorithms seen so far produce (output) a sequence of numbers.

This is a common thing that many more substantial algorithms do as part of their task.

The repetition uses counting. With counting there is a box that contains a number whose value is increased or decreased repeatedly.

The counter is the box that contains the number whose value is increased or decreased repeatedly.

The counter's value is used in determining if the repetition should be done again.

There are three key elements in repetition that uses counting that control the behavior:

  1. The start value given to the counter
  2. The condition, a part of the instruction that determines if statements will be executed again
  3. The modification of the number in the "counter" box.

Here is the first algorithm with the three key elements highlighted:

  1. Draw a box, label the box A, write the number 1 in box A
  2. Draw a line that values may be written on, label the line Output
  3. If the number in box A is less than or equal to 5 then do the next instruction, otherwise do instruction 7
  4. Write the number in box A on the line labeled Output
  5. Replace the number in box A with the number that is one more than the number currently in box A
  6. Go back and do instruction 3 again
  7. You are done

Line 1: The start value for the counter

Line 3: The condition

Line 5: The modification of the counter

New Instruction: Input

We will now do some preliminary, or set-up, instructions prior to executing the steps of the main algorithm.

For example:

  1. Draw a line that values may be written on, label the line Input
  2. On the line labeled Input write the following numbers: 23 7 14 9

The main algorithm will use the values on the Input line.

New Instruction - Group of Boxes

We will now do some different preliminary, or set-up, instructions prior to executing the steps of the main algorithm.

In the previous algorithms each box was separate with name of its own.

We will now use a group of numbered boxes.

For example:

  1. Draw five adjacent boxes and number the boxes 0 though 4
  2. Put the following numbers in boxes 0 - 4, one number per box: 23 7 4 19 2

The main algorithm will use the values in the group of boxes.

Summary of the Algorithms

The above algorithms, by number, accomplished the following:

  1. Output the numbers 1 through 5
  2. Output the odd numbers 1 through 9
  3. Output the numbers 25 20 15 ... 0
  4. Output the squares of the the numbers 1 through 5
  5. Output the sum 1 + 2 + 3 + ... + 5
  6. Output the sum of a sequence of input values
  7. Output the sum of a sequence of values in a group/list/array

Algorithm Notes

Consider the first algorithm that put the values 1 2 3 4 5 on the output line.

It is easy to say "I can write 1 2 3 4 5 quickly without even thinking about it".

What if the the following change was made to algorithm 1:

3. If the number in box A is less than or equal to 1000000 then do the next instruction, otherwise do instruction 7.

That is we want to see 1 2 3 4 ... 999998 999999 1000000

A person could not do that very quickly.

The output of the values 1 2 3 4 5 in algorithm 1 was simply help illustrate the working of the algorithm.

The idea behind algorithm 1 was used as part of the last algorithm to produce the sequence of box numbers.

Thus algorithm 1 is a building block, a fundamental set of steps that underlies many algorithms.

Consider the next-to-last algorithm that computed the sum of values on the input line or the last algorithm that computed the sum of values in a sequence of numbered boxes.

These algorithms, although basic, are useful. Totals for sales, items consumed, bus riders for the year, etc. will use these sort of algorithms.

A person might say "I can do that in my head".

Consider:

  • What if the input line or the boxes contained the 4 values: 2345642343, 123232122, 32534543, 321199945?
  • What if the input line or the boxes contained 1,000,000 values?

Clearly a person could not do these quickly, if at all.

Algorithms usually take input and produce an output.

For users of an algorithm the algorithm is a black box.

With a black box, the user does not see what's going on inside.

The algorithm is given input and the user sees only the output that is produced.

Why do this?

The instructions were simple, but that is the idea, we want to have a machine do them.

A person must write the algorithm (program) for the machine to carry out so it is necessary for that person to understand how to write algorithms such as these.

We want to be people who can understand and write algorithms and so we study these things.