Algorithms

Recall the dictionary definition of algorithm:

algorithm - An algorithm is a procedure for solving a mathematical problem in a finite number of steps that frequently involves the repetition of an operation,
or more broadly, a step-by-step method for accomplishing some task.

Note:

  • An algorithm is comprised of a number of operations.
  • The operations must be carried out by someone or something.

Formal definition

Algorithm - An algorithm is a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.

Note that this definition gives requirements "a step-by-step method for accomplishing some task" must be fulfilled to be an algorithm.

Breaking this apart we have,

  • well-ordered collection -
    we always know what task to do next,
    no: start over (where?), or do either this or that (how do we decide?).
  • of unambiguous (operations) -
    an operation which can be directly carried out with no explanation required. These are called primitive operations.
  • and effectively computable operations -
    operations the computing agent can successfully complete ("do-able" operations),
    ex. not do-able: find the exact value of pi cannot be done, tell someone to flap their arms real hard and fly, compute 5/0
  • produces a result -
    must produce an observable result, sometimes there is no answer,
    ex. an algorithm the lists all integers between two given integers. What if the given integers are 2 and 3?
  • halts in a finite amount of time -
    Clearly a sequence of operations that doesn't complete in a finite amount of time is not going to accomplish anything.

Computing Agent

Q: What actually executes an algorithm?
A: Generically it is a computing agent that executes an algorithm.

Computing agent - A computing agent is a machine, robot, person, etc. that can carry out the steps (operations, instructions) of an algorithm.

Thus the operations that comprise an algorithm may be carried out by anything that is capable of executing the operations the algorithm requires.

Primitive Operations

The computing agent thus must be able to perform the operations an algorithm uses.

The operations that a computing agent can directly execute are called the primitive operations of the computing agent.

The actual primitive operations operations that are available depends on the computing agent.

An algorithm instruction is comprised of one or more primitive operations.

Variables

An algorithm will often need to keep track of some information in carrying out its steps.

Variable - A variable is a named storage location that can hold a single data value. When it is given a new data value the old data value is discarded.

The labeled boxes that have been used in the algorithms we have seen are variables.

These variables are not exactly like the variables of algebra.

A variable in algebra represents one or more "unknown" values. For example:

3x - 4 = 5

A variable used in an algorithm is a name that represents a value.

When a variable name occurs in algorithm the variable's current value is used.

So far single letters have been used for variable names.

Variables are usually given names that describe the purpose of the value stored in the variable's storage location.

Primitive Operations Used in the Algorithms We Have Seen

Recall the following typical algorithm from the executing algorithms notes:

  1. If there are no numbers on the Input line do instruction 2, otherwise do instruction 3.
  2. You are done
  3. Draw a box, label the box S, write the number 0 in box S
  4. Draw a box, label the box X write the number 999 in box X
  5. Draw a line that values may be written on, label the line Output
  6. If there are still numbers on the line labeled Input then do the next instruction, otherwise do instruction 10
  7. Replace the number in box X with the the next number on the line labeled Input, erase from the Input line the number that was copied to box X
  8. Replace the number in box S with the sum of the number that is currently in box S plus the number in box X
  9. Go back and do instruction 6 again
  10. Write the number in box S on the line labeled Output
  11. You are done

Some instructions are very similar. Some differ only the a box name, for example.

List the primitive operations a computing agent must be able to perform to execute the above algorithm.

The computing agent must be able to:

  • Draw a box, label the box, write a number in the box
  • Arithmetic, put a calculated value in a specified box
  • Compare numbers for less than, etc.
  • Get input (and consume/remove it after it has been received)
  • Determine if there is any input
  • Write output

Also, manage the execution:

  • Go to the next instruction
  • Go to a specified instruction
  • Quit executing instructions

Categories of Instructions

Examine the instructions, try to generalize the similar instructions.

Would it make sense to have categories of instructions?

If yes, what might the categories be?

