Lecture 18

Algorithms

Algorithms are fundamental to computer science. An algorithm is an abstract description of a how a task is to be accomplished. Algorithms are independent of hardware and programming language.
 

Describing Algorithms

Using English

English is good for many things but expressing algorithms is not one of them.

Using a Real Programming Language

Not a bad idea, but an algorithm should be independent of any specific language

Using Pseudocode

Pseudocode is a type of simple imaginary programming language, you can make up new extensions to the language and don't need to worry about where to put semicolons.

Sequence, Selection and Iteration.

A sequence is a series of operations to be performed one after the other. In C, sequences are enclosed in {}.

A selection is a way of choosing between two of more sequences, based on a condition. In C, selection is achieved using:
 
 

or the switch construct.

Iteration is the repetition of a sequence. In C, this is achieved using while and for loops.

Surprisingly, these three forms are sufficient for constructing any algorithm. If it is possible to construct an algorithm to describe a particular process then such an algorithm can be constructed from sequence, selection and iteration alone.

Example:

Find the factorial of a number.

n factorial (n!) is defined as the product of all the positive integers up to and including n, 0! is defined as 1. The factorial of a negative number is undefined.
 
 

Where := means "is defined as". This can be evaluated by the following algorithm (expressed in C).
 
Functions using only sequence, selection and iteration are called iterative.

Recursion

Another way of describing the factorial function is: or This is called a recursive definition because it is defined in terms of itself. A recursive definition consists of two parts - the end or terminating case (also called the anchor or base) and the recursive or general case. The end case usually gives a value for a specific argument; this allows the recursion to terminate eventually. For example: Here, the definition of fact(0) is used to terminate the recursion.

A non-mathematical example of a recursive definition is that of ancestor.
 
 

The following uses a recursive definition of the factorial function:
 

Comparing this with the iterative version, we see that the recursive version seems more natural and straightforward. It is also more readable.

However, the iterative version will execute faster and use up less storage space.

The reason for this is that, for each recursive call, the arguments and local variables must be saved (by pushing them onto a stack). So, for example, the call factorial(10) will generate 10 recursive calls to factorial. When a call is completed, the arguments and local variables from the calling function must be popped from the top of the stack. All this pushing and popping takes time and occupies storage.

Often it is necessary to choose between a simple, compact and natural recursive algorithm and an iterative one which runs faster and uses less space but is less readable and more difficult to develop.

Using recursion is also appropriate when the data structure to be manipulated is defined recursively. An example of such a structure,is a binary tree. To search a binary tree we used a recursive function.

The Towers of Hanoi.

A classic example from the world of recursion is the towers of Hanoi problem. The problem is to move a pile of disks from one of three pins to another. What is the sequence of moves for a certain number of disks?

This is an example of a problem that is very difficult to solve by iteration. Call the pins A,B and C where A is the start pin and C is the end pin.

Suppose there is just one disk. This can be moved directly from A to C. Next suppose there are three disks on A. Suppose we can transfer the top two disks from A to B using C. We can then move the third disk from A to C. It remains only to transfer the two disks from B to C using A.

We have thus reduced the problem to transferring two disks from one pin to another. This in turn can be reduced to moving one disk from one pin to another, which we know how to do. The recursive solution for n disks is
 
 

The following is a C function for this operation.
void transfer(int n, char start, char end, char work)  {
  if (n > 0)  {
    transfer(n-1, start, work, end);
    printf("Move disk from %c to %c\n",start, end);
    transfer(n-1, work, end, start);
  }
}
When called as: The function prints: