Introduction to Algorithms/What is an Algorithm

Objective

Our main objective is to learn what an algorithm is and its basic components/concepts. By the end of this you should be able to recall what an algorithm is and what it does.

Definition of Algorithm

Merriam-Webster Online defines "Algorithm" as " a step-by-step procedure for solving a problem or accomplishing some end, especially by a computer" . The dictionary definition is missing the component that the procedure must be finite, that is, there has to be a condition for the termination of the algorithm.

Examples:

1. One example would be knitting socks.

The first step is to cast on stitches. Step-by-step the rows are knitted, the heel turned, and finally the last row cast off. The algorithm specifies how to do the sock, but each sock knitted is different, as it uses different wool, but all are similar in structure to each other.

2. Another important example would be sorting a hand of cards.

There are multiple ways of doing this, but one method is to take the lowest card and move it to the leftmost (or rightmost) position. Next, find the second lowest card and move it to the second leftmost position. Repeat until the cards are sorted.

Everyday example:

Here is a perhaps slightly whimsical example of an algorithm.

Algorithm for making buttered toast (1.0)

step1: Get a loaf of bread.
step2: Cut one slice from end of the loaf of bread.
step3: Put slice of bread into toaster.
step4: Turn  toaster on.
step5: Wait for toaster to finish.
step6: Put toasted bread onto a plate.
step7: Spread butter on toast.

As can be seen, the algorithm is a set of steps that can be followed in order to achieve a result.

Basic concepts

This simple example already contains many components commonly found in most algorithms:

• Instructions. Instructions are the heart and soul of any algorithm. An algorithm will consist of a series of sub-algorithms, each performing a smaller task. Extracting individual digits from the numbers to be added may well be an entire task in itself. Some instructions, like digit addition, can be considered fundamental instructions which cannot be broken up further; all algorithms can eventually be broken down into these instructions, like objects being composed of atoms.

• Variables. temporary and carry are both temporary values used to store additional information the algorithm needs to function correctly or effectively. Their values can vary as the algorithm progresses, hence their name.

• Conditionals. Some algorithms may need to make a decision somewhere in it. If the sum of the current two digits is 10 or larger, 1 will be carried over to the next digit position, otherwise nothing (ie. zero) is carried. Conditionals allow an algorithm to selectively execute instructions based on certain conditions which must be satisfied.

• Looping. The for each...end for instruction means to run certain instructions for each object in a set, in this case for each digit in a number. This is a special case of looping, the act of repeating a set of instructions while (or until) a goal is reached or a condition is satisfied; in this case while there are digits left (or until there are no digits left). Loops can contain any other instructions, including other loops!

• Subalgorithm. An algorithm may not be able to do all the work on its own. Usually, a large, complex algorithm can be broken up into parts, each perfoming a specific task. Smaller algorithms are easier to reuse, for example the for each ... digit selection algorithm could be reused in subraction, multiplication and division algorithms, and so on. Breaking up algorithms into logical parts also make it easier to analyze their behaviours and properties from a mathematical point of view.

• Performance. While initial algorithms may seem to function, you may discover that they may not be the best choice in the long term. For example, a simple bubble sort may work for a small amount of items, but if you try it on a large amount of data, it will take a massive amount of time. An algorithm with better performance would include the Merge Sort.

Assignments

Your assignment is to create a simple algorithm. If you need help then you can go back and look at the example above of an algorithm.

Completion status: this resource is a stub, which means that pretty much nothing has been done yet.

• Next Lesson
• Course Home Page