22
$\begingroup$

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?

$\endgroup$
  • 9
    $\begingroup$ "best" is very subjective, I think you should modify the title and in place of asking for "best" ask for what people do in practice. Maybe something like "how to present algorithms" or "good practices for presenting algorithms". You may also want to be more specific since presenting algorithms: 1. to students in an undergrad class 2. in a textbook 3. in a conference paper are very different tasks. $\endgroup$ – Kaveh Nov 9 '11 at 17:23
  • 1
    $\begingroup$ You may also want to check the relevant sections of Mathematical Writting by Knuth, Larrabee, and Roberts. $\endgroup$ – Kaveh Nov 10 '11 at 15:48
26
$\begingroup$

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.

Borůvka's algorithm

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}
$\endgroup$
  • $\begingroup$ interesting that you use field(record) instead of record[field]. I imagine this is the "$f_j(v)$ is the $j^{th}$ coordinate of $v$" view of the world ? $\endgroup$ – Suresh Venkat Nov 10 '11 at 17:03
  • $\begingroup$ @SureshVenkat: It's how you usually do it in functional languages, and also the notation in TAoCP. (Obviously, I can't know if that's why JɛffE uses this notation.) $\endgroup$ – Radu GRIGore Nov 10 '11 at 17:14
  • 5
    $\begingroup$ The main reason to be careful with pseudo-code is that it is easy to get confused about the algorithm so it is important to emphasize some things. Jeff's example above for Boruvka illustrates this. In the code L is being treated as a set. An edge uv can be the lightest edge incident to u as well as v so it is added twice in the loop but it does not matter if you think of L as a set. However, this is not obvious and some one implementing this can easily be tripped up if they implement L as a list. $\endgroup$ – Chandra Chekuri Nov 10 '11 at 20:04
  • 2
    $\begingroup$ @ChandraChekuri: Yes, implementing sets incorrectly can cause problems in algorithms that manipulate sets. $\endgroup$ – Jeffε Nov 14 '11 at 10:14
  • 1
    $\begingroup$ @SureshVenkat: Oh, that. No, I can't stand it. Bold keywords make the baby Jesus cry. Dijkstra should lose his Turing award for introducing that execrable typographical convention. $\endgroup$ – Jeffε Nov 16 '11 at 13:38
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Me also, but in Ruby. With github gists you can easily share executable snippets for them to play with. gist.github.com/chadbrewbaker/7202412 $\endgroup$ – Chad Brewbaker Nov 17 '13 at 20:18
  • $\begingroup$ Python is however not good to represent linear algebra. Octave is a better fit I think in this case (closer to pseudocode). $\endgroup$ – gaborous May 26 '15 at 23:38
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Just stick to one (per paradigm) that fits your level of abstraction best." I think this is a great advice to find an alternative to pseudocode. There are lots of languages, and almost always there is at least one that target a simple syntax for specific paradigm: Ada for concurrent design, Octave for linear algebra, Python for procedural, NetLogo for multi-agents systems, Prolog for logic, CLIPS for rule-based programming, etc. $\endgroup$ – gaborous May 26 '15 at 23:40
  • $\begingroup$ @gaborous If you can have readable, abstract code -- go for it. Unfortunately, I suspect that this will have you using at least three languages in any larger body of work; that would be unfortunate, too. $\endgroup$ – Raphael May 27 '15 at 6:11
  • $\begingroup$ of course I agree for larger code there's no language, but for small, core algorithms, it's often possible to find a language which is very close to pseudocode. $\endgroup$ – gaborous May 27 '15 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.