÷ƒ’À;è TeX output 1996.03.05:1311‹ÿÿÿÿ ª� ýs o� ýÞ�’ÂÂæóDÓítG®G®cmr17¹The‘7tóÖÆG®G®cmss17ºalg‘q:¹pac�Œqk‘ÿäage��Ÿùº¯ó!",š cmsy10¿ŽŽŽŸ�����’ÓUùóX«Q cmr12»Sta an‘ê¨Ulfb�SŽergŽŽŸ��’Äjýsta an�¬ru@nada.kth.seŽŽŽŽŽŸ%fj�’Ò|»18–ê¨August“1995ŽŸ.�’æ!Kót ‰: cmbx9ÇAbstractŽŸ¬Ñ�‘oßüóo´‹Ç cmr9ÆThis–÷òpacš¾9k‘ÿ|rage“de nes“t˜w˜o“en˜vironmen˜ts“for“t˜yp�AÇesetting“algorithms“inޤ ��‘bL�Ÿýó5�‘ü«‡ó¹Aa¨cmr6ÁAŽŽ‘© ÆT�‘þuAŸïÿEŽ‘˜ŸX‘c.2�Ÿÿÿó5ùž" cmmi9È"ŽŽ’„uÅÆ.‘WÌLines–~sare“automatically“n•¾9um“bšAÇered–~sand“can“b˜e“referenced,‘غtheŽ¡�‘bmeans–šùfor“easy“indenš¾9tation“is“pro˜vided,‘³rand“algorithms“can“b�AÇe“made“ oatingŽ¡�‘bb•AÇo“dies–Tif“desired.ŽŸ!Ä��‘Ió ÂÖN ff cmbx12Ë1Ž‘aLËIn�ŒÌtro�s3ductionŽŸç�‘Ió!ßêŸ'EŽ‘ãxX‘ü2�Ÿÿó  b> cmmi10µ"ŽŽ‘(|ϲ:Ž Á< � ÿSÜÃ�‘m"�ó&ò"V cmbx10ÑAlgorithm‘ÕT1:‘qDzExample–UUof“the“Ìalgorithm“²en•¸ãvironmen“t.ŽŸ ¸ä�‘m"�ÑInput:‘p²An–UUordered“set“µU‘Þ3²=‘Çó !",š cmsy10¸fµu�Ÿÿ±1Ž–|sµ;›ª¨u�Ÿÿ±2Ž“µ;�˜:˜:˜:Ž‘ÿ÷;˜u�Ÿÿó 0e—rcmmi7´nŽ‘q~¸g².Ž¡�‘m"�ÑOutput:‘`ñ²The–sset's“maximš¸ãum“elemen˜t,›z�and“a“set“µA²,˜¸jµA¸j–ø¼²=�“logޑ޵n²,Ž¡�‘m"�conš¸ãtaining–UUthe“next“largest“elemen˜t.‘qÇ(If“µn–Dz=“1,–UUthen“µA–Dz=“¸;²).Ž¡�‘m"�ó'Œ-ø cmcsc10ÒMax2²(µU‘²)Ž¡���‘m"�(1)ŽŽ’�G9Ñif‘lp¸jµU‘¸j–Dz=“1Ž¡���‘m"�(2)ŽŽ’��,Ñreturn‘ÕT²(µu�Ÿÿ±1Ž‘|sµ;‘ª¨¸;²)Ž¡���‘m"�(3)ŽŽ’�G9Ñelse‘ÕTif‘lp¸jµU‘¸j–Dz=“2Ž¡���‘m"�(4)ŽŽ�’��,Ñif‘lpµu�Ÿÿ±1Ž‘C‹µ>‘Çu�Ÿÿ±2ŽŽ’͹tÑthen‘UUreturn‘ÕT²(µu�Ÿÿ±1Ž–|sµ;‘ª¨¸fµu�Ÿÿ±2Ž“¸g²)Ž¡���‘m"�(5)ŽŽ’͹tÑelse‘UUreturn‘ÕT²(µu�Ÿÿ±2Ž–|sµ;‘ª¨¸fµu�Ÿÿ±1Ž“¸g²)Ž¡���‘m"�(6)ŽŽ’�G9ÑelseŽŸ ñÆ���‘m"�²(7)ŽŽ’��,(µb;‘ª¨B‘€q²)‘Ǹ ‘UUÒMax2²(¸fµu�Ÿÿ´iŽ‘TL¸g�ŸúÎ:�ó O!â…cmsy7·b´n=±2·cŽŸûZ�´i±=1ŽŽ‘Ü+²)Ž¡���‘m"�(8)ŽŽ’��,(µc;‘ª¨C‘·²)‘Ǹ ‘UUÒMax2²(¸fµu�Ÿÿ´iŽ‘TL¸g�Ÿü^ÿ�´nŽŸÙ”�i±=·b´n=±2·c±+1ŽŽ‘'ô ²)ŽŸ x“���‘m"�(9)ŽŽ�’��,Ñif‘lpµb–Ç>“cŽ’ÁìÑthen‘UUreturn‘ÕT²(µb;‘ª¨¸fµc¸g–8à[“µB‘€q²)Ž¡���‘m"�(10)ŽŽ’ÁìÑelse‘UUreturn‘ÕT²(µc;‘ª¨¸fµb¸g–8à[“µC‘·²)Ž¡ŽŸØä�‘M¹–Í\begin{algorithm}[h]ޤ �‘M¹–\caption{Example–¹–of“the“\texttt{algorithm}“environment.\label{alg:ex}}Ž¡�‘M¹–\alginout{An–¹–ordered“set“$U=\{u_1,u_2,\dots,u_n\}$.}Ž¡�‘x?Ü{The–¹–set's“maximum“element,“and“a“set“$A$,“$|A|=\log“n$,Ž¡�‘|ùrcontaining–¹–the“next“largest“element.‘ s,(If“$n=1$,“thenŽŽŸ�’ø²2ŽŽŒ‹ ” ª� ýs o� ý´�‘|ùrÍ$A=\emptyset$).}ޤ �‘M¹–\algname{Max2}{$U$}Ž¡�‘M¹–\begin{algtab}Ž¡�‘M¹–\algif{$|U|=1$}Ž¡�‘s†F\algreturn–¹–$(u_1,“\emptyset)$“\\Ž¡�‘M¹–\algelsif{$|U|=2$}Ž¡�‘s†F\algifthenelse{$u_1>u_2$}{\algreturn–¹–$(u_1,“\{u_2\})$}Ž¡�’é¥ì{\algreturn–¹–$(u_2,“\{u_1\})$}Ž¡�‘M¹–\algelseŽ¡�‘s†F$(b,B)‘¹–\leftarrow$Ž¡�’�³\algcall{Max2}{$\{u_i\}_{i=1}^{\lfloor‘¹–n/2\rfloor}$}\\Ž¡�‘s†F$(c,C)‘¹–\leftarrow$Ž¡�’�³\algcall{Max2}{$\{u_i\}_{i=\lfloor‘¹–n/2\rfloor+1}^{n}$}\\Ž¡�‘s†F\algifthenelse{$b>c$}{\algreturn–¹–$(b,“\{c\}\cup“B)$}Ž¡�’Ö¿”{\algreturn–¹–$(c,“\{b\}\cup“C)$}Ž¡�‘M¹–\algendŽ¡�‘M¹–\end{algtab}Ž¡�‘M¹–\end{algorithm}Ž¡ŸŸ?�‘I²There–ëis“a“list“of“all“programming“constructs“aš¸ãv‘ÿqÇailable“in“the“Ìalgtab“²en˜vironmen˜tޤ �‘Iat–©the“end“of“this“do�Gcumenš¸ãt.‘8^They“w˜ork“v˜ery“m˜uc˜h“lik˜e“the“macros“used“ab�Go˜v˜e.‘8^AsŽ¡�‘Ia–³žgeneral“rule,‘Óöif“a“macro“do�Gesn't“takš¸ãe“an“argumen˜t,‘Óöa“space“c˜harater“is“included“atŽ¡�‘Ithe–yçend“of“the“macro“de nition.‘(£F‘ÿ*ªor“example,‘¥Êt�¸ãyp�Ge“Ì$a=0$–?ý\algor“\algnot“$b=0$Ž¡�‘I²to–UUpro�Gduce“\µa–Dz=“0�‘UUÑorŽ�‘§notŽ‘&صb“²=“0."ŽŸ!��‘IË3Ž‘aLËThe‘ffImplemen�ŒÌtationŽŸç��‘Lüs±1Ž‘Sª®ó©±�Ê cmsy9Éh�ó(ÒoÇw cmss9Ópack�¾9ageŽ‘#g ÉiŽŸÙL�‘I²The–UUÌfloat“²pacš¸ãk‘ÿqÇage“b˜y“Anselm“Lingnau“is“used“for“ oating“algorithms.Ž© ì¦��‘Lüs±2Ž‘Sª®Í\RequirePackage{float,‘¹–ifthen}ŽŸì¦�‘I²Here–dUare“the“v‘ÿqÇarible“declarations.‘ žÇÌ\algmarginwidth²,–èÌ\alglinenowidth²,“andŽ¡�‘IÌ\algtabwidth–÷Ö²de ne“the“amounš¸ãt“of“inden˜tation“of“the“en˜tire“algorithm,‘ ‰the“spaceŽ¡�‘Ireservš¸ãed–UUfor“line“n˜um˜b�Gers,“and“the“inden˜tation“made“b˜y“Ì\algbegin“²resp�Gectiv˜ely‘ÿ*ª.ަ��‘Lüs±3Ž‘Sª®Í\newlength{\algmarginwidth}\setlength{\algmarginwidth}{.5in}ޤ ��‘Lüs±4Ž‘Sª®Í\newlength{\alglinenowidth}\setlength{\alglinenowidth}{1.2cm}Ž¡��‘Lüs±5Ž‘Sª®Í\newlength{\algtabwidth}\setlength{\algtabwidth}{.5cm}Ž¡��‘Lüs±6Ž‘Sª®Í\newlength{\alg@fromleft}Ž¡��‘Lüs±7Ž‘Sª®Í\newlength{\alg@tmplen}Ž¡��‘Lüs±8Ž‘Sª®Í\newsavebox{\alg@tmpbox}Ž¡��‘Lüs±9Ž‘Sª®Í\newcounter{alg@inmargin}\setcounter{alg@inmargin}{0}Ž¡��‘I±10Ž‘Sª®Í\newcounter{algline}Ž¡��‘I±11Ž‘Sª®Í\newboolean{alg@linenums}ŽŸì¦�‘I²The–ƒ strings“used“in“captions“and“in“the“List“of“Algorithms“di er“in“some“languages.ަ��‘I±12Ž‘Sª®Í\DeclareOption{english}{\def\alg@floatname{Algorithm}Ž¡��‘I±13ޒžÍ\def\alg@listname{List–¹–of“Algorithms}Ž¡��‘I±14ޒžÍ\def\alg@descname{Description}Ž¡��‘I±15ޒžÍ\def\alg@inputname{Input}Ž¡��‘I±16ޒžÍ\def\alg@outputname{Output}}Ž¡��‘I±17Ž‘Sª®Í\DeclareOption{american}{\def\alg@floatname{Algorithm}Ž¡��‘I±18ޒžÍ\def\alg@listname{List–¹–of“Algorithms}ŽŽŸ�’ø²3ŽŽŒ‹^ ª� ýs o� ý´��‘I±19ޒžÍ\def\alg@descname{Description}ޤ ��‘I±20ޒžÍ\def\alg@inputname{Input}Ž¡��‘I±21ޒžÍ\def\alg@outputname{Output}}Ž¡��‘I±22Ž‘Sª®Í\DeclareOption{swedish}{\def\alg@floatname{Algoritm}Ž¡��‘I±23ޒžÍ\def\alg@listname{Algoritmer}Ž¡��‘I±24ޒžÍ\def\alg@descname{Beskrivning}Ž¡��‘I±25ޒžÍ\def\alg@inputname{Input}Ž¡��‘I±26ޒžÍ\def\alg@outputname{Output}}Ž¡��‘I±27Ž‘Sª®Í\ExecuteOptions{english}Ž¡��‘I±28Ž‘Sª®Í\ProcessOptionsŽŸ�‘I²The–UUfollo�¸ãwing“de nitions“set“up“the“prop�Gerties“of“the“Ìalgorithmfloat².Ž©��‘I±29Ž‘Sª®Í\newcommand\floatc@alg[2]{{\bfseries\rmfamilyŽ¡��‘I±30Ž‘a×pÍ\hspace{\algmarginwidth}#1:}‘¹–#2\par}Ž¡��‘I±31Ž‘Sª®Í\newcommand\fs@alg{Ž¡��‘I±32Ž‘a×pÍ\let\@fs@capt\floatc@algŽ¡��‘I±33Ž‘a×pÍ\def\@fs@pre{}\def\@fs@post{}\def\@fs@mid{\vspace{3pt}}Ž¡��‘I±34Ž‘a×pÍ\let\@fs@iftopcapt\iftrue}Ž¡��‘I±35Ž‘Sª®Í\floatstyle{alg}Ž¡��‘I±36Ž‘Sª®Í\newfloat{algorithmfloat}{h}{loa}Ž¡��‘I±37Ž‘Sª®Í\floatname{algorithmfloat}{\alg@floatname}ޤ����‘îót\listofalgorithmsŽŽŽ‘I²The–›Ì\listofalgorithms“²macro“can“b�Ge“used“to“generate“a“list“of“all“algorithms“inŽŸ �‘Ia‘UUdo�Gcumen�¸ãt.ަ��‘I±38Ž‘Sª®Í\newcommand{\listofalgorithms}{\listof{algorithmfloat}{\alg@listname}}Ž¡����‘Žalg@marginŽŽŽ‘I²The–Þ8Ìalg@margin“²en•¸ãvironmen“t›Þ8mak“es˜the˜text˜a˜bit˜narro“w“er.‘ qThis˜en“vironmen“tޤ �‘Iis–—‹used“in“b�Goth“the“Ìalgorithm“²and“Ìalgtab“²en•¸ãvironmen“ts;‘¸¦it›—‹k“eeps˜trac“k˜of˜if˜theŽ¡�‘Itext–UUis“already“narro�¸ãw,“and“in“this“case“do�Ges“nothing.ަ��‘I±39Ž‘Sª®Í\newenvironment{alg@margin}‘¹–{ޤ ��‘I±40Ž‘a×pÍ\ifthenelse{\value{alg@inmargin}=0}‘¹–{Ž¡��‘I±41Ž‘t½ÈÍ\advance\leftskip\algmarginwidthŽ¡��‘I±42Ž‘t½ÈÍ\advance\rightskip\algmarginwidthŽ¡��‘I±43Ž‘t½ÈÍ\alg@fromleft=\leftskipŽ¡��‘I±44Ž‘a×pÍ}‘¹–{}Ž¡��‘I±45Ž‘a×pÍ\stepcounter{alg@inmargin}Ž¡��‘I±46Ž‘a×pÍ\parskip=0cm\parindent=0cmŽ¡��‘I±47Ž‘Sª®Í}‘¹–{%Ž¡��‘I±48Ž‘a×pÍ\addtocounter{alg@inmargin}{-1}%Ž¡��‘I±49Ž‘a×pÍ\ifthenelse{\value{alg@inmargin}=0}‘¹–{%Ž¡��‘I±50Ž‘p2Í\advance\leftskip-\algmarginwidth%Ž¡��‘I±51Ž‘p2Í\advance\rightskip-\algmarginwidth%Ž¡��‘I±52Ž‘a×pÍ}‘¹–{}%Ž¡��‘I±53Ž‘Sª®Í}ŽŸ����‘À$algorithmŽŽŽ‘I²The– ŠÌalgorithm“²en•¸ãvironmen“t– Šsimply“bšGegins“a“ oat“as“de ned“ab˜o•¸ãv“e.‘XƒActually‘ÿ*ª,‘³theޤ �‘Idefault–Zéis“to“use“the“placemen�¸ãt“parameter“ÌH²,“so“that“the“algorithm“will“not“reallyŽ¡�‘I oat.‘qÇInside–UUthe“ oat“all“text“is“indenš¸ãted“b˜y“Ì\algmarginwidth².ަ��‘I±54Ž‘Sª®Í\newenvironment{algorithm}[1][H]‘¹–{ޤ ��‘I±55Ž‘a×pÍ\begin{algorithmfloat}[#1]\begin{alg@margin}Ž¡��‘I±56Ž‘Sª®Í}‘¹–{Ž¡��‘I±57Ž‘a×pÍ\end{alg@margin}\end{algorithmfloat}Ž¡��‘I±58Ž‘Sª®Í}ŽŽŸ�’ø²4ŽŽŒ‹'2 ª� ýs o� ý´����‘3PÍalg@tabŽŽŽ‘I²The–hÑÌalg@tab“²en•¸ãvironmen“t–hÑis“what“do�Ges“most“of“the“formatting“job;‘r�it's“called“b�¸ãyޤ �‘IÌalgtab–½D²and“Ìalgtab*“²de ned“b�Geloš¸ãw.‘©”The“argumen˜t“de nes“the“amoun˜t“of“initialŽ¡�‘Iindenš¸ãtation.‘X cmmi10ó 0e—rcmmi7óKñ`y cmr10óÙ“ Rcmr7ùL˜ßßßßßßß