Notes on Algorithms

An algorithm is a defined procedure to accomplish a specific task. It must accept input, also known as instances, and transform the input to achieve the desired output. The transformation applied by an algorithm is defined by a series of steps which it must follow. Often, algorithms are used to solve algorithmic problems which can be formally defined as follows:

Problem: <description of the problem>
Input: <data provided to the algorithm>
Output: <what the algorithm must produce>

When creating an algorithm, several goals should be achieved:

It may not always be possible to achieve all these goals simulatenously and, therefore, a balance between them may be required.


Heuristics are used in place of algorithms when it is not possible to achieve the correct output as they can provide approximations. Different heuristics will provide output with varying degrees of correctness and, therefore, the heuristic used for a problem should be selected carefully so that it matches as closely as possible.

Algorithm correctness

To establish the correctness of an algorithm, a goal discussed above, proof is required. To show proof, the following is required:

The following sections will discuss how to achieve each of the parts shown above.

Proof statement

To define the proof statement, i.e. describe the problem, the following parts must be stated:

Two traps are often encountered when defining the proof statement:

A technique to achieving a correct and efficient algorithm is to reduce the set of allowed input.

Chain of reasoning

Several notation methods can be used to show the sequence of steps taken by an algorithm, i.e. show the chain of reasoning. The different notation methods are the following:

These methods describe an algorithm in different ways, i.e. different languages, and have varying degrees of accuracy and ease of understanding. While programming languages have the highest accuracy, they can be the most difficult to understand. On the other hand, English can be easily understood, but, the words used may introduce ambiguity and, therefore, reduce the accuracy of the description. When selecting a notation method, a decision between the level of accuracy and understanding needs to be made.

Proof of incorrectness

Counter-examples are inputs that result in an algorithm producing incorrect output and have the following properties:

When searching for weaknesses in an algorithm, first look at the problem in detail and think about what issues/difficulties may occur when solving. Second, systematically cover all possible inputs, including small, extreme, and tie input.

If incorrectness is not found in an algorithm, proof of the correctness of the algorithm is still required.

Proof of correctness

Mathematical induction is a proof technique which can be used as proof of the correctness of an algorithm. It involves proving a base case and then assuming it is correct up to a value. Induction has the following steps:

Recursion is similar to mathematical induction and has the following steps:

Modeling a problem

Algorithms are designed to work on rigorously defined abstract data structures, discussed below. Therefore, when describing a problem, it must be done abstractly, such that it becomes a sequence of transformations on abstract data structures. The following sections discuss the different abstract data structures that are available.

Combinatorial objects

The following are common data structures:

Recursive objects

Recursion involves the combination of a set of smaller items, resulting in a larger item. The abstract data structures discussed above can be handled recursively, shown below:

Recursive objects require the decomposition rules, and base cases. Decomposition rules describe how a recursive object may be broken down into a smaller object, and is known as the recursive case. Base cases define the smallest object that can be achieved from a recursive object, and results in the decomposition of the object terminating.

Further discussion about recursion can be found on my post Notes on Recursive Algorithms


This post briefly looked at algorithms, firstly what they are and how they can be used to solve problems by transforming given input to a required output. Secondly, how to prove the correctness of an algorithm was discussed, including tools and techniques that can be used. Finally, the reasoning for modeling a problem abstractly so that an algorithm can perform transformations on abstract data structures was presented.

These notes where prepared from the book “The Algorithm Design Manual” by Steven S. Skiena. This book provides an excellent starting point for understanding algorithms and how they work. You can find the book over at the Springer website.