How to describe an algorithm with mathematical notation?

Question

I often have to create new computer science algorithm. The problem come when I have to describe them in a scientific way. I don't know where I should look for to learn how to describe my algorithms with a mathematical notation. I can do some basic stuff such as describing the different set I use and their relations... but that's all.

So I want to know if there are good book about mathematical description of algorithms. Also, what part of math should a study for that (first order logic, propositionnal logic,?)

Thank you.

Answer 1

If it's truly important to describe the algorithm in mathematical notation, look to Haskell for inspiration. Many Haskell statements can be translated directly into mathematical notation. For example, the definition

fac 0 = 1
fac n = n * fac (n - 1)

is equivalent to the mathematical statements

$$\begin{align*}fac(0) &= 1\\fac(n) &= n\ fac(n - 1)\ (\operatorname{if} n \ne 0).\end{align*}$$

In practice, however, what you really want is usually to write algorithms precisely, with mathematical terminology. In order to accomplish this, it is essential to practice doing so, and to ask other people for feedback. You can't learn to play the piano by reading books about it, nor can you learn piano while wearing earmuffs. Look at examples, too; every time you look at an example and think "oh, what a good idea!", you've learned something.

Really, I don't know of any better ways to learn this. Think of an algorithm, and try to write it down in a way that a mathematician would understand. Ask a mathematician if they understand. If not, figure out why. Repeat.

Answer 2

The "gold standard" for rigorous mathematical descriptions of algorithms is (arguably) the book "Introduction to Algorithms," sometimes known as "CLRS" after the initials of each of the four authors, though on occasion I've heard it referred to as just "Cormen" (the primary author.)

The trick (as you can see in Amazon's "Look Inside," for instance on page 18 where "insertion sort" is described) is the use of a well-defined pseudocode.

Why is it that pseudocode is so much better suited for a precise description of an algorithm than mathematical notation?

My opinion: Because most mathematics (the maths you would generally refer to as "maths") is for indicating relations or comparisons or existences. This is fundamentally different from indicating steps or actions or instructions.

In fact, Donald Knuth is his multi-volume opus "The Art of Computer Programming," doesn't use any special notation at all for his descriptions of algorithms. They are for the most part described in plain English. He does make use of a few conventions, but if you skip over all prefaces and notes on conventions and go straight to the actual algorithms themselves you will find them quite readable.

---

In summary, I think you should differentiate between conveying an algorithm to your readers, and analyzing an algorithm in some formal sense. The latter may require mathematics and notation; the former only requires that you communicate clearly and describe precisely and unambiguously. In short, it requires a good mastery of the language with which you intend to communicate (which is probably English.)