NUS School of Computing
Article Contribution by Assoc Prof Soo Yuen Jien
Introduction: Mysterious Recipe
Let us conduct a little hands-on experiment. Below is a “mysterious recipe” consisting of five steps that requires only simple arithmetic.
If you have followed the steps up to now, then congratulations! You have just successfully followed (“executed”) an algorithm.
An algorithm is simply a set of well-defined steps, which give a desirable result to a problem. As you have experienced above, an algorithm can be followed “blindly”, that is, we can carry out the steps without knowing the wider context. It is hence naturally suitable to be translated into a computer programme. It will probably take 2-3 seconds for a human to carry out one round of the mysterious recipe, but a modern computer can easily perform hundreds of millions of rounds in a second.
In case you are still wondering, the mysterious recipe above calculates the value of Pi. The more rounds you perform, the more accurate (more digits) the result. This algorithm is not particularly efficient as it takes about 500,000 rounds before you get to the accuracy of 5 digits, that is, 3.14159.
Another Introduction: A Mess of Information
Consider the following collection of random numbers:
It will take a little bit of time for us to answer: “What is the third largest number in this collection?” or “How many numbers are smaller than four digits?”. The time needed will be much longer if we have, say, 10000 numbers strewn in a similar fashion. If we take a moment to organise the numbers, say, put them in order:
The same questions can be answered much more efficiently.
In the above toy example, you can easily see the usefulness and power of data organisation. Data structure is essentially a study of various ways we can organise information to facilitate processing and problem solving.