There are three categories of instructions used in constructing algorithms:

  1. Sequential instructions .
    A single task is carried out and then it is the turn of the next task in the sequence (ordered list).
  2. Repetition instructions.
    These instructions allow groups of other instructions to be repeated.
  3. Conditional instructions.
    If a specified "condition" is true an instruction is performed, otherwise the instruction is skipped.
    This allows certain instructions to be performed conditionally, that is, when certain conditions are true.

Conditional Instruction - Example

Assume the variables Count, Total, and Average exist.

  1. If the value in the box labeled Count is greater then 0 do the next instruction, otherwise do instruction 4
  2. Replace the value in the box labeled Average with the value in the box labeled Total divided by the value in the box labeled Count
  3. Go to instruction 5.
  4. Write on the output line "Cannot compute the average"
  5. ...

For the algorithm from above:

  • Identify the variables.
  • Identify the sequential, repetition, and conditional instructions.
  1. If there are no numbers on the Input line do instruction 2, otherwise do instruction 3.
  2. You are done.
  3. Draw a box, label the box S, write the number 0 in box S
  4. Draw a box, label the box X write the number 999 in box X
  5. Draw a line that values may be written on, label the line Output
  6. If there are still numbers on the line labeled Input then do the next instruction, otherwise do instruction 10
  7. Replace the number in box X with the the next number on the line labeled Input, erase from the Input line the number that was copied to box X
  8. Replace the number in box S with the sum of the number that is currently in box S plus the number in box X
  9. Go back and do instruction 6 again
  10. Write the number in box S on the line labeled Output
  11. You are done

Expression of Instructions

The algorithms seen so far have been expressed in pseudocode.

Pseudocode is a notation resembling a programming language but not intended for actual execution by a computer.

With pseudocode the computing agent is usually a human being.

Since the computing agent for pseudocode is a human being it is very flexible.

The only requirement for pseudocode is that the human who is reading it understands the intent of the pseudocode author.

Pseudocode is often used to express algorithms informally. This is because:

  • Pseudocode is clearer than natural language
  • Pseudocode does not require the details that an actual programming language requires

How important is the exact phrasing of the instructions?

Would it be possible to change the phrasing of any of the instructions but not change the behavior of the algorithm?

Consider different ways to express the instruction 8 from the above algorithm:

8. Replace the number in box S with the sum of the number that is currently in box S plus the number in box X

Other equivalent ways to express the instruction:

Set the value of box S to the sum of the value of box S plus value of box X

Set box S to the sum of box S plus box X

Set S to the sum S + X

S = S + X

A number of programming languages use notation like the last of the above versions.

Although the last version is terse what should happen when it is executed is known, that is what is necessary.

Simple Pseudocode Example

Rewrite the first example from the executing algorithms notes in a simpler version of pseudocode.

  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

Simple Pseudocode Example - Solution 1

  1. Set the value of A to 1
  2. While the value of A is less than or equal to 5 do the next instruction
  3. Output the value of A
  4. Add one to the value of A
  5. Go back and check the repetition condition again
  6. Done

Write an even simpler version of the original algorithm.

Simple Pseudocode Example - Solution 2

  • Set A to 1
  • While A <= 5
  •     Output the value of A
  •     Set A to A + 1
  • Done

Note that the indentation indicates the instructions that are to be executed repeatedly.

Exercise: Write pseudocode to output the even numbers from 0 through 100 inclusive.

Categories of Instructions Notes

Sequential instructions are the default but by using conditional and repetition instructions the sequential carrying out of instructions is altered.

Repetition instructions allow for the going back, and the repeating of, certain instructions.

Conditional instructions allows instructions to be carried out "conditionally", that is when specified conditions are true, otherwise the instructions are skipped.

Another "instructions", not mentioned here, is sub-task. With sub-task a separate group of instructions is carried out and when done execution resumes at the point where is left off to do the sub-task.