LaTeX/Algorithms

LaTeX has several packages for typesetting algorithms in form of "pseudocode". They provide stylistic enhancements over a uniform style (i.e., all in typewriter font) so that constructs such as loops or conditionals are visually separated from other text. The pseudocode is usually put in an algorithm environment. For typesetting real code, written in a real programming language, consider the listings package described in Source Code Listings.

Typesetting

There are four notable packages algorithmic, algorithm2e, algorithmicx, and program,

Typesetting using the algorithmic package

The algorithmic package uses a different set of commands than the algorithmicx package. This is not compatible with revtex4-1. Basic commands are:

 \STATE <text>
 \IF{<condition>} \STATE {<text>} \ELSE \STATE{<text>} \ENDIF
 \IF{<condition>} \STATE {<text>} \ELSIF{<condition>} \STATE{<text>} \ENDIF
 \FOR{<condition>} \STATE {<text>} \ENDFOR
 \FOR{<condition> \TO <condition> } \STATE {<text>} \ENDFOR
 \FORALL{<condition>} \STATE{<text>} \ENDFOR
 \WHILE{<condition>} \STATE{<text>} \ENDWHILE
 \REPEAT \STATE{<text>} \UNTIL{<condition>}
 \LOOP \STATE{<text>} \ENDLOOP
 \REQUIRE <text>
 \ENSURE <text>
 \RETURN <text>
 \PRINT <text>
 \COMMENT{<text>}
 \AND, \OR, \XOR, \NOT, \TO, \TRUE, \FALSE

Complete documentation is listed at [2] . Most commands are similar to the algorithmicx equivalents, but with different capitalization. The package algorithms bundle at the ctan repository, dated 2009-08-24, describes both the algorithmic environment (for typesetting algorithms) and the algorithm floating wrapper (see below) which is designed to wrap around the algorithmic environment.

The algorithmic package is suggested for IEEE journals as it is a part of their default style sheet.

How to rename require/ensure to input/output:

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

Typesetting using the algorithm2e package

The algorithm2e package (first released 1995, latest updated July 2017 according to the v5.2 manual) allows typesetting algorithms with a lot of customization. Like algorithmic, this package is also not compatible with Revtex-4.1.

Unlike algorithmic, algorithm2e provides a relatively huge number of customization options to the algorithm suiting to the needs of various users. The CTAN-manual provides a comprehensible list of examples and full set of controls.

Typically, the usage between \begin{algorithm} and \end{algorithm} would be
1. Declaring a set of keywords(to typeset as functions/operators), layout controls, caption, title, header text (which appears before the algorithm's main steps e.g.: Input,Output)
2. Writing the main steps of the algorithm, with each step ending with a \;
This may be taken in analogy with writing a latex-preamble before we start the actual document.

The package is loaded like

\usepackage[]{algorithm2e}

and a simple example, taken from the v4.01 manual, is

\begin{algorithm}[H]
 \KwData{this text}
 \KwResult{how to write algorithm with \LaTeX2e }
 initialization\;
 \While{not at end of this document}{
  read current\;
  \eIf{understand}{
   go to next section\;
   current section becomes this one\;
   }{
   go back to the beginning of current section\;
  }
 }
 \caption{How to write algorithms}
\end{algorithm}

which produces

More details are in the manual hosted on the ctan website.

Typesetting using the algorithmicx package

The algorithmicx package provides a number of popular constructs for algorithm designs. Put \usepackage{algpseudocode} 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 algorithmicx package (remember to add the \usepackage{algpseudocode} 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.

Basic commands have the following syntax:

Statement (\State causes a new line, can also be used in front of other commands)

\State $x\gets <value>$

Three forms of if-statements:

\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. Note that it is \ElsIf and not \ElseIf.

Loops:

\For{<condition>} <text> \EndFor

\ForAll{<condition>} <text> \EndFor

\While{<condition>} <text> \EndWhile

\Repeat <text> \Until{<condition>}

\Loop <text> \EndLoop

Pre- and postcondition:

\Require <text>

\Ensure <text>

Functions

\Function{<name>}{<params>} <body> \EndFunction

\Return <text>

\Call{<name>}{<params>}

This command will usually be used in conjunction with a \State command as follows:

\Function{Increment}{$a$}
    \State $a \gets a+1$
    \State \Return $a$
\EndFunction

Comments:

\Comment{<text>}

Note to users who switched from the old algorithmic package: comments may be placed everywhere in the source; there are no limitations as in the old algorithmic package.

The algorithmicx package allows you to define your own environments.

To define blocks beginning with a starting command and ending with an ending command, use

\algblock[<block>]{<start>}{<end>}

This defines two commands \<start> and \<end> which have no parameters. The text displayed by them is \textbf{<start>} and \textbf{<end>}.

With \algblockdefx you can give the text to be output by the starting and ending command and the number of parameters for these commands. In the text the n-th parameter is referenced by #n.

\algblockdefx[<block>]{<start>}{<end>}
    [<startparamcount>][<default value>]{<start text>}
    [<endparamcount>][<default value>]{<end text>}

Example:

\algblock[Name]{Start}{End}
\algblockdefx[NAME]{START}{END}%
    [2][Unknown]{Start #1(#2)}%
    {Ending}
\algblockdefx[NAME]{}{OTHEREND}%
    [1]{Until (#1)}
\begin{algorithmic}
\Start
    \Start
        \START[One]{x}
        \END
        \START{0}
        \OTHEREND{\texttt{True}}
    \End
    \Start
    \End
\End
\end{algorithmic}

More advanced customization and other constructions are described in the algorithmicx manual: http://mirror.ctan.org/macros/latex/contrib/algorithmicx/algorithmicx.pdf

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

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.14)

\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}

The official manual is located at

http://mirrors.ctan.org/macros/latex/contrib/algorithms/algorithms.pdf

References

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