{VERSION 2 3 "DEC ALPHA UNIX" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 0 21 "" 0 1 0 0 0 1 0 0 0 0 2 0 0 0 0 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Out put" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "B ullet Item" 0 15 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 0 0 0 -1 3 3 0 0 0 0 0 0 15 2 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 261 34 "Algorithm Analysis with \+ combstruct" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "The " }{HYPERLNK 17 "combstruct" 2 "combstruct" "" }{TEXT -1 474 " package is used to define and manipulate combinatorial structure s. Once defined by a combstruct grammar, a structure can be counted, \+ randomly generated, exhaustively generated, and its counting generatin g function can be found. In addition, a combstruct procedure can be c reated to describe an algorithm which acts on objects of that structur e. There are tools available in the combstruct package to find the co mplexity descriptor generating function of the algorithm. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "If " }{XPPEDIT 18 0 "f" "I\"fG6\"" }{TEXT -1 78 " is a description of a procedure whi ch acts on a combinatorial structure type " }{XPPEDIT 18 0 "A" "I\"AG6 \"" }{TEXT -1 55 ", then the complexity descriptor generating function is" }}{PARA 256 "" 0 "" {XPPEDIT 18 0 "tau[f](z) = Sum(c[n]*z^n, n=0. .infinity)" "/-&%$tauG6#%\"fG6#%\"zG-%$SumG6$*&&%\"cG6#%\"nG\"\"\")F)F 1F2/F1;\"\"!%)infinityG" }}{PARA 0 "" 0 "" {TEXT -1 6 "where " } {XPPEDIT 18 0 "c[n]" "&%\"cG6#%\"nG" }{TEXT -1 51 " counts the total c ost of operations required when " }{XPPEDIT 18 0 "f" "I\"fG6\"" } {TEXT -1 36 " is applied to every object of size " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 6 " from " }{XPPEDIT 18 0 "A" "I\"AG6\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 355 "These methods can be applied to a wide range of problems, includi ng regular languages, context-free languages and combinatorial problem s. Examples include analyzing a function over a regular expression, P ollard's rho-method for integer factorization, pathlength of various k inds of trees, strategies for binary powering, and mutually recursive \+ functions." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "For instructions regarding how to define a combinatorial struct ure see " }{HYPERLNK 17 "combstruct[specification]" 2 "combstruct[spec ification]" "" }{TEXT -1 43 ". For writing procedure descriptions, se e " }{HYPERLNK 17 "combstruct[prog_specification]" 2 "combstruct[prog_ specification]" "" }{TEXT -1 13 ". An older " }{HYPERLNK 17 "introdu ction" 1 "why.ms" "" }{TEXT -1 30 " to the combstruct package, a " } {HYPERLNK 17 "guide to writing grammar specifications" 1 "how.ms" "" } {TEXT -1 6 ", and " }{HYPERLNK 17 "examples" 1 "new.mws" "gfstuff" } {TEXT -1 120 " of finding the generating functions associated with the grammar specifications are all available in example worksheets." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "with(combstruct);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7.%+allstructsG%&countG%%drawG%)finishedG%'g feqnsG%)gfseriesG%(gfsolveG%,iterstructsG%+nextstructG%,prog_gfeqnsG%. prog_gfseriesG%-prog_gfsolveG" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 " Examples" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 15 "Binary Powering" }} {PARA 0 "" 0 "" {TEXT -1 86 "As a simple example, consider the problem of binary powering. The goal is to compute " }{XPPEDIT 18 0 "x^k" ") %\"xG%\"kG" }{TEXT -1 44 " using few operations. The key is to write \+ " }{XPPEDIT 18 0 "k" "I\"kG6\"" }{TEXT -1 35 " in binary notation. Fo r example " }{XPPEDIT 18 0 "x^29" "*$%\"xG\"#H" }{TEXT -1 20 " can be written as " }{XPPEDIT 18 0 "x^16" "*$%\"xG\"#;" }{TEXT -1 1 " " } {XPPEDIT 18 0 "x^8" "*$%\"xG\"\")" }{TEXT -1 1 " " }{XPPEDIT 18 0 "x^4 " "*$%\"xG\"\"%" }{TEXT -1 1 " " }{XPPEDIT 18 0 "x" "I\"xG6\"" }{TEXT -1 189 ", so its calculation involves only a few multiplication and s quaring operations. This method is particularly useful in cases where the multiplication operation is expensive, such as when " }{TEXT 259 1 "x" }{TEXT -1 100 " is a matrix. We find the total number of multip lication and squaring operations needed to compute " }{XPPEDIT 18 0 "x ^k" ")%\"xG%\"kG" }{TEXT -1 6 " when " }{XPPEDIT 18 0 "k" "I\"kG6\"" } {TEXT -1 62 " is a random integer whose binary representation is of le ngth " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "To define this problem, we start with a grammar to describe " }{TEXT 260 1 "k" }{TEXT -1 15 " . The integer " }{XPPEDIT 18 0 "k" "I\"kG6\"" }{TEXT -1 77 " is repre sented in its binary represenation as a sequence of ones and zeros. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "sys := \{chain=Sequence(bi t),bit=Union(zero,one),zero=Atom,one=Atom\}:" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 35 "We will work with unlabelled atoms." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "typ := unlabelled:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Then we describe the algorithm to compute " }{XPPEDIT 18 0 "x^k" ")%\"xG%\"kG" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 481 "binpower := proc(k::chain)\nlocal c1,b;\n if Type (k, Epsilon) then # k=0\n nil\n elif Typematch(k, specfunc (b::bit, c1::anything,Sequence))\n then\n if Type(b,zero) \+ then # k is even \n # binpower(x,iquo(k,2))^2 \n binpower(c1);\n squaring;\n elif Type( b,one) then # k is odd\n # binpower(x,iquo(k,2))^2 * x\n \+ binpower(c1);\n squaring;\n multiply; \n fi;\n fi;\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 " We define the cost of the basic statements used in the algorithm by gi ving them complexity measures." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "measures := \{squaring = 1, multiply = 1\}:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "Now we look for the generating functions. The \+ function " }{HYPERLNK 17 "combstruct[prog_gfsolve]" 2 "combstruct[prog _gfsolve]" "" }{TEXT -1 159 " finds exact expressions for the counting generating functions of the non-terminals of the grammar and the comp lexity descriptors of the program descriptions. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "prog_gfsolve([sys,typ,\{'binpower'=binpower\} , measures], z);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<'/-%$oneG6#%\"zGF (/-%%zeroGF'F(/-&%$tauG6#%)binpowerGF',$*&F(\"\"\",(F4F4F(!\"%*$F(\"\" #\"\"%!\"\"\"\"$/-%&chainGF',$*$,&F:F4F(F8F:F:/-%$bitGF',$F(F8" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "The truncated series of these gene rating functions can also be found using the function " }{HYPERLNK 17 "combstruct[prog_gfseries]" 2 "combstruct[prog_gfseries]" "" }{TEXT -1 42 ". The order of the series is based on the " }{HYPERLNK 17 "Orde r" 2 "Order" "" }{TEXT -1 22 " environment variable." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Order := 15:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 60 "prog_gfseries([sys,typ,\{'binpower'=binpower\}, mea sures], z);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%&TABLEG6#7'/-%%zeroG6 #%\"zG+%F+\"\"\"\"\"\"/-%$bitGF*+%F+\"\"#\"\"\"/-%$oneGF*F,/-%&chainGF *+CF+F-\"\"!F3\"\"\"\"\"%\"\"#\"\")\"\"$\"#;\"\"%\"#K\"\"&\"#k\"\"'\"$ G\"\"\"(\"$c#\"\")\"$7&\"\"*\"%C5\"#5\"%[?\"#6\"%'4%\"#7\"%#>)\"#8\"&% Q;\"#9-%\"OG6#F-\"#:/-&%$tauG6#%)binpowerGF*+AF+\"\"$\"\"\"\"#7\"\"#\" #O\"\"$\"#'*\"\"%\"$S#\"\"&\"$w&\"\"'\"%W8\"\"(\"%sI\"\")\"%7p\"\"*\"& g`\"\"#5\"&#zL\"#6\"&GP(\"#7\"'W(f\"\"#8\"'kSM\"#9FX\"#:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 240 "This result means that there are 8 chain s of length 3, and a total of 36 multiplications and squarings are nee ded to apply the function binpower to all 8 chains. Thus the average \+ number of operations on 3-bit long exponents is 36/8 = 4.5." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "The function " }{HYPERLNK 17 "combstruct[prog_gfeqns]" 2 "combstruct[prog_gfeqns]" " " }{TEXT -1 205 " returns the system of generating function equations \+ for this problem. It can be particularly useful on those occasions wh ere the solver is unable to find an exact expression for the generatin g functions." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "prog_gfeqns ([sys,typ,\{'binpower'=binpower\}, measures], z);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7'/-&%$tauG6#%)binpowerG6#%\"zG,**&F%\"\"\"-%%zeroGF*F. F.*&F/F.-%&chainGF*F.F.*&F%F.-%$oneGF*F.F.*&F5F.F2F.\"\"#/F5F+/F/F+/-% $bitGF*,&F/F.F5F./F2*$,&F.F.F " 0 "" {MPLTEXT 1 0 108 "sys := \{Tree= Union(node, tree), tree=Prod(node,tree2), \ntree2=Set(Tree,card=2), no de=Atom\}:\ntyp := labelled:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 172 " The path length algorithm will make use of this procedure to find the \+ tree size (number of nodes). It counts one for a node, and then recur sively traverses the subtrees. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 284 "treesize := proc(t::Tree)\nlocal s, x;\n if Type(t,node) then \n count\n elif Type(t, tree) then\n if Typematch(t, \+ specfunc(node, s::anything,Prod)) then\n count;\n \+ for x in s do\n treesize(x)\n od\n \+ fi;\n fi;\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "The in ternal pathlength is the sum of the distances of all nodes to the root , computed recursively as the size plus the pathlength of the subtrees . " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 293 "pathlength := proc(t::Tree) \nlocal s, x;\n if Type(t,node) then\n nil\n elif Type(t, tree) then\n if Typematch(t, specfunc(node, s::anything,Prod)) then\n for x in s do\n treesize(x);\n \+ pathlength(x)\n od\n fi;\n fi;\nend:\n " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "A cost of 1 is assigned to ea ch count operation." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "measures := \+ \{count=1\}:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "Then the same fun ctions as before can be used to find the generating functions." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "prog_gfsolve([sys,typ,\{'treesize'= treesize,'pathlength'=pathlength\}, measures], x);" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#<(/-%%nodeG6#%\"xGF(/-%%TreeGF',$*&F(!\"\",&\"\"#\"\" \"*$,&F1F1*$F(F0!\"##F1F0F5F1F6/-%&tree2GF',$*&,&F-#F.F0F(F1F1F(F.F./- %%treeGF',&F-F6F(F./-&%$tauG6#%)treesizeGF',$*(F(F.F/F1F3F=F6/-&FE6#%+ pathlengthGF',$*&F " 0 "" {MPLTEXT 1 0 84 "prog_gfseries([sys,typ,\{'treesize'=treesize,'pathlen gth'=pathlength\}, measures], x);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#- %&TABLEG6#7(/-&%$tauG6#%)treesizeG6#%\"xG+3F.\"\"\"\"\"\"#\"\"$\"\"#\" \"$#\"\"&F4\"\"&#\"#N\"\")\"\"(#\"#jF;\"\"*#\"$J#\"#;\"#6#\"$H%FB\"#8- %\"OG6#F0\"#:/-%%nodeGF-+%F.F0\"\"\"/-&F*6#%+pathlengthGF-+1F.F0\"\"$F 3\"\"&#\"#H\"\"%\"\"(#\"#lFZ\"\"*#\"$\"GF;\"#6#\"$&fF;\"#8FG\"#:/-%&tr ee2GF-+3F.#F0F4\"\"#Fdo\"\"%#F7F;\"\"'#\"\"(F;\"\")#\"#@FB\"#5#\"#LFB \"#7#FE\"$G\"\"#9FG\"#;/-%%TreeGF-+3F.F0\"\"\"Fdo\"\"$Fdo\"\"&Fgo\"\"( Fio\"\"*F\\p\"#6F_p\"#8FG\"#:/-%%treeGF-+1F.Fdo\"\"$Fdo\"\"&Fgo\"\"(Fi o\"\"*F\\p\"#6F_p\"#8FG\"#:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 284 "B ecause we are working in the labelled universe, the generating functio ns are exponential generating functions. Thus there are 5! * 1/2 = 60 trees with 5 nodes, and the total pathlength of those 60 trees is 5! \+ * 3 = 360, so the average pathlength of a tree with 5 nodes is 360/60= 6. " }}{PARA 0 "" 0 "" {TEXT -1 108 "We can re-define our tree so that each node has exactly 0 or 3 children, and then reuse the same algori thms." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 91 "sys := \{Tree=Unio n(node, tree), tree=Prod(node,tree2), \ntree2=Set(Tree,card=3), node=A tom\}:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "prog_gfseries([sy s,typ,\{'treesize'=treesize,'pathlength'=pathlength\}, measures], x); " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%&TABLEG6#7(/-&%$tauG6#%)treesize G6#%\"xG+/F.\"\"\"\"\"\"#\"\"#\"\"$\"\"%#\"\"(\"#7\"\"(#\"\"&\"\"*\"#5 #\"$:(\"%'H\"\"#8-%\"OG6#F0\"#;/-%%nodeGF-+%F.F0\"\"\"/-&F*6#%+pathlen gthGF-+-F.#F0F3\"\"%#F4\"\"%\"\"(#\"#B\"#C\"#5#\"$^#\"$;#\"#8FB\"#;/-% &tree2GF-+-F.#F0\"\"'\"\"$#F0F8\"\"'#F0\"#=\"\"*#\"#bF@\"#7FB\"#:/-%%T reeGF-+/F.F0\"\"\"F]o\"\"%F`o\"\"(Fbo\"#5Feo\"#8FB\"#;/-%%treeGF-+-F.F ]o\"\"%F`o\"\"(Fbo\"#5Feo\"#8FB\"#;" }}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 10 "References" }}{PARA 0 "" 0 "" {TEXT -1 119 "The following are a list of references relevant to a previous incarnation of this p rogram called Lamba-Upsilon-Omega, (" }{XPPEDIT 18 0 "Lambda" "I'Lambd aG6\"" }{TEXT -1 1 "-" }{XPPEDIT 18 0 "Upsilon" "I(UpsilonG6\"" } {TEXT -1 2 "- " }{XPPEDIT 18 0 "Omega" "I&OmegaG6\"" }{TEXT -1 290 ") \+ or LUO for short. They contain the theoretical foundations of this pr ogram and examples of other applications. The code for LUO, written in a combination of Maple and Caml, and electronic versions of these pap ers are available from http://www-rocq.inria.fr/algo/libraries/librari es.html." }}{PARA 15 "" 0 "" {TEXT 256 45 "Automatic average-case anal ysis of algorithms" }{TEXT -1 103 " P. Flajolet, B. Salvy and P. Zimme rmann. Theoretical Computer Science, Series A, vol. 79, no. 1, 1991." }}{PARA 15 "" 0 "" {TEXT 257 38 "Lambda-Upsilon-Omega the 1989 cookboo k" }{TEXT -1 76 " (INRIA Research Report 1073) P. Flajolet, B. Salvy a nd P. Zimmermann, 1989." }}{PARA 15 "" 0 "" {TEXT 258 55 "Lambda-Upsil on-Omega : an assistant algorithms analyzer" }{TEXT -1 175 " P. Flajol et, B. Salvy and P. Zimmermann. Applied Algebra, Algebraic Algorithms \+ and Error-Correcting Codes. T. Mora (editor). Lecture Notes in Compute r Science vol. 357, 1989." }}}}{MARK "1 0 0" 17 }{VIEWOPTS 1 1 0 1 1 1803 }