- Reasoning about correctness
- Modelling the problem
An algorithm is a procedure that takes input and produces output that accomplishes 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:
- 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:
- A programming language
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:
- A statement of what you’re trying to achieve
- A set of assumptions you take to be true
- A chain of reasoning that takes you from the assumptions to the statement you are attempting to prove
- A little square (∎) or QED to denote the end of the proof
In order to demonstrate correctness, your problem must be well-specified.
Problem specifications have two parts:
- The set of allowed input instances
- The required properties of the algorithm output
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].
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].
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 (P) through induction is to:
- Prove the case P(0)
- Assume that P(k) is true
- Prove P(k+1)
see this video teaching proof by induction for further explanation
Summations are common in algorithm analysis.
Sigma notation is a way of expressing summation formulas. For example, the sum of 1 to n in sigma notation is:
see this video explaining sigma notation for further explanation
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.
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.
-  S. Skiena, The Algorithm Design Manual, 2nd ed. Springer, 2008.