Pseudocode: A LATEX Style File for Displaying Algorithms

1 pseudocode : A LATEX Style File for KreherDepartment of Mathematical SciencesMichigan Technological UniversityHoughton, MI StinsonDepartment of Combinatorics and OptimizationUniversity of WaterlooWaterloo ON, N2L IntroductionThis paper describes a LATEX environment namedpseudocodethat can beused for describing Algorithms in pseudocode form. This is the Style usedin our textbookCombinatorial Algorithms : Generation, Enumeration andSearch[2]. The Style available for free downloadingfrom the web ~ package is quite easy to use, and allows Algorithms to bedescribedin a LATEX document using a natural Pascal-like syntax. In the remainingsections of this note, we describe how to use thepseudocodeenvironmentand we present some examples. Readers familiar with LATEX (see [3]) shouldbe able to easily customize the Style file to include additional desired requires thefancyboxpackage by Tim-othy Van Zandt.

2 This package is described in Section of [1]. Otherenvironments for describing Algorithms includealg,algorithmic,newalgandprogram. These Style files, as wellfancybox, are all available from theCTAN web ThepseudocodeEnvironmentWithin thepseudocodeenvironment, a number of commands for popularalgorithmic constructs are available. In general, the commands providedcan be nested to describe quite complex is invoked as follows:\begin{ pseudocode }{<Name>}{<Parameters>} pseudocode constructs\end{ pseudocode }The argument<Name>is the name of the algorithm, and<Parameters>isa list of parameters for the algorithm. For example, the commands\begin{ pseudocode }{CelsiusToFahr enheit}{c}f \GETS {9c/5} + 32\\\RETURN{f}\end{ pseudocode }produce the following output when included in a LATEX document:Algorithm :CelsiusToFahrenheit(c)f 9c/5 + 32return(f)Notice that the command\GETS produces a left arrow, which we useto indicate an assignment of a variable.

3 The user could use instead someother symbol, if desired. For example,\GETS could be replaced by=, as isdone in the C programming Thebegin-endConstructTo form compound statements from simple statements, thebegin-endcon-struct is used as follows:\BEGIN some statement\\another statement\\yet another statement\ENDThis generates the following: some statementanother statementyet another statement2 The effect of this construct is to group a collection of statements using aleft brace bracket of the appropriate the sections that follow we will use the notation<stmt>to indicatea simple statement or a compound statement. Note that the contents ofstatements are typeset in math mode. Therefore, non-math mode text mustbe enclosed in an\mbox{}.Observe that the double backslash\\plays the same role as the semi-colon in Pascal, , it is used to separate statements, andshould neverappear before\ Theif-then-elseConstructTheif-then-elsec onstruct takes various forms, such as the following:\IF <condition> \THEN <stmt>\IF <condition> \THEN <stmt> \ELSE <stmt>\IF <condition> \THEN <stmt> \ELSEIF <stmt> \THEN <stmt>Note that there is no limit placed on the number of\ELSEIFs that may beused in anif-then-elseconstruct.

4 For example, the commands:\IF some condition is true\THEN\BEGIN some statement\\another statement\\yet another statement\END\ELSEIF some other condition is true\THEN\BEGIN some statement\\another statement\\yet another statement\END\ELSEIF some even more bizarre condition is met\THENdo something else\ELSEdo the default actionswould produce the following output:3ifsome condition is truethen some statementanother statementyet another statementelse ifsome other condition is truethen some statementanother statementyet another statementelse ifsome even more bizarre condition is metthendo something elseelsedo the default TheforLoopTheforloop takes the following forms:\FOR <var> \GETS <lower> \TO <upper> \DO <stmt>\FOR <var> \GETS <upper> \DOWNTO <lower> \DO <stmt>\FOREACH <condition> \DO <stmt>For example,\FOR i \GETS 0 \TO 10 \DOsome processingproducesfori 0to10dosome processingand\FOREACH x \in \mathcal{S} \DOsome processingproducesfor eachx Sdosome ThewhileLoopThewhileloop takes the following form:\WHILE <condition> \DO <stmt>For example,4\WHILE some condition holds \DOsome processingproduceswhilesome condition holdsdosome Therepeat-untilLoopTherepeat-untilloop takes the following form.

5 \REPEAT <stmt> \UNTIL <condition>For example,\REPEAT some processing\UNTIL some condition is metproducesrepeatsome processinguntilsome condition is Main Programs and ProceduresWe can describe a main program that calls one (or more) procedures asfollows:\begin{ pseudocode }{<Name>}{<Parameters>}\PROCEDURE{<ProcedureName>}{<ProcedureParameters>}some stuff\ENDPROCEDURE\MAIN some stuff\\\CALL{<ProcedureName>}{<ActualParameters}>\\more stuff\ENDMAIN\end{ pseudocode }Here is a simple example to illustrate the use of a main program callinga procedure. The commands5\begin{ pseudocode }{TemperatureT able}{lower, upper}\PROCEDURE{CelsiusToFahrenheit}{c} f \GETS {9c/5} + 32\\\RETURN{f}\ENDPROCEDURE\MAINx \GETS lower \\\WHILE x \leq upper \DO\BEGIN\OUTPUT{x, \CALL{CelsiusToFahrenheit}{x}}\\x \GETS x+1\END\ENDMAIN\end{ pseudocode }produce the following output:Algorithm :TemperatureTable(lower, upper)procedureCelsiusToFahrenheit(c)f 9c/5 + 32return(f)mainx lowerwhilex upperdo output(x,CelsiusToFahrenheit(x))x x+ CommentsA comment statement may be inserted in an algorithm using thefollowingcommand:\COMMENT{<stmt>}For example, the commandsA \GETS B\\\COMMENT{Now increment the value of $A$}\\A \GETS A+1produce the output6A BcommentNow increment the value ofAA A+ 1 Note that comments are assumed to be text.

