diff options
Diffstat (limited to 'Master/texmf-dist')
| -rw-r--r-- | Master/texmf-dist/doc/latex/clrscode/README.TEXLIVE | 7 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/clrscode/clrscode.pdf | bin | 0 -> 38588 bytes | |||
| -rw-r--r-- | Master/texmf-dist/doc/latex/clrscode/clrscode.tex | 744 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/clrscode/page.tex | 18 |
4 files changed, 762 insertions, 7 deletions
diff --git a/Master/texmf-dist/doc/latex/clrscode/README.TEXLIVE b/Master/texmf-dist/doc/latex/clrscode/README.TEXLIVE deleted file mode 100644 index 183e17fa6ab..00000000000 --- a/Master/texmf-dist/doc/latex/clrscode/README.TEXLIVE +++ /dev/null @@ -1,7 +0,0 @@ -The following files have been removed in the TeX Live installation of -the current package, typically due to duplication, lack of space, or -missing source code. You can find these files on CTAN at - http://mirror.ctan.org/macros/latex/contrib/clrscode -If questions or concerns, email tex-live@tug.org. - - clrscode.pdf diff --git a/Master/texmf-dist/doc/latex/clrscode/clrscode.pdf b/Master/texmf-dist/doc/latex/clrscode/clrscode.pdf Binary files differnew file mode 100644 index 00000000000..4d1009eaa6c --- /dev/null +++ b/Master/texmf-dist/doc/latex/clrscode/clrscode.pdf diff --git a/Master/texmf-dist/doc/latex/clrscode/clrscode.tex b/Master/texmf-dist/doc/latex/clrscode/clrscode.tex new file mode 100644 index 00000000000..e2bb0572474 --- /dev/null +++ b/Master/texmf-dist/doc/latex/clrscode/clrscode.tex @@ -0,0 +1,744 @@ +% $Id$ +% $Log$ + +\documentclass[11pt,mtbold]{article} +\usepackage{mathtime} +\usepackage{clrscode} +\input{page} + +\newcommand{\subheading}[1]{\subsubsection*{#1}} +\newcommand{\clrscode}{\texttt{clrscode}} +\newcommand{\Codebox}{\texttt{codebox}} + +\begin{document} + +\title{Using the \clrscode{} Package in \LaTeXe} +\author{Thomas H. Cormen \\ thc@cs.dartmouth.edu} +\date{June 11, 2003} + +\maketitle + +\section{Introduction} +\label{sec:intro} + +This document describes how to use the \clrscode{} package in +\LaTeXe{} to typeset pseudocode in the style of \textit{Introduction +to Algorithms}, Second edition, by Cormen, Leiserson, Rivest, and +Stein (CLRS) \cite{CLRS01}. You use the commands in the same way we +did in writing CLRS, and your output will look just like the +pseudocode in the text. + +\section{Setup} +\label{sec:setup} + +To get the \clrscode{} package, download +http://www.cs.dartmouth.edu/\~{ }thc/clrscode/clrscode.sty . +To use the package, include the following line in your source file: + +{\small +\begin{verbatim} +\usepackage{clrscode} +\end{verbatim} +} + +\noindent The \clrscode{} package itself includes the line + +{\small +\begin{verbatim} +\usepackage{latexsym} +\end{verbatim} +} + +\noindent This line is necessary in order to get the character $\rhd$ +for comments in pseudocode. Therefore, you will need to have the +\texttt{latexsym} package installed and available on your system. + +\section{Typesetting names} +\label{sec:names} + +Pseudocode in CLRS uses four types of names: identifiers, procedures, +constants, and fixed functions. We provide commands \verb`\id`, +\verb`\proc`, \verb`\const`, and \verb`\func` for these names. Each +of these commands takes one argument, which is the name being typeset. +These commands work both in and out of math mode. When used in math +mode, and when the name given as an argument contains a dash, the dash +is typeset as a hyphen rather than as a minus sign. + +\begin{description} + +\item[Identifiers:] Identifiers are used for variable and attribute +names. When a variable name is just a single letter, e.g., the +identifier $j$ in line~2 of \proc{Insertion-Sort} on page~17, we just +typeset it in math mode: \verb`$j$`. + +Identifiers consisting of two or more letters, e.g., the attribute +\id{length} in the same line of \proc{Insertion-Sort}, should not be +typeset in this way. (See page~51 of Lamport \cite{Lamport93}.) +Although \LaTeXe{} provides the \verb`\mathit` command for typesetting +multiletter identifiers, we use our \verb`\id` command instead: +\verb`\id{length}`. We recommend that you use it, too. Since the +\verb`\id` command may be used both in and out of math mode, the source +text + +{\small +\begin{verbatim} +We use the \id{length} attribute to denote the length of an array, +e.g., $\id{length}[A]$. +\end{verbatim} +} + +\noindent will produce +\begin{quote} +We use the \id{length} attribute to denote the length of an array, +e.g., $\id{length}[A]$. +\end{quote} + +\sloppy + +To see how a dash turns into a hyphen, consider line~3 +of \proc{Max-Heapify} on page~130. Its source contains the text +\verb`$l \leq \id{heap-size}[A]$`, which typesets as $l \leq +\id{heap-size}[A]$. Using \verb`$l \leq \mathit{heap-size}[A]$` would +produce $l \leq \mathit{heap-size}[A]$, with a minus sign rather than +a hyphen in the identifier. + +\fussy + +\item[Procedures:] For procedure names, use the \verb`\proc` command. +It typesets procedure names in small caps, and dashes (which occur +frequently in our procedure names) are typeset as hyphens. Thus, the +source \verb`\proc{Insertion-Sort}` produces \proc{Insertion-Sort}. +Since you can use the \verb`\proc` command both in and out of math mode, +the source text + +{\small +\begin{verbatim} +We call \proc{Insertion-Sort} with an array $A$, so that the +call is $\proc{Insertion-Sort}(A)$. +\end{verbatim} +} + +\noindent will produce +\begin{quote} +We call \proc{Insertion-Sort} with an array $A$, so that the +call is $\proc{Insertion-Sort}(A)$. +\end{quote} + +\item[Constants:] We typeset constants like \const{nil}, \const{true}, +and \const{red} in small caps with the \verb`\const` command, e.g., +\verb`\const{nil}`, \verb`\const{true}`, and \verb`\const{red}`. I +don't think that any of our constants have dashes in them, but the +\verb`\const` command would typeset a dash within a constant name as a +hyphen, so that \verb`$\const{red-and-black}$` will produce +$\const{red-and-black}$. + +\item[Fixed functions:] We typeset the names of fixed functions in +plain old roman with the \verb`\func` command, e.g., \func{level} and +\func{out-degree}. By a ``fixed function,'' we mean a function that +is a specific, given function. For example, the $\sin$ function is +typically typeset in roman; $\sin x$ looks right, but wouldn't +$\id{sin} x$ look strange? Yet, on page~42, $\Theta(g(n))$ looks +right, but $\Theta(\textrm{g}(n))$ would look wrong, since $g$ is a +variable that stands for any one of a number of functions. + +As with the other commands for names, a dash within a function name will +typeset as a hyphen, so that \verb`$\func{out-degree}$` will produce +$\func{out-degree}$ rather than $\textrm{out}-\textrm{degree}$. Note +that \LaTeXe{} provides commands for many fixed functions, such as +$\sin$ and $\log$; Table 3.9 on page~44 of~\cite{Lamport93} lists +these ``log-like'' functions. + +\end{description} + +There is one other command that doesn't really fit anywhere else, so +I'll mention it here. We denote subarrays with the ``$\twodots$'' +notation, which is produced by the \verb`\twodots` command. Thus, the +source text \verb`$A[1 \twodots j-1]$` will produce $A[1 \twodots +j-1]$. The \verb`\twodots` command must be used in math mode. + +\section{The \Codebox{} environment} +\label{sec:codebox} + +We typeset pseudocode by putting it in a \Codebox{} environment. A +\Codebox{} is a section of code that will not break across pages (I +hope). + +\subheading{Contents of a \Codebox{}} + +Each procedure should go in a separate \Codebox{}, even if you have +multiple procedures appearing consecutively. The only possible reason +I can think of to put more than one procedure in a single \Codebox{} +is to ensure that the procedures appear on the same page. If you +really need your procedures to appear on the same page, there are +other means in \LaTeXe, such as the \texttt{minipage} environment, +that you can use. Moreover, if you have written your procedures so +that they have to appear on the same page, you should probably be +asking yourself whether they are too interdependent. + +The typical structure within a \Codebox{} is as follows. Usually, the +first line is the name of a procedure, along with a list of +parameters. (Not all \Codebox{}es include procedure names; for +example, see the pseudocode near the bottom of page~306 of CLRS\@.) +After the line containing the procedure name comes one or more lines +of code, usually numbered. Some of the lines may be unnumbered, being +continuations of previous lines. In rare cases, when there is just +one line of code per procedure, we don't bother numbering the line; +see the \proc{Parent}, \proc{Left}, and \proc{Right} procedures on +page~128 for example. Lines are usually numbered starting from~1, but +again there are exceptions, such as the pseudocode near the bottom of +page~306. + +\subheading{Using \texttt{$\backslash$Procname} to name the procedure} + +The \verb`\Procname` command specifies the name of the procedure. It +takes as a parameter the procedure name and parameters, typically all +in math mode. \verb`\Procname` makes its argument flush left against +the margin, and it leaves a little bit of extra space below the line. +For example, here is how we typeset the \proc{Insertion-Sort} +procedure on page~17: + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Insertion-Sort}(A)$} +\li \For $j \gets 2$ \To $\id{length}[A]$ +\li \Do + $\id{key} \gets A[j]$ +\li \Comment Insert $A[j]$ into the sorted sequence + $A[1 \twodots j-1]$. +\li $i \gets j-1$ +\li \While $i > 0$ and $A[i] > \id{key}$ +\li \Do + $A[i+1] \gets A[i]$ +\li $i \gets i-1$ + \End +\li $A[i+1] \gets \id{key}$ + \End +\end{codebox} +\end{verbatim} +} + +\subheading{Using \texttt{$\backslash$li} and \texttt{$\backslash$zi} +to start new lines} + +To start a new, numbered line, use the \verb`\li` command. To start a +new, \emph{un}numbered line, use the \verb`\zi` command. Note that +since a \Codebox{} is not like the \verb`verbatim` environment, the +line breaks within the source text do not correspond to the line +breaks in the typeset output. + +\subheading{Tabs} + +I find that it is best to set the tab stops to every 4 characters when +typing in and displaying pseudocode source with the \clrscode{} +package. I use emacs, and to get the tabs set up the way I want them, +my \mbox{\texttt{tex-mode.el}} file includes the line +\verb`(setq tab-width 4)`. For reasons I do not understand, sometimes +emacs ``forgets'' this setting, and I have to do a little friendly +persuasion. + +A \Codebox{} environment has a \verb`tabbing` environment within it. +The tab stops come in pairs, in that each pair of tab stops gives one +level of indentation. Tab stops are paired up so that when we typeset +the keywords \kw{then} and \kw{else}, they have the correct vertical +alignment. In other words, within each pair of tab stops, the first +stop is where \kw{then} and \kw{else} begin, and the second stop +completes a full level of indentation. For the most part, you won't +need to be concerned with tabs. The primary exception is when you +want to include a comment at the end of a line of pseudocode, and +especially when you want to include comments after several lines and +you want the comments to vertically align. Note that the +\verb`tabbing` environment within a codebox has nothing to do with +tabs that you enter in your source code; when you press the TAB key, +that's the same as pressing the space bar in the eyes of \LaTeXe{}. + +\subheading{Commands for keywords} + +As you can see from the source for \proc{Insertion-Sort}, there are +commands \verb`\For`, \verb`\Do`, and \verb`\While` that produce the +keywords \kw{for}, \kw{do}, and \kw{while}. \verb`\Do` and some other +commands also affect indentation. + +Sometimes you want to include a keyword in the main text, as I have +done in several places in this document. Use the \verb`\kw` command +to do so. For example, to produce a sentence that appeared two +paragraphs ago, I typed in the following: + +{\small +\begin{verbatim} +Tab stops are paired up so that when we typeset the keywords \kw{then} +and \kw{else}, they have the correct vertical alignment. +\end{verbatim} +} + +The following commands simply produce their corresponding keywords, +typeset in boldface: \verb`\For`, \verb`\To`, \verb`\Downto`, +\verb`\By`, \verb`\While`, \verb`\If`, \verb`\Return`, \verb`\Goto`, +and \verb`\Error`. Although you could achieve the same effect with +the \verb`\kw` command (e.g., \verb`\kw{for}` instead of \verb`\For`), +you will find it easier and more readable to use the above commands. +The \verb`\Comment` command simply produces the comment symbol~$\rhd$. +None of the above commands affects indentation. + +In \kw{for} loops and \kw{while} loops, the important commands are +\verb`\Do` and \verb`\End`. \verb`\Do` produces the keyword \kw{do}, +and it also increments the indentation level. \verb`\End` simply +decrements the indentation level, and it is the way to end any +\kw{for} or \kw{while} loop or otherwise decrement the indentation +level. + +As you can see from the above example, I like to place each \verb`\Do` +and \verb`\End` on its own line. You can of course format your source +text as you like, but I find that the way I format pseudocode makes it +easy to match up \verb`\Do`-\verb`\End` pairs. + +We also use \verb`\End` to terminate an \kw{if}-\kw{then} or +\kw{if}-\kw{then}-\kw{else} construct. For an example of +\kw{if}-\kw{then}, here's the \proc{Merge-Sort} procedure on page~32: + +\newpage + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Merge-Sort}(A, p, r)$} +\li \If $p < r$ +\li \Then + $q \gets \floor{(p + r) / 2}$ +\li $\proc{Merge-Sort}(A, p, q)$ +\li $\proc{Merge-Sort}(A, q+1, r)$ +\li $\proc{Merge}(A, p, q, r)$ + \End +\end{codebox} +\end{verbatim} +} + +\noindent For a more complicated example, using +\kw{if}-\kw{then}-\kw{else}, here's the \proc{Tree-Insert} procedure +on page~261: + +{\footnotesize +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Tree-Insert}(T,z)$} +\li $y \gets \const{nil}$ +\li $x \gets \id{root}[T]$ +\li \While $x \neq \const{nil}$ +\li \Do + $y \gets x$ +\li \If $\id{key}[z] < \id{key}[x]$ +\li \Then $x \gets \id{left}[x]$ +\li \Else $x \gets \id{right}[x]$ + \End + \End +\li $p[z] \gets y$ +\li \If $y = \const{nil}$ +\li \Then + $\id{root}[T] \gets z$\>\>\>\>\>\>\>\>\Comment Tree $T$ was empty +\li \Else + \If $\id{key}[z] <\ id{key}[y]$ +\li \Then $\id{left}[y]\ gets z$ +\li \Else $\id{right}[y] \gets z$ + \End + \End +\end{codebox} +\end{verbatim} +} + +\noindent As you can see, I like to line up the \verb`\End` commands +under the \verb`\Then` and \verb`\Else` commands. I could just as +easily have chosen to line up \verb`\End` under the \verb`\If` command +instead. I also sometimes elect to put the ``then'' or ``else'' code +on the same source line as the \verb`\Then` or \verb`\Else` command, +especially when that code is short. + +The \proc{Tree-Insert} example also shows how we put a comment on the +same line as code. Via the tab command \verb`\>`, we explicitly tab +to where we want the comment to begin and then use the \verb`\Comment` +command to produce the comment symbol. When there are several lines +with comments, you probably want them to align vertically. I just add +tab characters, using a trial-and-error approach, until I am pleased +with the result. For example, here's how we produced the +\proc{KMP-Matcher} procedure on page~926: + +\newpage + +{\footnotesize +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{KMP-Matcher}(T,P)$} +\li $n \gets \id{length}[T]$ +\li $m \gets \id{length}[P]$ +\li $\pi \gets \proc{Compute-Prefix-Function}(P)$ +\li $q \gets 0$\>\>\>\>\>\>\>\>\>\>\Comment Number of characters matched. +\li \For $i \gets 1$ \To $n$\>\>\>\>\>\>\>\>\>\>\Comment + Scan the text from left to right. +\li \Do + \While $q > 0$ and $\Px{q+1} \neq \Tx{i}$ +\li \Do $q \gets \pi[q]$\>\>\>\>\>\>\Comment Next character does not match. + \End +\li \If $\Px{q+1} = \Tx{i}$ +\li \Then $q \gets q+1$\>\>\>\>\>\>\Comment Next character matches. + \End +\li \If $q = m$\>\>\>\>\>\>\>\>\Comment Is all of $P$ matched? +\li \Then + print ``Pattern occurs with shift'' $i-m$ +\li $q \gets \pi[q]$\>\>\>\>\>\>\Comment Look for the next match. + \End + \End +\end{codebox} +\end{verbatim} +} + +\noindent All six comments align nicely. + +For a \kw{repeat} loop, use the \verb`\Repeat` and \verb`\Until` +commands, as in the \proc{Hash-Insert} procedure on page~238: + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Hash-Insert}(T,k)$} +\li $i \gets 0$ +\li \Repeat + $j \gets h(k,i)$ +\li \If $T[j] = \const{nil}$ +\li \Then + $T[j]\gets k$ +\li \Return $j$ +\li \Else + $i \gets i+1$ + \End +\li \Until $i = m$ +\li \Error ``hash table overflow'' +\end{codebox} +\end{verbatim} +} + +\noindent Note that the \verb`\Until` command has an implied +\verb`\End`. + +Sometimes, you need more complicated ``\kw{if}-ladders'' than you can +get from the \verb`\Then` and \verb`\Else` commands. The +\proc{Randomized-Select} procedure on page~186 provides an example, +and it uses the \verb`\ElseIf` and \verb`\ElseNoIf` commands: + +\newpage + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Randomized-Select}(A, p, r, i)$} +\li \If $p = r$ +\li \Then \Return $A[p]$ + \End +\li $q \gets \proc{Randomized-Partition}(A, p, r)$ +\li $k \gets q - p +1$ +\li \If $i = k$\>\>\>\>\Comment the pivot value is the answer +\li \Then \Return $A[q]$ +\li \ElseIf $i < k$ +\li \Then \Return $\proc{Randomized-Select}(A, p, q-1, i)$ +\li \ElseNoIf \Return $\proc{Randomized-Select}(A, q+1, r, i-k)$ + \End +\end{codebox} +\end{verbatim} +} + +\noindent For an \kw{if}-ladder, use \verb`\Then` for the first case, +\verb`\ElseNoIf` for the last case, and \verb`\ElseIf` for all +intermediate cases. An \kw{if}-ladder is terminated by \verb`\End`. +As another example, here is the \proc{Segments-Intersect} procedure on +page~937: + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Segments-Intersect}(p_1, p_2, p_3, p_4)$} +\li $d_1 \gets \proc{Direction}(p_3, p_4, p_1)$ +\li $d_2 \gets \proc{Direction}(p_3, p_4, p_2)$ +\li $d_3 \gets \proc{Direction}(p_1, p_2, p_3)$ +\li $d_4 \gets \proc{Direction}(p_1, p_2, p_4)$ +\li \If $((d_1 > 0 \mbox{ and } d_2 < 0) \mbox{ or } + (d_1 < 0 \mbox{ and } d_2 > 0))$ and + \Indentmore +\zi $((d_3 > 0 \mbox{ and } d_4 < 0) \mbox{ or } + (d_3 < 0 \mbox{ and } d_4 > 0))$ + \End +\li \Then \Return \const{true} +\li \ElseIf $d_1 = 0$ and $\proc{On-Segment}(p_3, p_4, p_1)$ +\li \Then \Return \const{true} +\li \ElseIf $d_2 = 0$ and $\proc{On-Segment}(p_3, p_4, p_2)$ +\li \Then \Return \const{true} +\li \ElseIf $d_3 = 0$ and $\proc{On-Segment}(p_1, p_2, p_3)$ +\li \Then \Return \const{true} +\li \ElseIf $d_4 = 0$ and $\proc{On-Segment}(p_1, p_2, p_4)$ +\li \Then \Return \const{true} +\li \ElseNoIf \Return \const{false} + \End +\end{codebox} +\end{verbatim} +} + +This example also shows our first use of an unnumbered line: the +second half of the tests on line~5. We use \verb`\zi` to indicate +that we're starting an unnumbered line. + +\subheading{Indentation} + +We also wish to indent the unnumbered line after line~5 by one level +more than the line above it. We do so with the \verb`\Indentmore` +command. The \verb`\End` command following the indented line +decrements the indentation level back to what it was prior to the +\verb`\Indentmore`. If I had wanted to indent the line by two levels, +I would have used two \verb`\Indentmore` commands before the line and +two \verb`\End` commands afterward. (Recall that \verb`\End` simply +decrements the indentation level.) + +Upon seeing the \verb`\end{codebox}` command, the \Codebox{} +environment checks that the indentation level is back to where it was +when it started, namely an indentation level of~0. If it is not, you +will get a warning message like the following: + +{\small +\begin{verbatim} +Warning: Indentation ends at level 1 in codebox on page 1. +\end{verbatim} +} + +\noindent This message would indicate that there is one missing +\verb`\End` command. On the other hand, you might have one too many +\verb`\End` commands, in which case you would get + +{\small +\begin{verbatim} +Warning: Indentation ends at level -1 in codebox on page 1. +\end{verbatim} +} + +\subheading{Right justification} + +The final two commands, \verb`\RComment` and \verb`\Flushright`, are +infrequently used and pertain to right justification. +\verb`\RComment` produces a comment that is flush against the right +margin. For example, here is how we typeset the +\proc{Binomial-Heap-Union} procedure on page~463: + +\newpage + +{\footnotesize +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Binomial-Heap-Union}(H_1,H_2)$} +\li $H \gets \proc{Make-Binomial-Heap}()$ +\li $\id{head}[H] \gets \proc{Binomial-Heap-Merge}(H_1,H_2)$ +\li free the objects $H_1$ and $H_2$ but not the lists they point to +\li \If $\id{head}[H] = \const{nil}$ +\li \Then \Return $H$ + \End +\li $\id{prev-x} \gets \const{nil}$ +\li $x \gets \id{head}[H]$ +\li $\id{next-x} \gets \id{sibling}[x]$ +\li \While $\id{next-x} \neq \const{nil}$ +\li \Do + \If $(\id{degree}[x] \neq \id{degree}[\id{next-x}])$ or +\zi \Flushright $(\id{sibling}[\id{next-x}] \neq \const{nil}$ + and $\id{degree}[\id{sibling}[\id{next-x}]] = \id{degree}[x])$ +\li \Then + $\id{prev-x} \gets x$ + \RComment Cases 1 and 2 +\li $x \gets \id{next-x}$ + \RComment Cases 1 and 2 +\li \Else + \If $\id{key}[x] \leq \id{key}[\id{next-x}]$ +\li \Then + $\id{sibling}[x] \gets \id{sibling}[\id{next-x}]$ + \RComment Case 3 +\li $\proc{Binomial-Link}(\id{next-x},x)$ + \RComment Case 3 +\li \Else + \If $\id{prev-x} = \const{nil}$ + \RComment Case 4 +\li \Then $\id{head}[H] \gets \id{next-x}$ + \RComment Case 4 +\li \Else $\id{sibling}[\id{prev-x}] \gets + \id{next-x}$ + \RComment Case 4 + \End +\li $\proc{Binomial-Link}(x,\id{next-x})$ + \RComment Case 4 +\li $x \gets \id{next-x}$ + \RComment Case 4 + \End + \End +\li $\id{next-x} \gets \id{sibling}[x]$ + \End +\li \Return $H$ +\end{codebox} +\end{verbatim} +} + +\noindent This procedure is also the only place in CLRS in which we +used the \verb`\Flushright` command. It puts the unnumbered line +following line~10 flush against the right margin. + +\subheading{Referencing line numbers} + +In the source files for CLRS, there are no absolute references to line +numbers. We use \emph{only} symbolic references. The \Codebox{} +environment is set up to allow you to place \verb`\label` commands on +lines of pseudocode and then reference these labels. The references +will resolve to the line numbers. Our convention is that any label +for a line number begins with \verb`\li:`, but you can name the labels +any way that you like. + +For example, here's how we \emph{really} wrote the +\proc{Insertion-Sort} procedure on page~17: + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Insertion-Sort}(A)$} +\li \For $j \gets 2$ \To $\id{length}[A]$ + \label{li:ins-sort-for} +\li \Do $\id{key} \gets A[j]$ \label{li:ins-sort-pick} + \label{li:ins-sort-for-body-begin} +\li \Comment Insert $A[j]$ into the sorted sequence + $A[1 \twodots j-1]$. +\li $i \gets j-1$ \label{li:ins-sort-find-begin} +\li \While $i > 0$ and $A[i] > \id{key}$ + \label{li:ins-sort-while} +\li \Do + $A[i+1] \gets A[i]$ \label{li:ins-sort-while-begin} +\li $i \gets i-1$ \label{li:ins-sort-find-end} + \label{li:ins-sort-while-end} + \End +\li $A[i+1] \gets \id{key}$ \label{li:ins-sort-ins} + \label{li:ins-sort-for-body-end} + \End +\end{codebox} +\end{verbatim} +} + +\noindent Note that any line may have multiple labels. As an example +of referencing these labels, here's the beginning of the first item +under ``Pseudocode conventions'' on page~19: + +{\small +\begin{verbatim} +\item For example, the body of the \kw{for} loop that begins on +line~\ref{li:ins-sort-for} consists of lines +\ref{li:ins-sort-for-body-begin}--\ref{li:ins-sort-for-body-end}, +and the body of the \kw{while} loop that begins on +line~\ref{li:ins-sort-while} contains lines +\ref{li:ins-sort-while-begin}--\ref{li:ins-sort-while-end} but +not line~\ref{li:ins-sort-for-body-end}. +\end{verbatim} +} + +\subheading{Setting line numbers} + +On rare occasions, we needed to start line numbers somewhere other +than~1. Use the \verb`setlinenumber` command to set the next line +number. For example, in Exercise~24.2-2 on page~594, we want the line +number to be the same as a line number within the +\proc{Dag-Shortest-Paths} procedure on page~592. Here's the source +for the exercise: + +{\small +\begin{verbatim} +Suppose we change line~\ref{li:dag-sp-loop-begin} of +\proc{Dag-Shortest-Paths} to read + +\begin{codebox} +\setlinenumber{li:dag-sp-loop-begin} +\li \For the first $\card{V}-1$ vertices, taken in topologically sorted order +\end{codebox} +Show that the procedure would remain correct. +\end{verbatim} +} + +\noindent The \proc{Dag-Shortest-Paths} procedure is + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Dag-Shortest-Paths}(G,w,s)$} +\li topologically sort the vertices of $G$ \label{li:dag-sp-topo-sort} +\li $\proc{Initialize-Single-Source}(G,s)$ \label{li:dag-sp-init} +\li \For each vertex $u$, taken in topologically sorted order + \label{li:dag-sp-loop-begin} +\li \Do + \For each vertex $v \in \id{Adj}[u]$ + \label{li:dag-sp-inner-begin} +\li \Do $\proc{Relax}(u,v,w)$ \label{li:dag-sp-loop-end} + \End + \End +\end{codebox} +\end{verbatim} +} + +Even more rarely (just once, in fact), we needed to set a line number +to be some other line number plus an offset. That was in the two +lines of pseudocode near the bottom of page~306, where the first line +number had to be one greater than the number of the last line of +\proc{Left-Rotate} on page~278. Use the \verb`setlinenumberplus` +command: + +{\footnotesize +\begin{verbatim} +\begin{codebox} +\setlinenumberplus{li:left-rot-parent}{1} +\li $\id{size}[y] \gets \id{size}[x]$ +\li $\id{size}[x] \gets \id{size}[\id{left}[x]] + \id{size}[\id{right}[x]] + 1$ +\end{codebox} +\end{verbatim} +} + +\noindent Here, the last line of \proc{Left-Rotate} has +\verb`\label{li:left-rot-parent}`. + +\section{Reporting bugs} +\label{sec:bugs} + +If you find errors in the \clrscode{} package, please send me email +(thc@cs.dartmouth.edu). It would be best if your message included +everything I would require to elicit the error myself. + +The \texttt{clrscode.sty} file contains the following disclaimer: + +{\small +\begin{verbatim} +% Written for general distribution by Thomas H. Cormen, June 2003. + +% The author grants permission for anyone to use this macro package and +% to distribute it unchanged without further restriction. If you choose +% to modify this package, you must indicate that you have modified it +% prior to your distributing it. I don't want to get bug reports about +% changes that *you* have made! +\end{verbatim} +} + +\noindent I have enough trouble keeping up with my own bugs; I don't +want to hear about bugs that others have introduced in the package! + +\section{Revision history} + +\begin{itemize} + +\item 11 June 2003. Initial revision of document and code. + +\end{itemize} + +\begin{thebibliography}{9} + +\bibitem{CLRS01} Thomas H. Cormen, Charles E. Leiserson, Ronald L. +Rivest, and Clifford Stein. \textit{Introduction to Algorithms}, +second edition. The MIT Press and McGraw-Hill, 2001. + +\bibitem{Lamport93} Leslie Lamport. \textit{\LaTeX: A Document +Preparation System User's Guide and Reference Manual}. +Addison-Wesley, 1993. + +\end{thebibliography} + +\end{document} diff --git a/Master/texmf-dist/doc/latex/clrscode/page.tex b/Master/texmf-dist/doc/latex/clrscode/page.tex new file mode 100644 index 00000000000..de6c87bfc8e --- /dev/null +++ b/Master/texmf-dist/doc/latex/clrscode/page.tex @@ -0,0 +1,18 @@ +\setlength{\oddsidemargin}{0in} +\setlength{\evensidemargin}{0in} +\setlength{\textwidth}{6.5in} +\setlength{\topmargin}{0in} +\setlength{\textheight}{8.5in} +\setlength{\headheight}{0pt} +\setlength{\headsep}{0pt} + +\setcounter{topnumber}{3}% +\def\topfraction{.7}% +\setcounter{bottomnumber}{1} +\def\bottomfraction{.3} +\setcounter{totalnumber}{5}% +\def\textfraction{.1}% was .2 +\def\floatpagefraction{.7}% was .7 +\setcounter{dbltopnumber}{2} +\def\dbltopfraction{.7} +\def\dblfloatpagefraction{.5} |