; TeX output 1996.03.05:1311soDtGGcmr17The7tGGcmss17algq:pacqkage!", cmsy10UXQ cmr12Sta anUlfbSergjsta anru@nada.kth.se%fj|18August1995.!Kt : cmbx9Abstractэoo cmr9Thispac9k|ragede nestwoenvironmentsfortypAesettingalgorithmsin bL5Aacmr6A TuAEXc.25" cmmi9"u.WLines~sareautomaticallyn9umbAered~sandcanbereferenced,غthebmeansforeasyinden9tationisprovided,randalgorithmscanbAemade oatingbbAodiesTifdesired.!čI Nff cmbx121aLIntros3ductionI!'ExX2 b> cmmi10"(|ϲ:< SÍm"&"V cmbx10AlgorithmT1:qDzExampleUUofthealgorithmenvironment. 䍑m"Input:pAnUUorderedsetU3= !", cmsy10fu1|s;u2;:::;u 0ercmmi7nq~g.m"Output:`Thesset'smaximumelement,zandasetA,jAj=logn,m"containingUUthenextlargestelement.q(Ifn=1,UUthenA=;).m"'- cmcsc10Max2(U)m"(1)G9iflpjUj=1m"(2),returnT(u1|s;;)m"(3)G9elseTiflpjUj=2m"(4),iflpu1C>u2͹tthenUUreturnT(u1|s;fu2g)m"(5)͹telseUUreturnT(u2|s;fu1g)m"(6)G9else ƍm"(7),(b;Bq) UUMax2(fuiTLg: O!cmsy7bn=2cZi=1+)m"(8),(c;C) UUMax2(fuiTLg^nٔi=bn=2c+1' ) xm"(9),iflpb>cthenUUreturnT(b;fcg8[Bq)m"(10)elseUUreturnT(c;fbg8[C)䍑M\begin{algorithm}[h] M\caption{Exampleofthe\texttt{algorithm}environment.\label{alg:ex}}M\alginout{Anorderedset$U=\{u_1,u_2,\dots,u_n\}$.}x?{Theset'smaximumelement,andaset$A$,$|A|=\logn$,|rcontainingthenextlargestelement. s,(If$n=1$,then2 so|r$A=\emptyset$).} M\algname{Max2}{$U$}M\begin{algtab}M\algif{$|U|=1$}sF\algreturn$(u_1,\emptyset)$\\M\algelsif{$|U|=2$}sF\algifthenelse{$u_1>u_2$}{\algreturn$(u_1,\{u_2\})$}{\algreturn$(u_2,\{u_1\})$}M\algelsesF$(b,B)\leftarrow$\algcall{Max2}{$\{u_i\}_{i=1}^{\lfloorn/2\rfloor}$}\\sF$(c,C)\leftarrow$\algcall{Max2}{$\{u_i\}_{i=\lfloorn/2\rfloor+1}^{n}$}\\sF\algifthenelse{$b>c$}{\algreturn$(b,\{c\}\cupB)$}ֿ{\algreturn$(c,\{b\}\cupC)$}M\algendM\end{algtab}M\end{algorithm}?IThereisalistofallprogrammingconstructsavqailableinthealgtabenvironment IattheendofthisdoGcument.8^TheyworkverymuchlikethemacrosusedabGove.8^AsIageneralrule,ifamacrodoGesn'ttakeanargument,aspacecharaterisincludedatItheyendofthemacrode nition.(F*orexample,typGe$a=0$?\algor\algnot$b=0$ItoUUproGduce\a=0UUornot&صb=0."!I3aLTheffImplementationLs1S cmsy9h(ow cmss9pack9age#g iLITheUUfloatpackqagebyAnselmLingnauisusedfor oatingalgorithms. 즍Ls2S\RequirePackage{float,ifthen}즍IHeredUarethevqaribledeclarations. \algmarginwidth,\alglinenowidth,andI\algtabwidthֲde netheamountofindentationoftheentirealgorithm, thespaceIreservedUUforlinenumbGers,andtheindentationmadeby\algbeginrespGectively*.Ls3S\newlength{\algmarginwidth}\setlength{\algmarginwidth}{.5in} Ls4S\newlength{\alglinenowidth}\setlength{\alglinenowidth}{1.2cm}Ls5S\newlength{\algtabwidth}\setlength{\algtabwidth}{.5cm}Ls6S\newlength{\alg@fromleft}Ls7S\newlength{\alg@tmplen}Ls8S\newsavebox{\alg@tmpbox}Ls9S\newcounter{alg@inmargin}\setcounter{alg@inmargin}{0}I10S\newcounter{algline}I11S\newboolean{alg@linenums}즍IThe stringsusedincaptionsandintheListofAlgorithmsdi erinsomelanguages.I12S\DeclareOption{english}{\def\alg@floatname{Algorithm}I13\def\alg@listname{ListofAlgorithms}I14\def\alg@descname{Description}I15\def\alg@inputname{Input}I16\def\alg@outputname{Output}}I17S\DeclareOption{american}{\def\alg@floatname{Algorithm}I18\def\alg@listname{ListofAlgorithms}3^soI19\def\alg@descname{Description} I20\def\alg@inputname{Input}I21\def\alg@outputname{Output}}I22S\DeclareOption{swedish}{\def\alg@floatname{Algoritm}I23\def\alg@listname{Algoritmer}I24\def\alg@descname{Beskrivning}I25\def\alg@inputname{Input}I26\def\alg@outputname{Output}}I27S\ExecuteOptions{english}I28S\ProcessOptionsITheUUfollowingde nitionssetupthepropGertiesofthealgorithmfloat.I29S\newcommand\floatc@alg[2]{{\bfseries\rmfamilyI30ap\hspace{\algmarginwidth}#1:}#2\par}I31S\newcommand\fs@alg{I32ap\let\@fs@capt\floatc@algI33ap\def\@fs@pre{}\def\@fs@post{}\def\@fs@mid{\vspace{3pt}}I34ap\let\@fs@iftopcapt\iftrue}I35S\floatstyle{alg}I36S\newfloat{algorithmfloat}{h}{loa}I37S\floatname{algorithmfloat}{\alg@floatname}t\listofalgorithmsIThe\listofalgorithmsmacrocanbGeusedtogeneratealistofallalgorithmsin IaUUdoGcument.I38S\newcommand{\listofalgorithms}{\listof{algorithmfloat}{\alg@listname}}alg@marginIThe8alg@marginenvironment8makesthetextabitnarrower. qThisenvironment IisusedinbGoththealgorithmandalgtabenvironments;itkeepstrackofiftheItextUUisalreadynarrow,andinthiscasedoGesnothing.I39S\newenvironment{alg@margin}{ I40ap\ifthenelse{\value{alg@inmargin}=0}{I41t\advance\leftskip\algmarginwidthI42t\advance\rightskip\algmarginwidthI43t\alg@fromleft=\leftskipI44ap}{}I45ap\stepcounter{alg@inmargin}I46ap\parskip=0cm\parindent=0cmI47S}{%I48ap\addtocounter{alg@inmargin}{-1}%I49ap\ifthenelse{\value{alg@inmargin}=0}{%I50p2\advance\leftskip-\algmarginwidth%I51p2\advance\rightskip-\algmarginwidth%I52ap}{}%I53S}$algorithmIThe algorithmenvironment simplybGeginsa oatasde nedabove.XActually*,the IdefaultZistousetheplacementparameterH,sothatthealgorithmwillnotreallyI oat.qInsideUUthe oatalltextisindentedby\algmarginwidth.I54S\newenvironment{algorithm}[1][H]{ I55ap\begin{algorithmfloat}[#1]\begin{alg@margin}I56S}{I57ap\end{alg@margin}\end{algorithmfloat}I58S}4'2so3Palg@tabIThehalg@tabenvironmenthiswhatdoGesmostoftheformattingjob;rit'scalledby IalgtabDandalgtab*de nedbGelow.Theargumentde nestheamountofinitialIindentation.X cmmi10 0ercmmi7K`y cmr10ٓRcmr7L