Good practices for writing algorithms

Question

This is about how effectively we can express an algorithm at hand. I need this for my undergraduate teaching.

I understand there is no such thing as standard way of writing a pseudo code. Different authors follow different conventions.

It would be helpful if people here point out, the way they follow and think the best one.

Is there any book that deals with this in a good detail?

Answer 1

Writing pseudocode is like writing code: It's not particularly important which standard you follow, as long as you (and the people you write with) actually follow some standard.

But for the record, here's the idiosyncratic standard I use in my lecture notes, research papers, and upcoming book.

• Use standard imperative syntax for control flow and memory access — if, while, for, return, array[index], function(arguments). Spell out "else if".

  • But use $field(record)$ instead of record.field or record->field

• Use standard mathematical notation for math — Write $xy$ instead of x*y, $a\bmod b$ instead of a%b, $s\le t$ instead of s <= t, $\lnot p$ instead of !p, $\sqrt{x}$ instead of sqrt(x), $\pi$ instead of PI, $\infty$ instead of MAX_INT, etc.

  • But use $x\gets y$ for assignment, to avoid the == problem.

  • But avoid notation (and pseudocode!) entirely if English is clearer.

    • Symmetrically, avoid English if notation is clearer!

• Minimize syntactic sugar — Indicate block structure by consistent indentation (à la Python). Omit sugary keywords like "begin/end" or "do/od" or "fi". Omit line numbers. Do not emphasize keywords like "for" or "while" or "if" by setting them in a different typeface or style. Ever. Just don't.

  • But typeset algorithm names and constants in \textsc{Small Caps}, variable names in italic, and literal strings in sans serif.

  • But add a small amount of vertical "breathing" space (\\[0.5ex]) between meaningful code chunks.

• Don't specify unimportant details. If it doesn't matter what order you visit the vertices, just say "for all vertices".

For example, here is a recursive formulation of Borůvka's minimum spanning tree algorithm. I've previously defined $G / L$ as the graph obtained from $G$ by contracting all edges in the set $L$, and Flatten as a subroutine that removes loops and parallel edges.

I use my own lightweight algorithm LaTeX environment to typeset pseudocode. (It's just a tabbing environment inside an \fbox.) Here's my source code for Borůvka's algorithm:

\begin{algorithm}
	\textul{$\textsc{Borůvka}(G)$:}\+
\\	if $G$ has no edges\+
\\		return $\varnothing$\-
\\[0.5ex]
	$L \gets \varnothing$
\\	for each vertex $v$ of $G$\+
\\		add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
	return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}

Answer 2

I tend to use something resembling Python syntax. Python is close enough to pseudocode already that in some cases my pseudocode can shade into being actual working code.

Answer 3

If you want to have definite code (i.e. little to no math, close to real programming) you might want to consider to have code that actually compiles. This has several advantages:

• You get syntax highlighting everywhere.
• Compiler checks syntax for you and enforces consistency.
• You can unit-test your implementations to improve code quality.
• You can run the algorithm and compare measured runtimes to analyses (thusly motivating advanced analysis techniques).

A professor at my university does this in his algorithms course. His language of choice is Modula. I don't think the particular choice of language matters, though. Just stick to one (per paradigm) that fits your level of abstraction best.