LaTeX/Algorithms and Pseudocode: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Wikibooks

Up to date as of January 23, 2010

From Wikibooks, the open-content textbooks collection

LaTeX has a variety of packages that can help to format algorithms, code, and "pseudocode". These packages provide stylistic enhancements over a uniform style (i.e., typewriter fonts) so that constructs such as loops or conditionals are visually separated from other text.

Typesetting Algorithms

Typesetting using the algorithmic package

The algorithmic environment provides a number of popular constructs for algorithm designs. The command \begin{algorithmic} can be given the optional argument of a positive integer, which if given will cause line numbering to occur at multiples of that integer. E.g. \begin{algorithmic}[5] will enter the algorithmic environment and number every fifth line.

Below is an example of typesetting a basic algorithm using the algorithmic package (remember to add the \usepackage{algorithmic} statement to your document preamble):

\begin{algorithmic}
\IF {$i\geq maxval$}
\STATE $i\gets 0$
\ELSE
\IF {$i+k\leq maxval$}
\STATE $i\gets i+k$
\ENDIF
\ENDIF
\end{algorithmic}


The LaTeX source can be written to a format familiar to programmers so that it is easy to read. This will not, however, affect the final layout in the document.

There are several constructs provided by algorithmic detailed below

Advertisements

Single line statements

\STATE <text>
A simple statement, e.g. for setting a variable
\begin{algorithmic}
\STATE i=0
\end{algorithmic}


would produce
i = 0

If-statements

There are three forms of this construct

\IF{<condition>} <text> \ENDIF
\IF{<condition>} <text> \ELSE <text> \ENDIF
\IF{<condition>} <text> \ELSIF{<condition>} <text> \ELSE <text> \ENDIF
The third form accepts as many \ELSIF{} clauses as required.

For-loops

There are two forms

\FOR{<condition>} <text> \ENDFOR
\FORALL{<condition>} <text> \ENDFOR
A traditional "for" loop. The method of iteration is usually described in the first argument,

e.g.

\FOR{$i = 1$ to 10}
\STATE $i \leftarrow i + 1$
\ENDFOR


While-loops

\WHILE{<condition>} <text> \ENDWHILE

Repeat until condition

\REPEAT <text> \UNTIL{<condition>}

Infinite loops

\LOOP <text> \ENDLOOP

\REQUIRE <text>

\ENSURE <text>

\RETURN <text>

Printing variables

\PRINT <text>
This is included because it is used so frequently it is considered an operation in its own right.

Comments

\COMMENT{<text>}

Note that you can not use \COMMENT as the first statement of any closed structure, such as \IF..\ENDIF, \FOR..\ENDFOR, \FORALL..\ENDFORALL, \WHILE..\ENDWHILE, and \begin{algorithmic}..\end{algorithmic}. An error "LaTeX Error: Something's wrong--perhaps a missing \item" will be reported (It does not make much sense). There are two workarounds:

  1. Use \STATE \COMMENT{<text>}.
2. Use the optional arguments in those closed structures.
For example, \WHILE[<comment-text>]{<condition>}
To use math in comment text, replace $..$ by \ensuremath{..}


The algorithm environment

It is often useful for the algorithm produced by algorithmic to be "floated" to the optimal point in the document to avoid it being split across pages. The algorithm environment provides this and a few other useful features. Include it by adding the
\usepackage{algorithm} to your document's preamble. It is entered into by

\begin{algorithm}
\caption{<your caption for this algorithm>}
\label{<your label for references later in your document>}
\begin{algorithmic}
<algorithmic environment>
\end{algorithmic}
\end{algorithm}


Algorithm numbering

The default numbering system for the algorithm package is to number algorithms sequentially. This is often not desirable, particularly in large documents where numbering according to chapter is more appropriate. The official documentation is not very clear on how to change this, but it can be done by inserting a \numberwithin{} into the preamble:

\usepackage{algorithmic}
\usepackage{algorithm}
\numberwithin{algorithm}{chapter}  % <--- chapter, section etc. depending on what is required


When using hyperref and referencing algorithms latex gives an error: ! Undefined control sequence. <argument> algorithm.\theHalgorithm This can be solved adding at the preamble:

\newcommand{\theHalgorithm}{\arabic{algorithm}}


List of algorithms

When you use figures or tables, you can add a list of them close to the table of contents; the algorithm package provides a similar command. Just put

\listofalgorithms


anywhere in the document, and LaTeX will print a list of the "algorithm" environments in the document with the corresponding page and the caption.

An example from the manual

This is an example taken from the manual (official manual, p.7)

\begin{algorithm}                      % enter the algorithm environment
\caption{Calculate $y = x^n$}          % give the algorithm a caption
\label{alg1}                           % and a label for \ref{} commands later in the document
\begin{algorithmic}                    % enter the algorithmic environment
\REQUIRE $n \geq 0 \vee x \neq 0$
\ENSURE $y = x^n$
\STATE $y \Leftarrow 1$
\IF{$n < 0$}
\STATE $X \Leftarrow 1 / x$
\STATE $N \Leftarrow -n$
\ELSE
\STATE $X \Leftarrow x$
\STATE $N \Leftarrow n$
\ENDIF
\WHILE{$N \neq 0$}
\IF{$N$ is even}
\STATE $X \Leftarrow X \times X$
\STATE $N \Leftarrow N / 2$
\ELSE[$N$ is odd]
\STATE $y \Leftarrow y \times X$
\STATE $N \Leftarrow N - 1$
\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}

