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