Sorting Algorithms: Introduction
(Up to Basic Computer Science : Lists and Arrays)

Sorting has been analyzed by computer scientists for decades, and thus it is an ideal subject to begin with when studying computer science. Sorting is done with algorithms, which are a set of specific commands that are followed in a certain order to complete a task. A cooking recipe is an algorithm, but we usually reserve the word algorithm for mathematics or science related topics.

To study sorting, you must first be comfortable with iteration and recursion. These two terms designate the ways tasks are repeatedly performed. A jolly old programmer might give you this definition of recursion:

re-cur-sion (ri-'ker-zhen) n See recursion.

If you don't know what iteration and recursion are and how they are different, look up a book on a common programming language like C++ and it should tell you. Or, you can go to Cprogramming.com, which has tutorials on C++ with a section on recursion.

Note: in most of these algorithms, two elements of an array are often switched. So, to make the algorithms easier to read, we have written a function called swap() which takes two variables and exchanges the values in them. Here is the function code in C++:

inline int swap( int &x, int &y )

{

  int z = x;

  x = y;

  y = z;

}

Note as well that we are using C++. For all the example code in this site, we will be using C++, for it is a widely used and taught language that is efficient and suitable for our purposes.

The basic sorting algorithms are mostly iterative, and thus probably easier to understand.

The most simple algorithm, but not the most intuitive algorithm, is Bubble sort. This sort is still used a lot because it is easier and shorter to type than the other sorts.

The most intuitive algorithm is Selection Sort. Humans use this sort all the time when sorting objects. This algorithm is especially useful when sorting across a network.

Radix Sort (also known as Bin Sort) is a fairly fast sort that uses digits of numbers to sort arrays. Because of this, however, Radix Sort is fairly specialized, and makes it difficult to write general purpose code.

A very important sorting algorithm is Insertion Sort. This sort may not seem important, but it is used a surprising amount because it works well with almost sorted arrays.

One of the advanced sorting algorithms is the Heap Sort, which is based on the Heap Tree. You should read the two essays on Data Trees and Heap Trees before you attempt to read about this sort.

Bubble Sort
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

Bubble Sort is by far the simplest and shortest of all the sorting algorithms. Here is the code for it:

( About Example C++ code )

// By convention, 'n' is usually the size of the

// array to be sorted.

void bubblesort( int array[], int n )

{

  for ( int i = 0; i <>

    for ( int j = 1; j <>

      if ( array[j-1] > array[j] )

        // Note the use here of swap()

        swap( array[j-1], array[j] );

}

You can see why we call this a short algorithm. Even though it's short, I will explain it anyway.

Basically, this algorithm goes through the entire array and compares every adjacent pair of elements in the array starting from the first and working towards the last. This cycle is repeated over and over until the entire array is sorted.

Notice that at the end of each cycle, the last element, and then the next to last element, and so on is in place. Thus, the cycle is shortened by one element each time so that we don't have to bother with the last elements which are already in place.

Let us walk through this algorithm on an example: 3 2 5 4 1. Note that n = 5.

First Iteration ( i = 0 ): We are considering the array 3 2 5 4 1.

( j = 1 ): 3 > 2, so swap() and the array is now 2 3 5 4 1.
( j = 2 ): 3 <>, so nothing happens and the array is still 2 3 5 4 1.
( j = 3 ): 5 > 4, so swap() and the array is now 2 3 4 5 1.
( j = 4 ): 5 > 1, so swap() and the array is now 2 3 4 1 5.

j is no longer strictly less than n - i, so we are finished with the First Iteration.

Second Iteration ( i = 1 ): We are now considering the array 2 3 4 1. (Not the last one, remember? n - i = 4, so we only consider the first 4 elements.)

( j = 1 ): 2 <>, so nothing happens and the array is still 2 3 4 1.
( j = 2 ): 3 <>, so nothing happens and the array is still 2 3 4 1.
( j = 3 ): 4 > 1, so swap() and the array is now 2 3 1 4.

j is no longer strictly less than n - i, so we are finished with the Second Iteration.

Third Iteration ( i = 2 ): We are now considering the array 2 3 1.

( j = 1 ): 2 <>, so nothing happens and the array is still 2 3 1.
( j = 2 ): 3 > 1, so swap() and the array is now 2 1 3.

j is no longer strictly less than n - i, so we are finished with the Third Iteration.

Fourth Iteration ( i = 3 ): We are now considering the array 2 1.

( j = 1 ): 2 > 1, so swap() and the array is now 1 2.

j is no longer strictly less than n - i, so we are finished with the Fourth Iteration.

Now i is no longer strictly less than n-1, so we are finished sorting.

Now that you have seen the entire sorting process written out, the algorithm will make more sense to you.

One of the problems with Bubble Sort is that even when the array is fully sorted, the sort continues. This problem, however, is easily remedied: just insert a boolean flag that keeps track of whether or not the sort called swap() on anything in the last iteration. If it did not, then the sort has finished early.

Still, improving the efficiency of the Bubble Sort algorithm is really quite a useless effort. If you want more efficiency, use another algorithm. The reason for using Bubble Sort is because it is easy to type, so making Bubble Sort more complex is not really all that appealing.

If you would like a usable version of the Bubble Sort algorithm, there is one below that uses templates. The only efficiency improvement to Bubble Sort is the early exit flag, since that does not add much length to the code.

Selection Sort
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

Selection Sort is the sort used most often by humans, since it's makes a lot of sense. The algorithm is simple:

Let's say you are sorting some index cards labeled with numbers, and you want to order them smallest to largest. Here are the index cards:

4, 3, 1, 5, 2

Scan the list and find the smallest. This is, of course, 1. Put that into the first position, switching it wih 4. We now have this:

1, 3, 4, 5, 2

Now, we can ignore the 1 and concentrate on the other 4 numbers. Now, we find the next smallest number (which is 2), and move it to the second position. Then we do this for the third smallest, and so on. We keep following this process until we have what we wanted: a sorted list.

On the computer, this algorithm can be consolidated into this form:

For every n, ranging from 1 to the size of the array, start at the nth element of the array and find the smallest element. Switch this element with the nth element of the array.

The concept is quite simple, and therefore makes the algorithm quite easy to program. Even though Selection Sort is one of the slower algorithms, it is used because it sorts with a minimum of data shifting. That is, the algorithm doesn't swap the elements of the array as many times as other algorithms do in order to sort the array. This is really useful when you're programming over a network, because sometimes transferring data can be really slow and time consuming.

Although you should be able to easily program your own version of this simple algorithm, you can study and use the commented version we have in our files:

Radix Sort, Part 1
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

[Part 1] [Part 2]

Radix Sort is a clever and intuitive little sorting algorithm. Radix Sort puts the elements in order by comparing the digits of the numbers. I will explain with an example.

Consider the following 9 numbers:

493 812 715 710 195 437 582 340 385

We should start sorting by comparing and ordering the one's digits:

Notice that the numbers were added onto the list in the order that they were found, which is why the numbers appear to be unsorted in each of the sublists above. Now, we gather the sublists (in order from the 0 sublist to the 9 sublist) into the main list again:

340 710 812 582 493 715 195 385 437

Note: The order in which we divide and reassemble the list is extremely important, as this is one of the foundations of this algorithm.

Now, the sublists are created again, this time based on the ten's digit:

Now the sublists are gathered in order from 0 to 9:

710 812 715 437 340 582 385 493 195

Finally, the sublists are created according to the hundred's digit:

At last, the list is gathered up again:

195 340 385 437 493 582 710 715 812

And now we have a fully sorted array! Radix Sort is very simple, and a computer can do it fast. When it is programmed properly, Radix Sort is in fact one of the fastest sorting algorithms for numbers or strings of letters.

Insertion Sort
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

Insertion Sort, like Selection Sort, is a fairly intuitive algorithm. Insertion Sort's advantages lie in that it works really well with almost sorted arrays. In the non-computer world, it is often used by card players sorting cards that are dealt one at a time.

Imagine that you have the following 5 cards dealt to you in this order (we only care about the numbers, so we'll ignore the suits): 3, 2, 4, 5, 1.

First, we're dealt the card with the 3 on it. Then, we're dealt the 2, which is inserted before the 3. Then, we're dealt the 4 and the 5, both of which are put at the end. When we are given the 1, it is inserted before the 2. Now, we've been dealt five cards, and so the hand been sorted.

Of course, when we are sorting an array, we don't get the elements one at a time. Instead, we get them all at once, but we can still visualize them as if we are being given them one at a time. We just ignore the elements that haven't been "dealt" to us yet.

Here's another example: let's sort this list: 3, 5, 7, 2, 8, 1, 9, 0, 4, 6.

The sort goes something like this:

Notice that the numbers that have been "dealt" are always in order..

Easy and simple, right? Well, the way the computer does Insertion Sort isn't quite so simple.

The computer begins with the new card at the end and swaps it backwards until it is in the correct location. So, the card with the 1 would have to be swapped 4 times. This method becomes extremely long in certain cases, such as when the list begins completely backwards (5, 4, 3, 2, 1). That particular formation is the worst case scenario, and for that, Insertion Sort is very, very slow.

So, a man by the name of Shell created a sorting algorithm called the Diminishing-Increment Insertion Sort, also known simply as Shell Sort. Mr. Shell tried to get the benefits of Insertion Sort without the drawbacks. Unfortunately, Mr. Shell's Sort is far from being the fastest algorithm, and it is more complex than Insertion or Selection Sort.

Still, for most cases, Insertion Sort is much faster than Selection Sort, and it is not very complicated to type, so it is used often in various computer science projects.

There is a nicely commented, usable version of Insertion Sort that you can download at our site:

Heap Trees, Part 2
(Up to Basic Computer Science : Data Trees)

[Part 1] [Part 2]

Heap sort is one of the fastest sorting algorithms, rivaling such speed-demons as Quicksort and mergesort. The advantages of heap sort are that it does not use recursion and that heap sort works just as fast for any data order. That is, there is basically no worst case scenario.

First, since the heap we just implemented is an array, you can just convert the array into a heap with the following algorithm: (refer back to the code structure on the previous page)

• Call shiftDown() on the parent of the last element. (Halfway back, remember?)
• Moving left, keep calling shiftDown() of the parent of the next to last element and so on until the end of the level is reached.
• Move up a level, and keep calling shiftDown() on the parent node in the same way.
• Keep repeating the second and third step until you've called shiftDown() on the root node.

Basically, since the heap is an array at heart anyway, you just call shiftDown() on the parent of the last child or pair of children, and then keep working your way left across the array, calling shiftDown() on each element.

Now that you have a legitamate heap, you can sort it back into an ordered array. Heap sort works from back to front; it starts with the last element of the sorted array and then steadily works towards the front. Just keep calling remove() and storing the data from back to front until the heap is empty.

Even though this sounds a bit repetative, it really is quite fast, especially for large numbers of elements. Sometimes, it can be faster than Quicksort or mergesort just because the heap sort is not recursive. Although on average heap sort is slower than Quicksort and mergesort, heap sort is more consistent in its speed. Thus, in applications where timing may be crucial, heap sort is preferred to Quicksort.

The heap tree and heap sort should be much easier to implement than the binary search tree. Just follow the guidelines established above, and the programming shouldn't trouble you much. The description page for the source code file will explain how the heap sort is implemented in the code.

Learn Basic Algorithms and Data Structures

There are a variety of important algorithms and data structures that are the lingua franca of computer science. Everyone needs to know what a <>or binary tree is because they get used all the time. Perhaps just as important are fundamental algorithms like binary search, graph searching algorithms, sorting algorithms, and tree-based searches such as minimax. These algorithms and their variants show up a lot, and people will generally expect that any computer scientist will understand how they work.

Learn Basic Theory

There are a couple of things you should definitely be aware of: you should understand how to represent numbers in different bases and how to manipulate boolean expressions using boolean logic. Both of these tools will come in handy in a variety of circumstances, especially when reading other people's code or trying to clarify your own. (Boolean logic is especially useful for formulating clear conditional statements.)

Even more important, you should have a good sense of the limits of current computers. In particular, it really helps to understand the ideas in algorithmic efficiency and Big-O notation. Knowing these topics makes it clearer why certain programs and algorithms will take a very long time to run, and how to spot them. It also makes it signifcantly easier to optimize your program when you know which algorithms to choose.

Finally, it's useful to have a sense of the absolute limits of what computers can do; it turns out that there are just some things that are not possible for a computer to do. Sometimes it can be tempting to try to write a program that does just that!

Understanding Different Base Systems

This essay is targeted at new students of computer programming or computer science who want to understand how base two (binary), base eight (octal), and base sixteen (hexadecimal) work.

First of all, it's important to realize that each of these base systems is just another way of writing down the same number. When you convert a number between different bases, it should still have the same value. In this essay, when I want to refer to the actual value of a number (regardless of its base), I'll do it in base 10 because that's what most people are used to.

It's generally easiest to understand the concept of different bases by looking at base 10. When we have a number in base 10, each digit can be referred to as the ones digit, tens digit, the hundreds digit, the thousands digit, or so forth. For instance, in the number 432, 4 is the hundreds digit, 3 is the tens digit, and 2 is the ones digit.

Another way to think about this is to rewrite 432 as

  4 x 102 

+ 3 x 101

+ 2 x 100

Each digit is multiplied by the next power of ten. Numbers in other bases, such as base 16, are merely numbers where the base is not ten! For instance, we could interpret 432 as though it were in base 16 by evaluating it as

  4 x 162 

+ 3 x 161

+ 2 x 100

This would be the same as the number 1074 in base 10.

So to convert a number from a given base into base 10, all we need to do is treat each place as a power of the given base times the value of the digit in that place. Note that customarily for a given base, only digits from 0 to the base minus one are used. For instance, in decimal, we only use the digits 0 through 9. That's because we don't need any more digits to express every possible number. (But we do need at least that many; if we only had 8 digits, how would we ever express the value 9?)

Now, bases greater than 10 will require more than 10 possible digits. For intsance, the number 11 in base ten can be expressed in base 16 with only a single digit because the ones place in base 16 can range from 0 to 15. Since we only have 10 digits, the letters A through F are used to stand for the "digits" 10 through 15. So, for instance, the hexadecimal number B stands for the decimal number 11.

Bases less than ten will require fewer digits--for instance, binary, which works using powers of two, only needs two digits: one and zero. The binary number 1001, for instance, is the same as writing

1 * 23

1 * 22

1 * 21

1 * 20

which comes out to the decimal value 9.

Numbers written in octal use a base of 8 instead of 2 or 16. See if you can figure out what the number 20 written in octal would be in base ten.

Because octal, hexadecimal, and decimal numbers can often share the same digits, there needs to be some way of distinguishing between them. Traditionally, octal numbers are written with a leading 0; for instance, 020 is the same thing as the number 20 in base 8. Hexadecimal numbers are written with the prefix of "0x". So 0x20 would be the number 20 in base 16; we'd interpret it the same as the decimal number 32.

Converting from decimal to octal or hexadecimal

It turns out that when you wish to convert from decimal to octal or hexadecimal, there is a very easy formula that you can use. I'll give you the one for octal, and let you puzzle out the hexadecimal version (which may come quite naturally to some of you).

To convert from octal to hexadecimal, all you need to do is group the binary digits into pairs of three and convert each one into the corresponding octal number. For instance, given the binary number 010011110, you would group 011 and 110 together. 010 is 2, 011 is 3 and 110 is 6. So the octal number is 0236.

So why exactly does this work? Well, let's take a look at what 011110 looks like:

  0 * 28

  1 * 27

  0 * 26

  0 * 25

+ 1 * 24

+ 1 * 23

+ 1 * 22

+ 1 * 21

+ 0 * 20

That's actually the same as

  0 * 22 * 26

+ 1 * 21 * 26

+ 0 * 20 * 26

+ 0 * 22 * 23

+ 1 * 21 * 23

+ 1 * 20 * 23

+ 1 * 22 * 20

+ 1 * 21 * 20

+ 0 * 20 * 20

Whoa! First, notice that the far right column is actually turning into powers of 8! 2³ is 8, and 2⁶ is 64! So this means for each group of three digits, we have the base increasing by a factor of 8. Moreover, look at the right hand column. It can sum up to at most 7 (since 2⁰ + 2¹ + 2² = 1 + 2 + 4 and the binary digit just decides whether each power of two is included into the sum or not). That's exactly the same as having eight digits, 0 through 7, and once we sum them all together, we multiply the sum by a power of eight. That's just the same as making each group of three binary digits an octal digit!

Knowing this, can you come up with the way to do the same thing for hexadecimal numbers?

Efficiency and the Space-Time Continuum
(Up to Basic Computer Science)
Get Printable Version

A lot of computer science is about efficiency. For instance, one frequently used mechanism for measuring the theoretical speed of algorithms is Big-O notation. What most people don't realize, however, is that often there is a trade-off between speed and memory: or, as I like to call it, space and time.

Think of space efficiency and time efficiency as two opposite ends on a band (a continuum). Every point in between the two ends has a certain time and space efficiency. The more time efficiency you have, the less space efficiency you have, and vice versa. The picture below illustrates this in a simple fashion:

Algorithms like Quicksort and Mergesort are exceedingly fast, but require lots of space to do the operations. On the other side of the spectrum, Bubble Sort is exceedingly slow, but takes up the minimum of space.

Heap Sort, for instance, has a very good balance between space and speed. The heap itself takes up about the same space as an array, and yet the speed of the sort is in the same order of magnitude as Quicksort and Mergesort (although it is slower on average than the other two). Heap Sort has the additional benefit of being quite consistent in its speed, so it is useful in programs where timing is crucial (i.e. networks).

For data trees, 2-3 trees and 2-3-4 trees are faster and more balanced than the normal binary search trees, but they take up an extraordinary amount of space because they usually have tons of unused variables lying around.

The Red-Black tree is a compromise between space and time. The Red-Black tree is basically a binary tree representation of a 2-3-4 tree, and so it takes up less space than the 2-3-4 tree (it doesn't have all of those empty fields), but it still retains the search efficiency of the 2-3-4 tree!

Thus, there has to be a balance in the space and time aspects of computing. Most of the research in Computer Science these days is devoted to Time efficiency, particularly the theoretical time barrier of NP-Complete problems (like the Traveling Salesman Problem). These days memory is cheap, and storage space almost seems to be given away.

With networking and robotics, however, the necessity of a balance becomes apparent. Often, memory on these machines is scarce, as is processing power. Memory has to be used conservatively, otherwise the network servers could become stalled until the operation is finished. Robots often have to function with the limited resources installed on their own structures, and thus many times they do not have the memory to be spared for vast computing speed. In these situations, a compromise must be made.

With networking, this issue becomes mainly about topology. Network Topology is basically a description of how the physical connections of a network are set up. Maybe you know the term "daisy chain": that is a kind of network topology. A daisy chain (in which all computers are connected to two others in one chain) uses the minimum of cables, but the relative speed of the connections is smaller, because if the computer on one end tries to send a signal to a computer at the other end, it must first go through every computer in between. On the other hand, if every computer were connected to every other computer (called a "fully connected mesh network"), signals would be fast, but you would use a lot more cables, and the network may become hard to maintain. So, in this case, space correlates to the number of connections in a network, while time refers to the speed that signals travel the network.

Thus, although it may seem a trivial issue, it is really quite important, even now, to have efficiency in both space and time. Of course, the type of compromise made depends on the situation, but generally, for most programmers, time is of the essence, while for locations in which memory is scarce, of course, space is the issue. Maybe someday we'll be able to find algorithms that are extremely efficient in both speed and memory, bridges in the Space-Time continuum.

Parallel Algorithm Design

The parallel algorithm for a given problem attempts to divide it into sub-problems which can then be solved concurrently on the different processors of a parallel computer.

The design of a parallel algorithm can be viewed as consisting of four stages - Partitioning, Communication Analysis, Granularity Control and Mapping. The following simple example illustrates some of the issues involved in each of the stages.

Consider the following scenario: n answer-scripts have to be marked, each of which contains the answers to m questions. The scripts could be viewed as the data, and the marking process itself as the computation to be performed on it.

In order to design a parallel solution to this problem, it must first be decomposed into smaller tasks which can be executed simultaneously. This is referred to as the partitioning stage.

This can be done in one of two ways. Each script could be marked by a different marker - this would require n markers. Alternatively, marking each question could be viewed as a task. This would result in m such tasks, each of which could be tackled by a separate marker, implying that every script passes through every marker.

In the first approach, the data (scripts) is first decomposed and then the computation (marking) is associated with it. This technique is called domain decomposition.

In the second approach, the computation to be performed (marking) is first decomposed and then the data (scripts) is associated with it. This technique is called functional decomposition. The partitioning technique that will be chosen often depends on the nature of the problem.

Suppose one needs to compute the average mark of the n scripts. If domain decomposition was chosen, then the marks from each of the markers would be required. If the markers are at different physical locations, then some form of communication is needed, in order to obtain the sum of the marks.

The nature of the information flow is specified in the communication analysis stage of the design. In this case, each marker can proceed independently and communicate the marks at the end. However, other situations would require communication between two concurrent tasks before computation can proceed.

It may be the case that the time to communicate the marks between two markers is much greater than the time to mark a question. In which case, it is more efficient to reduce the number of markers and have a marker work on a number of scripts, thereby decreasing the amount of communication.

Effectively, several small tasks are combined to produce larger ones, which results in a more efficient solution. This is called granularity control. For example, k markers could mark n/k scripts each. The problem here is to determine the best value of k.

The mapping stage specifies where each task is to execute. In this example, all tasks are of equal size and the communication is uniform, so any task can be mapped to any marker. However, in more complex situations, mapping strategies may not be obvious, requiring the use of more sophisticated techniques.

Parallel algorithm design is an interesting and challenging area of computer science which requires a combination of creative and analytical skills.

Recursion

A definition is said to be recursive if the name of the concept being defined recurs within its definition. Put in other words, a process or a function is recursive if it can re-activate itself. You can find out about recursion here.

An unusual use of recursion in a definition comes from Professor Seymour Papert, Professor of Media Technology, at MIT (The Massachusetts Institute of Technology) and the inventor of the graphical programming language LOGO. Here are Papert's instructions on how to make a circle. First, take a step forward, then turn a little to the right, then make a circle. His description is a very unusual one because it describes a circle as a process rather than as a static geometric shape. His description is recursive because making a circle is defined in terms of making a circle. Recursion is often used to define functions.

Factorial

The factorial of a number n, written n!, is the product of the numbers between it and zero. A function to compute factorials can be defined like this.

0! = 1
n! = n * (n - 1)!

You can use the function below.

Fibonacci

In the fibonacci sequence, each number is the sum of its predecessors. The first two numbers are both one. The fibonacci function is defined like this.

fib(0) = 1
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

You can use the function below.

Greatest Common Divisor

Just to emphasize that recursion is not a new idea, here is a method for calculating the greatest common divisor [or highest common factor] of two numbers. The method was invented by the Greek mathematician Euclid of Alexandria who lived between [approximately] 330BC and 275BC.

gcd(x, y) = y, if x is zero
gcd(x, y) = gcd(y, x), if y < x
gcd(x, y) = gcd(y mod x, x), otherwise

You can use this function below.

Prime Factors

The function for finding the prime factors of a number n is relatively straightforward.

1. If n is even, one factor is 2, then find the prime factors of n/2.

2. If n is divisible by 3, remove this factor and then find the prime factors of the remainder.

3. If n is divisible by 5, remove this factor and then find the prime factors of the remainder.

4. If n is divisible by 7, remove this factor and then find the prime factors of the remainder.

5. ...

It might seem that we must first calculate the prime numbers so that we may perform steps 2, 3 and subsequently. In fact, just using the odd numbers will be enough since an apparent factor of 15 will be removed as a factor of 3 and a factor of 5. Our recursive definition uses two functions.

pfr(n) = 2 and pfr(n/2), if n is even
pfr(n) = pf(n, m), if n is odd

The pf function uses m as the odd number counter.

pf(1, m) = none
pf(n, m) = n, if n < m²
pf(n, m) = m and pf(n/m, m), if m divides n
pf(n, m) = pf(n, m + 2), otherwise

You can use the function below.

Base conversion

To convert a number from one base to another is simple if the number can be represented as a single digit; you simply write down the digit. If the number cannot be represented in a single digit then divide by the base, convert the result to the other base and after it simply write down the digit which represents the remainder, even if the remainder is zero. You can try this below. You can enter bases such as those shown below but the method described above cannot be used to calculate unary representations.

• Enter 01 for binary (Base 2);
• Enter 012 for ternary (Base 3);
• Enter 01234567 for octal (Base 8);
• Enter 0123456789ABCDEF for hexadecimal (Base 16).

Recursion

A definition is said to be recursive if the name of the concept being defined recurs within its definition. Put in other words, a process or a function is recursive if it can re-activate itself. You can find out about recursion here.

An unusual use of recursion in a definition comes from Professor Seymour Papert, Professor of Media Technology, at MIT (The Massachusetts Institute of Technology) and the inventor of the graphical programming language LOGO. Here are Papert's instructions on how to make a circle. First, take a step forward, then turn a little to the right, then make a circle. His description is a very unusual one because it describes a circle as a process rather than as a static geometric shape. His description is recursive because making a circle is defined in terms of making a circle. Recursion is often used to define functions.

Factorial

The factorial of a number n, written n!, is the product of the numbers between it and zero. A function to compute factorials can be defined like this.

0! = 1
n! = n * (n - 1)!

You can use the function below.

Fibonacci

In the fibonacci sequence, each number is the sum of its predecessors. The first two numbers are both one. The fibonacci function is defined like this.

fib(0) = 1
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

You can use the function below.

Greatest Common Divisor

Just to emphasize that recursion is not a new idea, here is a method for calculating the greatest common divisor [or highest common factor] of two numbers. The method was invented by the Greek mathematician Euclid of Alexandria who lived between [approximately] 330BC and 275BC.

gcd(x, y) = y, if x is zero
gcd(x, y) = gcd(y, x), if y < x
gcd(x, y) = gcd(y mod x, x), otherwise

You can use this function below.

Prime Factors

The function for finding the prime factors of a number n is relatively straightforward.

1. If n is even, one factor is 2, then find the prime factors of n/2.

2. If n is divisible by 3, remove this factor and then find the prime factors of the remainder.

3. If n is divisible by 5, remove this factor and then find the prime factors of the remainder.

4. If n is divisible by 7, remove this factor and then find the prime factors of the remainder.

5. ...

It might seem that we must first calculate the prime numbers so that we may perform steps 2, 3 and subsequently. In fact, just using the odd numbers will be enough since an apparent factor of 15 will be removed as a factor of 3 and a factor of 5. Our recursive definition uses two functions.

pfr(n) = 2 and pfr(n/2), if n is even
pfr(n) = pf(n, m), if n is odd

The pf function uses m as the odd number counter.

pf(1, m) = none
pf(n, m) = n, if n < m²
pf(n, m) = m and pf(n/m, m), if m divides n
pf(n, m) = pf(n, m + 2), otherwise

You can use the function below.

Base conversion

To convert a number from one base to another is simple if the number can be represented as a single digit; you simply write down the digit. If the number cannot be represented in a single digit then divide by the base, convert the result to the other base and after it simply write down the digit which represents the remainder, even if the remainder is zero. You can try this below. You can enter bases such as those shown below but the method described above cannot be used to calculate unary representations.

• Enter 01 for binary (Base 2);
• Enter 012 for ternary (Base 3);
• Enter 01234567 for octal (Base 8);
• Enter 0123456789ABCDEF for hexadecimal (Base 16).

Systems Administration

Most modern computing facilities are based on a wide variety of different hardware, ranging in size from portable PCs to powerful workstations and servers. These machines are usually interconnected as part of a complex network with many different protocols and software packages used to provide the required services. The job of integrating, developing and managing these complex systems is called Systems Administration.

Some typical questions that might concern a systems administrator include:

• With 400 software packages on the system, there will be constant changes and updates required. How can we arrange for 300 machines to always have the same up-to-date version?
• In a network of several hundred machines, there will nearly always be at least one machine which is down. How can we be sure that this doesn't always disrupt hundreds of other machines on the network?
• How can we ensure that valid users have easy access to information on the network, while still keeping this information secure against unauthorised access?
• If it takes one person to install and maintain a single machine, how can we avoid requiring 300 people to install and maintain 300 machines?
• How can we arrange for a user to log on to any one of hundreds of machines and still have access to the same files and programs?
• How can we design the network so that tens of extra machines can be easily added without overloading, or requiring a major re-configuration, of existing systems?

More information about the departmental systems is available here. A good starting point for further information on Systems Administration in general, is the web page for the Systems Administrators Guild (SAGE).

Virtual Reality

Virtual reality (VR) is a technology which allows users to participate in, and interact with, a 3D computer-generated world, or virtual environment (VE). In essence, VR aims to provide a new and more natural means of Human-Computer Interaction.

How Does It Work?

There are two flavours of virtual reality: Desktop and Immersive. Desktop VR simply requires a standard computer monitor to display the 3D world, e.g. popular games on the PC like Doom, Descent etc. can be considered Desktop VR because they allow the player to explore and interact within a 3D environment.

By comparison, Immersive VR requires the use of special display devices to make the user feel more enclosed in the virtual environment. We can do this by either making the displays much bigger (e.g. projection screen systems) or by bringing the displays closer to the eyes (e.g. head-mounted displays, like the one opposite).

We may also use new input devices to allow the user to interact with the world in a natural manner. For example, the person on the right is using a glove device so that they can directly manipulate and select objects in the virtual environment with their hands.

In order to use the head-mounted display to look inside a virtual world, or a glove to interact with that world, we need some form of tracking technology which can monitor 6 degrees of freedom. That is, track the position (x,y,z) and orientation (yaw,pitch,roll) of your head or hand in 3D space. With this information, the computer knows when you move your body part and can update the image of the virtual world accordingly.

What Is VR Used For?

VR arguably provides the most natural means of communicating with a computer because it allows us to use our inherent 3D spatial skills that have evolved over thousands of years (such as walking, gesturing, looking, grabbing etc.) There is a therefore a vast range of potential applications for VR. Below is a small cross-section of some of the uses which VR technology has already been used for:

• Architectural Design: Architects can now use VR technology to designing and walking through a building or room. E.g. here is the UNC Walkthrough Project .
• Art: VR is a new medium for artists to express their visions. For example, take a look at the VR-ART Virtual Gallery .
• Education: Systems have been designed to help disabled children, allow the visualisation of mathematical concepts, perform virtual lectures & conferences etc. For example, here is the Virtual Reality and Education Laboratory and the VIRART Educational Applications of VR page.
• Medicine: There is much interest in the possibility of for virtual surgery and the provision of other aids for the surgeon, e.g. in the fields of ultrasonic imaging, MRI, drug design etc. For example, how do you fancy attending the Virtual Clinic ?
• Training: VR can be used to safely train personnel for high-risk activities. For example, VR technology was used by NASA for their Hubble Space Telescope Repair Training System .
• Scientific Visualisation: Scientific visualisation is the use of computers to understand complex phenomenon. For example, manipulating and viewing complex molecules or computational fluid dynamics models. E.g. click here to see the NASA Ames' Virtual Windtunnel .
• Entertainment: There are of course a number of VR games available in arcades and for your home computer. Here is the Atlantis VR Entertainment Resource Guide .
• Virtual Prototyping: Creating a computer-generated prototype is quicker, cheaper and also easier to modify. The Virtual Manufacturing project at Bath University is an example of this.
• VRML: The Virtual Reality Modeling Language (VRML) is a developing standard for describing interactive 3D scenes delivered across the Internet. Click here for the VRML Repository .

If you want to find more information about virtual reality on the World Wide Web, then you can take a look at Toni Emerson's Internet Resources in Virtual Reality .