More information about all possible commands available at the project page
http://developer.berlios.de/docman/?group_id=3442
The official manual is located at
http://developer.berlios.de/docman/display_doc.php?docid=800&group_id=3442

Typesetting using the program package

The program package provides macros for typesetting algorithms. Each line is set in math mode, so all the indentation and spacing is done automatically. The notation |variable_name| can be used within normal text, maths expressions or programs to indicate a variable name. Use \origbar to get a normal | symbol in a program. The commands \A, \B, \P, \Q, \R, \S, \T and \Z typeset the corresponding bold letter with the next object as a subscript (eg \S1 typesets {\bf S$_1$} etc). Primes work normally, eg \S‘‘.

Below is an example of typesetting a basic algorithm using the program package (remember to add the \usepackage{program} statement to your document preamble):

\begin{program}
\mbox{A fast exponentiation procedure:}
\BEGIN %
\FOR i:=1 \TO 10 \STEP 1 \DO
|expt|(2,i); \\ |newline|() \OD %
\rcomment{This text will be set flush to the right margin}
\WHERE
\PROC |expt|(x,n) \BODY
z:=1;
\DO \IF n=0 \THEN \EXIT \FI;
\DO \IF |odd|(n) \THEN \EXIT \FI;
\COMMENT{This is a comment statement};
n:=n/2; x:=x*x \OD;
\{ n>0 \};
n:=n-1; z:=z*x \OD;
|print|(z) \ENDPROC
\END
\end{program}


The commands $$and$$ are redefined to typeset an algorithm in a minipage, so an algorithm can appear as a single box in a formula. For example, to state that a particular action system is equivalent to a WHILE loop you can write:

$$$\ACTIONS A: A \EQ \IF \B{} \THEN \S{}; \CALL A \ELSE \CALL Z \FI \QE \ENDACTIONS$$ \EQT $$\WHILE \B{} \DO \S{} \OD$$$


Dijkstra conditionals and loops:

\begin{program}
\IF x = 1 \AR y:=y+1
\BAR x = 2 \AR y:=y^2
\utdots
\BAR x = n \AR y:=\displaystyle\sum_{i=1}^n y_i \FI

\DO 2 \origbar x \AND x>0 \AR x:= x/2
\BAR \NOT 2 \origbar x    \AR x:= \modbar{x+3} \OD
\end{program}


Loops with multiple exits:

\begin{program}
\DO \DO \IF \B1 \THEN \EXIT \FI;
\S1;
\IF \B2 \THEN \EXIT(2) \FI \OD;
\IF \B1 \THEN \EXIT \FI \OD
\end{program}


A Reverse Engineering Example.

Here's the original program:

\begin{program}
\VAR \seq{m := 0, p := 0, |last| :=  ''};
\ACTIONS |prog|:
|prog| \ACTIONEQ %
\seq{|line| :=  '', m := 0, i := 1};
\CALL |inhere| \ENDACTION
l \ACTIONEQ %
i := i+1;
\IF (i=(n+1)) \THEN \CALL |alldone| \FI ;
m := 1;
\IF |item|[i] \neq |last|
\THEN |write|(|line|); |line| :=  ''; m := 0;
\CALL |inhere| \FI ;
\CALL |more| \ENDACTION
|inhere| \ACTIONEQ %
p := |number|[i]; |line| := |item|[i];
|line| := |line| \concat  '' \concat p;
\CALL |more| \ENDACTION
|more| \ACTIONEQ %
\IF (m=1) \THEN p := |number|[i];
|line| := |line| \concat , '' \concat p \FI ;
|last| := |item|[i];
\CALL l  \ENDACTION
|alldone| \ACTIONEQ |write|(|line|); \CALL Z \ENDACTION \ENDACTIONS \END
\end{program}


And here's the transformed and corrected version:

\begin{program}
\seq{|line| :=  '', i := 1};
\WHILE i \neq n+1 \DO
|line| := |item|[i] \concat  '' \concat |number|[i];
i := i+1;
\WHILE i \neq n+1 \AND |item|[i] = |item|[i-1] \DO
|line| := |line| \concat , '' \concat |number|[i]);
i := i+1 \OD ;
|write|(|line|) \OD
\end{program}


The package also provides a macro for typesetting a set like this: \set{x \in N | x > 0}.

Lines can be numbered by setting \NumberProgramstrue and numbering turned off with \NumberProgramsfalse

Source Code Formatting using the Listings package

(See the Listings package reference page for more information.)

A complete reference manual can be found at http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/listings.pdf

This is a basic example for some Pascal code:

\documentclass{article}
\usepackage{listings}             % Include the listings-package
\begin{document}
\lstset{language=Pascal}          % Set your language (you can change the language for each code-block optionally)

\begin{lstlisting}[frame=single]                % Start your code-block
for i:=maxint to 0 do
begin
{ do nothing }
end;
Write(’Case insensitive ’);
Write(’Pascal keywords.’);
\end{lstlisting}

\end{document}


References

 TODO write more and add some pictures for example code

Advertisements

 Got something to say? Make a comment. Your name Your email address Message