summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/clrscode3e/clrscode3e.tex
blob: 6ca1fdfdb8b05149321ad330bc68bf5d2d1424f3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
\documentclass[11pt]{article}
\usepackage{times}
\usepackage[mtpcal,mtphrb,zswash,subscriptcorrection]{mtpro2}
\usepackage{clrscode3e}
\usepackage{url}
\urlstyle{rm}
\input{page}

\newcommand{\subheading}[1]{\subsubsection*{#1}}
\newcommand{\clrscodethree}{\texttt{clrscode3e}}
\newcommand{\Codebox}{\texttt{codebox}}
\newcommand{\defn}[1]{\textit{\textbf{#1}}}

\begin{document}

\title{Using the \clrscodethree{} Package in \LaTeXe}
\author{Thomas H. Cormen \\ thc@cs.dartmouth.edu}
\date{February 20, 2018}

\maketitle

\section{Introduction}
\label{sec:intro}

This document describes how to use the \clrscodethree{} package in
\LaTeXe{} to typeset pseudocode in the style of \textit{Introduction
to Algorithms}, Third edition, by Cormen, Leiserson, Rivest, and Stein
(CLRS 3/e) \cite{CLRS09}.  You use the commands\footnote{We use the
term ``command'' rather than ``macro'' throughout this document,
though ``macro'' would work just as well.} in the same way we did in
writing CLRS 3/e, and your output will look just like the pseudocode
in the text.

\section{Setup}
\label{sec:setup}

To get the \clrscodethree{} package, download
\url{http://www.cs.dartmouth.edu/~thc/clrscode/clrscode3e.sty}, and
put it where it will be found when you run \LaTeXe{}.  To use the
package, include the following line in your source file:

{\small
\begin{verbatim}
\usepackage{clrscode3e}
\end{verbatim}
}

\noindent The \clrscodethree{} package itself includes the line

{\small
\begin{verbatim}
\RequirePackage{graphics}   % needed for \scalebox command
\end{verbatim}
}

\noindent This line is necessary in order to get the right spacing for
the $\isequal$ symbol that we use for equality tests.  Therefore, you
will need to have the \texttt{graphics} package installed and
available on your system.

\section{Typesetting names}
\label{sec:names}

Pseudocode in CLRS 3/e 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:] Use identifiers for variable names of more than
one character.  When a variable name is just a single character, e.g.,
the identifier~$j$ in line~1 of \proc{Insertion-Sort} on page~18, we
just typeset it in math mode rather than using the \verb`\id` command:
\verb`$j$`.

\sloppy

Do not typeset identifiers consisting of two or more characters, e.g.,
the variable \id{key} in line~2 of \proc{Insertion-Sort}, in this way.
(See page~51 of Lamport \cite{Lamport93}.)  Although \LaTeXe{}
provides the \verb`\mathit` command for typesetting multiletter
identifiers, use our \verb`\id` command instead: \verb`\id{key}`,
rather than \verb`\mathit{key}` or---horrors!---\verb`$key$`.  Since
the \verb`\id` command may be used both in and out of math mode, the
source text

\fussy

{\small
\begin{verbatim}
Line~5 uses the variable \id{key} in the test $A[i] > \id{key}$.
\end{verbatim}
}

\noindent will produce
\begin{quote}
Line~5 uses the variable \id{key} in the test $A[i] > \id{key}$.
\end{quote}

To see how a dash turns into a hyphen, consider line~1 of
\proc{Find-Max-Crossing-Subarray} on page~71.  It contains the
variable \id{left-sum}.  Typesetting this variable name by
\verb`\id{left-sum}` produces a hyphen in the identifier, but
typesetting it by \verb`\mathit{left-sum}` would produce
$\mathit{left-sum}$, with a minus sign---rather than a hyphen---in the
identifier.

\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 such as \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}`.  The \verb`\const` command typesets a dash within
a constant name as a hyphen, so that, as on page~409,
\verb`\const{no-such-path}` will produce $\const{no-such-path}$.

\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~44, $\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 Lamport \cite{Lamport93}
lists these ``log-like'' functions.

\end{description}

\section{Typesetting object attributes}
\label{sec:attributes}

In the first two editions of the book, we used square brackets for
object attributes.  For example, we represented the length of an
array~$A$ by $\id{length}[A]$.  Based on requests from readers, we
switched to the object-like dot-notation in the third edition, so that
we now denote the length of array~$A$ by \attrib{A}{length}.

You might think that you could typeset \attrib{A}{length} by
\verb`$A.\id{length}$`, but that would produce $A.\id{length}$, which
has not quite enough space after the dot.  Therefore, we created a set
of commands to typeset object attributes.  Each one may be used either
in or out of math mode.

Most of the time, we use the \verb`\attrib` command, which takes two
arguments: the name of the object and the name of the attribute.
Let's make a couple of definitions:
\begin{itemize}

\item An \defn{i-string} is a string that you would use in an
\verb`\id` command, typically one or more non-Greek letters, numerals,
or dashes.

\item An \defn{x-string} is a string that you would not use in an
\verb`\id` command, typically because it has a subscript or one or
more Greek letters.

\item As a special, and very common, case, a single non-Greek letter
can count as either an i-string or an x-string.

\end{itemize}

\noindent The \verb`\attrib` command works well when the object name
is an x-string and the attribute name is an \mbox{i-string}.  For
example, to produce \attrib{A}{length}, use \verb`\attrib{A}{length}`.
Here, we treat the object name,~$A$, as an x-string.  The attribute
name, \id{length}, is of course an i-string.

If all your objects are x-strings and all your attributes are
i-strings, then the \verb`\attrib` command will be all you need.  We
provide several other commands for other situations that arose when we
produced CLRS~3/e.

The four basic attribute commands are \verb`\attribxi`,
\verb`\attribxx`, \verb`\attribii`, and \verb`\attribix`.  Each takes
two arguments: the object name and the attribute name.  The last two
letters of the command name tell you what type of strings the
arguments should be.  The next-to-last letter tells you about the
object name, and the last letter tells you about the attribute name.
\verb`i` indicates that the argument will be treated as an \verb`\id`,
in which case the command calls the \verb`\id` command and also puts
the right amount of space between the argument and the dot.

\begin{itemize}

\item You may use \verb`\attribxi` precisely when you would use
\verb`\attrib`.  In fact, \verb`\attrib` is just a call to
\verb`\attribxi`.

\item Use \verb`\attribxx` when both the object name and attribute
names are x-strings.  For example, you would use \verb`\attribxx` if
the attribute name has a subscript, so that to produce
\attribxx{y}{c_i}, you would use \verb`\attribxx{y}{c_i}`.  Another
situation in which you would use \verb`\attribxx` is when the
attribute name is a Greek letter: to produce \attribxx{v}{\pi}, use
\verb`\attribxx{v}{\pi}`.

\item If both the object name and attribute name are i-strings, then
you should use \verb`\attribii`.  For example,
\verb`\attribii{item}{key}` produces \attribii{item}{key}, and
\verb`\attribii{prev-item}{np}` produces \attribii{prev-item}{np}.

\item If the object name is an i-string and the attribute name is an
x-string, then use \verb`\attribix`.  (We never had this situation
arise in CLRS 3/e.)  But if we had wanted to produce
\attribix{item}{\pi}, we would have used \verb`\attribix{item}{\pi}`.

\end{itemize}

For convenience, the \clrscodethree{} package also contains commands
for cascading attributes, such as \attribb{x}{left}{size}.  These
commands string together calls to the appropriate \verb`\attribxi` and
\verb`\attribxx` commands.  The number of arguments they take depends
on how many attributes you are stringing together.

\begin{itemize}

\item When you have two attributes, use \verb`\attribb`, which takes
an object name and two attribute names: \verb`\attribb{x}{left}{size}`
produces \attribb{x}{left}{size}.  This command assumes that the
object name is an x-string and both attribute names are i-strings.

\item For three attributes, use \verb`\attribbb`, which takes an
object name (an x-string) and three object names (i-strings): to
produce \attribbb{y}{p}{left}{size}, use
\verb`\attribbb{y}{p}{left}{size}`.

\item For four attributes, use \verb`\attribbbb`, which is like
\verb`\attribbb` but with one additional attribute tacked on.  We
never needed to use this command in CLRS 3/e.

\item The \verb`\attribbxxi` command is for one level of cascading
where the first attribute given is an \mbox{x-string}.  For example,
\verb`\attribbxxi{x}{c_i}{n}` produces \attribbxxi{x}{c_i}{n}.

\end{itemize}

If your cascading attributes do not fit any of these descriptions,
you'll have to roll your own command from the \verb`\attribxx` and
\verb`\attribxi` (or \verb`\attrib`) commands.  For example, suppose
you want to produce \attribxx{\attribxi{x}{left}}{\id{key_i}}.
Because it has a subscript, $\id{key}_i$ is an x-string, and so you
should not use \verb`\attribb`.  Instead, use
\verb`\attribxx{\attribxi{x}{left}}{\id{key_i}}`.  (You could replace
the call of \verb`\attribxi` by a call of \verb`\attrib`.)  Note that
this call treats $\id{key_i}$ as an attribute of \attrib{x}{left},
which is correct, rather than treating \attribii{left}{\id{key}_i} as
an attribute of~$x$, which is not correct.

Edges of a graph can have attributes, too, and the \clrscodethree{}
package provides two commands for attributes of edges.  These commands
assume that the edges are of the form $(u,v)$, where the vertices $u$
and~$v$ are x-strings.  They take three parameters: the two vertices
that define the edge and the name of the attribute.
\begin{itemize}

\item When the attribute name is an i-string, use \verb`\attribe`.
For example, to produce \attribe{u}{v}{c}, use
\verb`\attribe{u}{v}{c}`.

\item When the attribute name is an x-string, use \verb`\attribex`.
For example, to produce \attribex{u}{v}{c'}, use
\verb`\attribex{u}{v}{c'}`.

\end{itemize}

\section{Miscellaneous commands}
\label{sec:misc}

The \clrscodethree{} package contains three commands that don't really
fit anywhere else, so let's handle them here.  All three must be used
in math mode.

\begin{itemize}

\item 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]$.

\item We use the \verb`\gets` command for the assignment operator.
For example, line~4 of \proc{Insertion-Sort} on page~18 is
\verb`$i \gets j - 1$`, producing $i \gets j - 1$.

\item We use the \verb`\isequal` command to test for equality with the
$\isequal$ symbol.  For example, line~1 of
\proc{Find-Maximum-Subarray} on page~72 contains the test $\id{high}
\isequal \id{low}$, which we get by typesetting
\verb`$\id{high} \isequal \id{low}$`.

\end{itemize}

You might wonder why we bother with the \verb`\gets` command when we
could just typeset an equals sign directly.  The answer is that in the
first two editions of \textit{Introduction to Algorithms}, we used a
different symbol (a left arrow) for the assignment operator, and it
made sense to use a command for that.  Many readers told us that they
preferred to use an equals sign for assignment---as many programming
languages use---and so we made this change for the third edition.  But
it's a good idea to continue using the \verb`\gets` command so that we
can easily change our assignment operator should we desire to do so in
the future.

Once we decided to use the equals sign for assignment, we could no
longer use it for equality tests.  We created the \verb`\isequal`
command for equality tests, and we decided to base it on the double
equals sign used for equality tests in C, C++, and Java.  Typesetting
it as \verb`==` in math mode produces $==$, which is too wide for our
tastes.  Our \verb`\isequal` command calls the \verb`\scalebox`
command from the \texttt{graphics} package to narrow the symbol, and
it puts a nice amount of space between the equals signs: $\isequal$.

\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 does not break across pages.

\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, then you
should consider using other means in \LaTeXe, such as the
\texttt{minipage} environment.  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 on page~343 of CLRS 3/e.)  After the line
containing the procedure name come one or more lines of code, usually
numbered.  Some of the lines may be unnumbered, being continuations of
previous lines.  Lines are usually numbered starting from~1, but again
there are exceptions, such as the pseudocode on page~343.

\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~18:

\pagebreak

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\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 in the text editor to
every 4 characters when typing in and displaying pseudocode source
with the \clrscodethree{} 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)`.

A \Codebox{} environment has a \verb`tabbing` environment within it.
Each tab stop gives one level of indentation.  We designed the
indentation so that the body of an \kw{else} clause starts at just the
right 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.

If you used the \texttt{clrscode} package from the second edition of
the book, you might notice different tabbing behavior when you port
your pseudocode to the \clrscodethree{} package.  Where the
\texttt{clrscode} package used two tab stops for each level of loop
indentation, the \clrscodethree{} package uses just one tab stop.  We
made this change in the \clrscodethree{} package because the third
edition eliminates the keyword \kw{then} and left-aligns \kw{else}
with its corresponding \kw{if}.

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}, the commands
\verb`\For` and \verb`\While` produce the keywords \kw{for} and
\kw{while} in boldface within a \Codebox{}.

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 the previous paragraph, I typed in
the following:

{\small
\begin{verbatim}
As you can see from the source for \proc{Insertion-Sort}, the commands
\verb`\For` and \verb`\While` produce the keywords \kw{for} and
\kw{while} in boldface within a \texttt{codebox}.
\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`
(which does not appear in CLRS 3/e, but you might wish to use),
\verb`\Error`, \verb`\Spawn`, \verb`\Sync`, and \verb`\Parfor` (which
produces the compound keyword \mbox{\kw{parallel~for}}).  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 in pseudocode.  The
\verb`\Comment` command simply produces the comment symbol
\CommentSymbol, followed by a space.  To get the comment symbol
without a following space, use \verb`\CommentSymbol`.  None of the
above commands affects indentation.

\subheading{Loops}

The \proc{Insertion-Sort} example above shows typical ways to typeset
\kw{for} and \kw{while} loops.  In these loops, the important commands
are \verb`\Do` and \verb`\End`.  \verb`\Do` increments the indentation
level to start the body.  Put \verb`\Do` on a line starting with
\verb`\li`, but don't put either \verb`\li` or \verb`\zi` between the
\verb`\Do` command and the first statement of the loop body.  Use
\verb`\li` or \verb`\zi` in front of all loop-body statements after
the first one.  \verb`\End` simply decrements the indentation level,
and you use it to end any \kw{for} or \kw{while} loop, or otherwise
decrement the indentation level.

In the first two editions of the book, the body of a \kw{for} or
\kw{while} loop began with the keyword \kw{do}.  Responding to
requests from readers to make pseudocode more like C, C++, and Java,
we eliminated this keyword in the third edition.

As you can see from the above example, I like to place each \verb`\Do`
and \verb`\End` on its own line.  You can format your source text any
way you like, but I find that the way I format pseudocode makes it
easy to match up \verb`\Do`-\verb`\End` pairs.

If you want your \kw{for} loop to decrease the loop variable in each
iteration, use \verb`\Downto` rather than \verb`\To`.  If you want the
stride to be a value other than~$1$, use the \verb`\By` command.  For
example, line~6 of \proc{Iterative-FFT} on page~917 is typeset as
\begin{verbatim}
\For $k \gets 0$ \To $n-1$ \By $m$
\end{verbatim}

Loops that use the \kw{repeat}-\kw{until} structure are a bit
different.  We use the \verb`\Repeat` and \verb`\Until`
commands, as in the \proc{Hash-Insert} procedure on page~270:

\pagebreak

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Hash-Insert}(T,k)$}
\li $i \gets 0$
\li \Repeat
\li     $j \gets h(k,i)$
\li     \If $T[j] \isequal \const{nil}$
\li         \Then
                $T[j] \gets k$