6 Thus, in order to includemathematical expressions in a comment, math mode must be used Other Predefined KeywordsSeveral other predefined keywords are available. We summarize their usagein Table 1: Other Predefined Keywordscommandoutput\LOCAL{list of variables}locallist of variables\GLOBAL{list of variables}globallist of variables\EXTERNAL{list of procedures}externallist of procedures\RETURN{list of values}return(list of values)\OUTPUT{list of values}output(list of values)\EXIT exit\ANDand\ORor\NOTnot\TRUE true\FALSE false\GETS Also note that all of the keywords\IF,\WHILE,\CALL{}{},\NOT, available for use outside of thepseudocodeenvironment, but they mustbe input in math mode. For example,The $\WHILE$ loop is our is our Statement NumberingStatements can be numbered and given a reference key so that they can bereferenced in a LATEX document using a\ref{}command (see section [3]).

7 This is done as follows:7\STMTNUM{<space>}{<key>}The argument<space>is the amount of space to be left between the textand the statement number. This is a length that is specified bythe user, andgenerally will require some experimentation in order for itto look nice. Theargument<key>is the reference key used in the LATEX \ref{}commandto refer to the given default numbering for statements is arabic. However, itcan bechanged by a suitable\renewcommand{}. An example is provided in thenext An exampleThe following example demonstrates the use of thepseudocodeenviron-ment to describe a complete algorithm, the familiar mergesort LATEX input\renewcommand{\thepseudonum}{\roman {pseudonum}}\begin{ pseudocode }{MergeSort }{n,X}\label{MergeSort}\COMMENT{Sort the array $X$ of length $n$}\\\IF n=2 \THEN\BEGIN\IF X[0]>X[1] \THEN\BEGINT \GETS X[0]\\X[0]\GETS X[1]\\X[1]\GETS T\END\END\ELSEIF n>2 \THEN\BEGINm\GETS \lfloor n/2 \rfloor\\\FOR i\GETS 0 \TO m-1 \DO A[i] \GETS X[i]\\\FOR i\GETS m \TO n-1 \DO B[i] \GETS X[i]\\\COMMENT{Now sort the subarrays $A$ and $B$}\\\CALL{MergeSort}{m,A}\\\CALL{Merge Sort}{n-m,B}\\i\GETS 0\\j\GETS 0\\\FOR k \GETS 0 \TO n-1 \DO\BEGIN\IF A[i] \leq B[j] \THEN8\BEGINX[k]\GETS A[i]

8 \STMTNUM{1in}{ }\\i\GETS i+1\END\ELSE\BEGINX[k]\GETS B[j] \STMTNUM{ }{ }\\j\GETS j+1\END\END\END\end{ pseudocode }produces the following output:Algorithm :MergeSort(n, X)commentSort the arrayXof lengthnifn= 2then ifX[0]> X[1]then T X[0]X[0] X[1]X[1] Telse ifn >2then m n/2 fori 0tom 1doA[i] X[i]fori mton 1doB[i] X[i]commentNow sort the subarraysAandBMergeSort(m, A)MergeSort(n m, B)i 0j 0fork 0ton 1do ifA[i] B[j]then X[k] A[i](i)i i+ 1else X[k] B[j](ii)j j+ 1 The counterpseudonumkeeps track of the statement numbers. Thestyle of the counter values can be changed using the method described inSection of [3]. For example, we used the command9\renewcommand{\thepseudonum}{\ro man{pseudonum}}in our example so that statements were numbered with lowercase Romannumerals. We also assigned a label to the algorithm using the\label{}command that is described in Section of [3].

9 Finally, by trial and error,we determined spacing so that the statement numbers would now give an example of how the numbered statements in the abovealgorithm can be referenced in a LATEX document. The commandsOn lines (\ref{ }) and (\ref{ }) of Algorithm\ref{MergeSort}, we determine the $k$th element of thesorted the following output:On lines (i) and (ii) of Algorithm , we determine thekth element of thesorted FramingThepseudocodeenvironment also has an optional parameter,<frame>.The complete form of thepseudocodeenvironment is\begin{ pseudocode }[<frame>]{<Name>}{<Parameters>} pseudocode constructs\end{ pseudocode }The possible values of<frame>are:shadowbox doublebox ovalbox Ovalboxframebox plain ruled displayThe values ending with box draw various types of frames around thealgorithm.

10 The valueplainis the default and adds no frame to the algo-rithm. The valuedisplayis used for Displaying sections of code withoutthe algorithm name or parameters. Here are some examples with input:\begin{ pseudocode }[<frame>]{SquareAndMultiply}{x,b,n}\COMMENT{ Compute $x^b \pmod{n}$}\\z\GETS 1\\\WHILE b > 0 \DO\BEGINz \GETS z^2 \pmod{n} \\\IF b\mbox{ is odd}10\THEN z \GETS z \cdot x \pmod{n} \\b \GETS \CALL{ShiftRight}{b}\END\\\RETURN{z}\end { pseudocode }where we give<frame>each of the values described <frame>isshadowboxwe obtain:Algorithm :SquareAndMultiply(x, b, n)commentComputexb(modn)z 1whileb >0do z z2(modn)ifbis oddthenz z x(modn)b ShiftRight(b)return(z)When<frame>isdoubleboxwe obtain:Algorithm :SquareAndMultiply(x, b, n)commentComputexb(modn)z 1whileb >0do z z2(modn)ifbis oddthenz z x(modn)b ShiftRight(b)return(z)When<frame>isovalboxwe obtain:11 Algorithm.