Algorithms

Table of contents

  1. Introduction
  2. Reasoning about correctness
    1. Problems and properties
    2. Demonstrating incorrectness
    3. Induction and recursion
    4. Sigma notation
  3. Modelling the problem
  4. Conclusion
  5. References

Introduction

An algorithm is a procedure that takes input and produces output to accomplish a specific task [1, P. 3].

An algorithm should solve a general, well-specified problem. A specification for an algorithm should include the complete set of instances it will operate on, and the algorithm’s output after running on one of these instances [1, P. 3].

A good algorithm is:

  • Correct
  • Efficient
  • Easy to implement

It’s not always possible to meet these goals [1, P. 4].

An algorithm is commonly expressed in one of the following forms:

  1. English
  2. Pseudocode
  3. A programming language

[1, P. 12]

Reasoning about correctness

The most important property of an algorithm is that it’s correct.

One way to demonstrate the correctness of an algorithm is a mathematical proof.

A mathematical proof consists of four parts:

  1. A statement of what you’re trying to achieve
  2. A set of assumptions you take to be true
  3. A chain of reasoning that takes you from the assumptions to the statement you are attempting to prove
  4. A little square (∎) or QED to denote the end of the proof

[1, P. 11]

Problems and properties

In order to demonstrate correctness, your problem must be well-specified.

Problem specifications have two parts:

  1. The set of allowed input instances
  2. The required properties of the algorithm output

[1, P. 12]

You should avoid asking ill-defined questions. Asking “what is the best path?” is ill-defined: what does best mean? You should be more specific, for example: “which is the fastest path to take?” [1, P. 13].

Demonstrating incorrectness

You can prove an algorithm incorrect by providing an input that produces the incorrect output. These are called counter-examples [1, P. 13].

Good counter-examples are verifiable and simple [1, P. 13].

Induction and recursion

Failure to prove an algorithm as incorrect does not make it correct. Mathematical induction is a common method to prove the correctness of an algorithm.

The way to prove a predicate through induction is to:

  • Prove the case
  • Assume that is true
  • Prove

see this video teaching proof by induction for further explanation

Sigma notation

Summations are common in algorithm analysis.

Sigma notation is a way of expressing summation formulas. For example, the sum of 1 to in sigma notation is:

see this video explaining sigma notation for further explanation

Modelling the problem

Modelling is the process of formulating your application in terms of well-defined, well-understood problems. Modelling can eliminate the need to create your own algorithm, since you can rephrase your problem to use a pre-written algorithm [1, P. 19].

Most problems are real-world problems. For example, you might need to create a system to route traffic. Algorithms don’t work on real-world objects, they work abstractions, like a graph. In order to write effective algorithms you must learn how to describe your problems in terms of abstract strictures [1, P. 19].

In order to model a problem, you should have a solid understanding of the data structures available to you.

Conclusion

Algorithms are procedures that accomplish a specific task.

You can determine the correctness of an algorithm using a mathematical proof, one way of doing this is by using mathematical induction.

Algorithms work on abstract objects. In order to write algorithms for real-world problems, you need to model your real-world problems in terms of abstract objects that an algorithm can work on.

References

  1. [1] S. Skiena, The Algorithm Design Manual, 2nd ed. Springer, 2008.