\li             \Return $j$
\li         \Else
                $i \gets i+1$
            \End
\li \Until $i \isequal m$
\li \Error ``hash table overflow''
\end{codebox}
\end{verbatim}
}

\noindent Note that the \verb`\Until` command has an implied
\verb`\End`.

\subheading{Typesetting \kw{if} statements}

As you can see from the above example of \proc{Hash-Insert}, we
typeset \kw{if} statements with the commands \verb`\If`, \verb`\Then`,
\verb`\Else`, and \verb`\End`.  In the first two editions of the book,
the keyword \kw{then} appeared in pseudocode, but---again mindful of
requests from our readers to make our pseudocode more like C, C++, and
Java---we eliminated the keyword \kw{then} in the third edition.  The
\verb`\Then` command remains, however, in order to indent the code
that runs when the test in the \kw{if} clause evaluates to
\const{true}.

We use \verb`\End` to terminate an \kw{if} statement, whether or not
it has an \kw{else} clause.  For an example of an \kw{if} statement
without an \kw{else} clause, here's the \proc{Merge-Sort} procedure on
page~34:

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

Note: the command \verb`\floor` is our own.  It is defined as

{\small
\begin{verbatim}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\end{verbatim}
}

The \proc{Hash-Insert} procedure above shows how to typeset an \kw{if}
statement that has an \kw{else} clause.  For a more complicated
example, using nested \kw{if} statements, here's the
\proc{Cascading-Cut} procedure on page~519:

\pagebreak

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Cascading-Cut}(H,y)$}
\li $z \gets \attrib{y}{p}$
\li \If $z \neq \const{nil}$
\li     \Then
            \If $\attrib{y}{mark} \isequal \const{false}$
\li             \Then $\attrib{y}{mark} \gets \const{true}$
\li             \Else
                    $\proc{Cut}(H,y,z)$
\li                 $\proc{Cascading-Cut}(H,z)$
                \End
        \End
\end{codebox}
\end{verbatim}
}

\noindent Note that \verb`\Then` and \verb`\Else` always follow an
\verb`\li` command to start a new numbered line.  As with the
\verb`\Do` command, don't put either \verb`\li` or \verb`\zi` between
\verb`\Then` or \verb`\Else` and the statement that follows.

As you can see, I 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 one short line, such as in line~4 of
\proc{Cascading-Cut}.

Sometimes, you need more complicated ``\kw{if}-ladders'' than you can
get from the \verb`\Then` and \verb`\Else` commands.  The
\proc{Transplant} procedure on page~296 provides an example,
and it uses the \verb`\ElseIf` and \verb`\ElseNoIf` commands:

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Transplant}(T, u, v)$}
\li \If $\attrib{u}{p} \isequal \const{nil}$
\li     \Then $\attrib{T}{root} \gets v$
\li \ElseIf $u \isequal \attribb{u}{p}{left}$
\li     \Then $\attribb{u}{p}{left} \gets v$
\li	\ElseNoIf
        $\attribb{u}{p}{right} \gets v$
    \End
