LaTeX/Algorithms

From Wikibooks, open books for an open world
Jump to: navigation, search
LaTeX logo.svg

LaTeX

Getting Started
  1. Introduction
  2. Installation
  3. Installing Extra Packages
  4. Basics

Common Elements

  1. Document Structure
  2. Text Formatting
  3. Paragraph Formatting
  4. Colors
  5. Fonts
  6. List Structures
  7. Special Characters
  8. Internationalization
  9. Rotations
  10. Tables
  11. Title creation
  12. Page Layout
  13. Importing Graphics
  14. Floats, Figures and Captions
  15. Footnotes and Margin Notes
  16. Hyperlinks
  17. Labels and Cross-referencing

Mechanics

  1. Errors and Warnings
  2. Lengths
  3. Counters
  4. Boxes
  5. Rules and Struts

Technical Texts

  1. Mathematics
  2. Advanced Mathematics
  3. Theorems
  4. Chemical Graphics
  5. Algorithms
  6. Source Code Listings
  7. Linguistics

Special Pages

  1. Indexing
  2. Glossary
  3. Bibliography Management
  4. More Bibliographies

Special Documents

  1. Letters
  2. Presentations
  3. Teacher's Corner
  4. Curriculum Vitae

Creating Graphics

  1. Introducing Procedural Graphics
  2. MetaPost
  3. Picture
  4. PGF/TikZ
  5. PSTricks
  6. Xy-pic
  7. Creating 3D graphics

Programming

  1. Macros
  2. Plain TeX
  3. Creating Packages
  4. Themes

Miscellaneous

  1. Modular Documents
  2. Collaborative Writing of LaTeX Documents
  3. Export To Other Formats

Help and Recommendations

  1. FAQ
  2. Tips and Tricks

Appendices

  1. Authors
  2. Links
  3. Package Reference
  4. Sample LaTeX documents
  5. Index
  6. Command Glossary

edit this boxedit the TOC

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. For typesetting real code, written in a real programming language, consider the listings package described in Source Code Listings.

Typesetting using the algorithmic package[edit]

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
 \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.[1]

Typesetting using the algorithm2e package[edit]

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

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 algorihtm, 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

Latex-algorithm2e-if-else.png

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

Typesetting using the algorithmicx package[edit]

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.

Latex-algorithmic-if-else.png

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.

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

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

Custom algorithmic blocks[edit]

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

The algorithm environment[edit]

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[edit]

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[edit]

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[edit]

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}


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://mirrors.ctan.org/macros/latex/contrib/algorithms/algorithms.pdf


Typesetting using the program package[edit]

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}

LaTeX program package example01.png

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

References[edit]

  1. [1]
  2. http://tex.stackexchange.com/questions/70181/revtex4-1-and-algorithm2e-indentation-clash


Clipboard

To do:
write more and add some pictures for example code; how to generate pngs?

answer: just take a screenshot and crop


Previous: Chemical Graphics Index Next: Source Code Listings