# LaTeX/Algorithms and Pseudocode: Wikis

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

### 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.

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

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

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)

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