\li \If $v \neq \const{nil}$
\li     \Then $\attrib{v}{p} \gets \attrib{u}{p}$
        \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` followed by
\verb`\Then` for all intermediate cases.  You use \verb`\ElseNoIf`
like you use \verb`\Else` in that it follows an \verb`\li` command,
you don't follow it with \verb`\Then`, and, because it terminates an
\kw{if}-ladder, it's followed by \verb`\End`.  I usually line up the
terminating \verb`\End` with \verb`\If`, the \verb`\ElseIf` commands,
and \verb`\ElseNoIf`, but the way you line it up won't change the
typeset output.

As another example, here is the \proc{Segments-Intersect} procedure on
page~1018:

\pagebreak

{\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 \isequal 0$ and $\proc{On-Segment}(p_3, p_4, p_1)$
\li     \Then \Return \const{true}
\li \ElseIf $d_2 \isequal 0$ and $\proc{On-Segment}(p_3, p_4, p_2)$
\li     \Then \Return \const{true}
\li \ElseIf $d_3 \isequal 0$ and $\proc{On-Segment}(p_1, p_2, p_3)$
\li     \Then \Return \const{true}
\li \ElseIf $d_4 \isequal 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 levels}

In the \proc{Segments-Intersect} procedure, we 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}
}

\noindent Whenever the indentation level is nonzero upon hitting an
\verb`\end{codebox}` command, you'll get a warning telling you what
the indentation level was.

\subheading{Tabs and comments}

Line~3 of \proc{Insertion-Sort} shows how to make a line that is only
a comment.  It's a little more tricky to put a comment at the end of a
line of code.  Using the tab command \verb`\>`, explicitly tab to
where you want the comment to begin and then use the \verb`\Comment`
command to produce the comment symbol.  When several lines contain
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~1005:

{\footnotesize
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{KMP-Matcher}(T,P)$}
\li $n \gets \attrib{T}{length}$
\li $m \gets \attrib{P}{length}$
\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}\ne \Tx{i}$
\li             \Do $q \gets \pi[q]$\>\>\>\>\>\>\Comment next character does not match
                \End
\li         \If $\Px{q+1} \isequal \Tx{i}$
\li             \Then $q \gets q+1$\>\>\>\>\>\>\Comment next character matches
                \End
\li         \If $q \isequal 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.

Note: the commands \verb`\Px` and \verb`\Tx` are our own, with the
definitions

{\small
\begin{verbatim}
\newcommand{\Px}[1]{P[#1]}
\newcommand{\Tx}[1]{T[#1]}
\end{verbatim}
}

We used the command \verb`\RComment` to justify a comment against the
right margin.  We used this command only in the \proc{RB-Insert-Fixup}
procedure on page~316 and the \proc{RB-Delete-Fixup} procedure on
page~326.  For example, here's how we typeset line~5 of
\proc{RB-Insert-Fixup}:

{\small
\begin{verbatim}
\li                     \Then
                            $\attribb{z}{p}{color}\gets \const{black}$
                                \RComment case 1
\end{verbatim}
}

\subheading{Referencing line numbers}

The source files for CLRS 3/e contain 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~18:

\pagebreak

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
                                            \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 Indentation indicates block structure.  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~657, we want the line
number to be the same as a line number within the
\proc{Dag-Shortest-Paths} procedure on page~655.  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 \attrib{G}{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 on page~343, where the first line number had to be
one greater than the number of the last line of \proc{Left-Rotate} on
page~313.  Use the \verb`setlinenumberplus` command:

{\small
\begin{verbatim}
\begin{codebox}
\setlinenumberplus{li:left-rot-parent}{1}
\li $\attrib{y}{size} \gets \attrib{x}{size}$
\li $\attrib{x}{size} \gets \attribb{x}{left}{size}
        + \attribb{x}{right}{size} + 1
\end{codebox}
\end{verbatim}
}

\noindent Here, the last line of \proc{Left-Rotate} has
\verb`\label{li:left-rot-parent}`.

\subheading{Indenting long argument lists in procedure calls}

You might find that you have to call a procedure with an argument list
so long that the call requires more than one line.  When this
situation arises, it often looks best to align the second and
subsequent lines of arguments with the first argument.  The only place
we did so was in the $\proc{Sum-Arrays}'$ procedure in Problem~27-1 on
page~805.

To get this style of alignment, use the \verb`\Startalign` and
\verb`\Stopalign` commands, in concert with the \verb`\>` command of
\LaTeXe{}.  The \verb`\Startalign` command takes an argument that is
the text string that you wish to align just to the right of.  Start
each line that you want to indent with \verb`\>`.  Use the
\verb`\Stopalign` command to restore indentation to its state from
before the \verb`\Startalign` command.

The source code for $\proc{Sum-Arrays}'$ shows how to use these
commands:

\pagebreak

{\small
\begin{verbatim}
\begin{codebox}
\Procname{$\proc{Sum-Arrays}{$'$}(A, B, C)$}
\li $n \gets \attrib{A}{length}$
\li $\id{grain-size} \gets\ \ ?$ \>\>\>\>\>\>\Comment to be determined
\li $r \gets \ceil{n/\id{grain-size}}$ 
\li \For $k \gets 0$ \To $r-1$
\li     \Do
            \Spawn $\proc{Add-Subarray}(A, B, C, k\cdot\id{grain-size}+1,$
\Startalign{\Spawn $\proc{Add-Subarray}($}
\>                  $\min((k+1)\cdot\id{grain-size}, n))$
\Stopalign
        \End
\li \Sync
\end{codebox}
\end{verbatim}
}

\noindent The second line of arguments in the call to
\proc{Add-Subarray} starts right under the first parameter, $A$, in
the call.

\section{Reporting bugs}
\label{sec:bugs}

If you find errors in the \clrscodethree{} 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{clrscode3e.sty} file contains the following disclaimer:

{\small
\begin{verbatim}
% Written for general distribution by Thomas H. Cormen, March 2009.

% 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 20 February 2018.  Included definitions for the commands
\verb`\floor`, \verb`\Px`, and \verb`\Tx`.  Changed \verb`\procdecl`
and \verb`\procdecltag` commands to \verb`\proc`.

\item 27 January 2010.  Corrected an error in the documentation.  The
first line after a \verb`\Repeat` command should begin with
\verb`\li`.

\item 23 March 2009.  Initial revision of document and code.

\end{itemize}

\begin{thebibliography}{9}

\bibitem{CLRS09} Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein.  \textit{Introduction to Algorithms},
third edition.  The MIT Press, 2009.

\bibitem{Lamport93} Leslie Lamport.  \textit{\LaTeX: A Document
Preparation System User's Guide and Reference Manual}.
Addison-Wesley, 1993.

\end{thebibliography}

\end{document}