LaTeX/Algorithms and Pseudocode

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. Put \usepackage{algorithmic} in the preamble to use the algorithmic environment to write algorithm pseudocode (\begin{algorithmic}...\end{algorithmic}). You might want to use the algorithm environment (\usepackage{algorithm}) to wrap your algorithmic code in an algorithm environment (\begin{algorithm}...\end{algorithm}) to produce a floating environment with numbered algorithms.

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 algorithms 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

#include<stdio.h>
i=10;
int main(){
for(i=1 i<10 i++){
   println(i)
 }
}

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 \gets i + 1$
\ENDFOR

While-loops

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

\WHILE{$i \leq 10$}
    \STATE i=i+1;
\ENDWHILE

Repeat until condition

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

Infinite loops

\LOOP <text> \ENDLOOP

Precondition

\REQUIRE <text>

Postcondition

\ENSURE <text>

Returning variables

\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 cannot 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{..}

Compatibility with hyperref

Due to a bug, the algorithmic package is not compatible with hyperref. A workaround is the algorithmic-fix package. Copy the code found on the linked page to a file called algorithmic-fix.sty and include it with \usepackage{algorithmic,algorithmic-fix}. However, if this trick fails, try using \usepackage{hyperref} before using \usepackage{algorithmic}. In this case, you might not even need the algorithmic-fix.sty.

Renaming things: algorithm to procedure, require/ensure to input/output

\floatname{algorithm}{Procedure}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

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 numbering of algorithms can be influenced by providing the name of the document component within which numbering should be recommenced. The legal values for this option are: part, chapter, section, subsection, subsubsection or nothing (default). For example:

\usepackage[chapter]{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

Package page

Package documentation

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

• The official manual for the algorithms package, Rogério Brito (2009), http://mirrors.ctan.org/macros/latex/contrib/algorithms/algorithms.pdf