Algorithms

Writing Algorithms with Control Structures

Background

Since the invention by Von Neumann of the stored program computer, the ability of computing equipment to alter its behavior, depending on input datai was gradually recognized. Calculating machines had, for some time, been able to perform fixed arithmetic operations on data, but the potential of machines capable of making decisions opened up many new possibililities. Machines that could make decisions were capable of sorting records, tabulating and summarizing data, searching for information, and many more advanced operations that could not even be imagined at the time.

In early programming languages, like Fortran (first invented in 1954), the goto statement allowed the computer to deviate from the sequential execution of the program instructions. The goto statement was recognized to be a very powerful construction, and soon, programs of increasing complexity and power were developed.

However, the increasinging complex code became harder and harder to maintain. Edgar Dijkstra, in 1966, was one of the first persons to recognize that this run away complexity of programs was due to the overuse of the goto statement (Dijkstra, E. W., "Go To Considered Harmful," Communications of the ACM, March 1966). In fact, it was determined shortly thereafter, that the goto statement is not needed at all. This was the birth of the discipline of Structured Programming.

Dijkstra proved that any program that can be written with goto statements could be rewritten using only these constructions:

Sequence

Repetition (Alice Loop and While constructions)

Decision (Alice If/Else construction)

Algorithms

An algorithm is a set of unambiguous steps for solving a problem.
In the years since Dijkstra published his famous paper in 1966, computer scientists have spent a lot of time studying how to write efficient algorithms.
Although the algorithms written today are more complicated than the algorithms that Dijkstra wrote, they still use the same building blocks of sequence, repetition, and decision.
The only truly new construction is Do Together, which is used for performing actions simultaneously in an animation or to perform computations at the same time on multiple processors.
Here is a discussion of these constructions.

Sequence

The sequence construction simply lists statements in order.
Here is an algorithm to bake bread:
The order of the steps matters. Change their order and your bread flop.
Here is an Alice method for a beach chair that requires only sequence:

Repetition

The Loop construction repeats a group of actions a fixed number of times.

For this example atom, use a SphereHighPoly (Local Gallery >> Shapes).

atom.wiggle

The following method uses definite repetition; atom.wiggle is repeated exactly five times.

world.my first method

An atom might keep wiggling until it disappears (decays). During each wiggle an atom decays with probability p, where p is small. The probability that the atom does not decay during a wiggle is 0.95:

world.my first method

The repetition in the previous method is indefinite repetition; the number of repetitions is unpredictable.

The repetition might even repeat forever (until the Alice animation is stopped):

world.my first method

An algorithm from everyday life that uses repetition:
Important: the indentation matters for algorithms; the indented statements after While more dishes show which statements are included in the While loop. The statements "empty sink" and "wipe out sink" are not in the While loop; they are performed only once.

Decision

Decision means choosing between two actions, depending on whether a condition is true or false.

In the following Alice animation, the coach turns left or right, depending on the condition in an If/Else construction:

coach.TurnLeftOrRight

When the condition in the If statement is true, the coach turns left.

When the condition in the If statement is false, the coach turns right.

If the condition is set as in the following example, the coach turns to the left 50% of the time and to the right 50% of the time.

coach.TurnLeftOrRight

Obtain the "choose true 0.5(50%) of the time" expression from the world functions.

Here is another algorithm from everyday life that uses both repetition and decision: