(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: amortize.dvi %%Pages: 4 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f amortize.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2003.02.12:1626 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (amortize.dvi) @start %DVIPSBitmapFont: Fa cmr10 10 19 /Fa 19 122 df<001C131C007F137F39FF80FF80A26D13C0A3007F137F001C131C000013 00A40001130101801380A20003130301001300485B00061306000E130E485B485B485B00 6013601A197DB92A>34 D<121C127FEAFF80A5EA7F00121C0909798817>46 D<003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770A3006017 30A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C>84 D<3901800180000313033907000700000E130E485B001813180038133800301330007013 7000601360A200E013E0485BA400CE13CE39FF80FF806D13C0A3007F137FA2393F803F80 390E000E001A1974B92A>92 D97 DI100 DI103 DII108 D<2703F00FF0EB1FE000 FFD93FFCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013 CE01FE14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA3 40257EA445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F700 13FE496D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038 FC0080491300A45BB3A2487EB512F0A31C257EA421>114 DI<1318A51338A31378A313F812011203 1207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFE EB01F81A347FB220>I121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmr7 7 1 /Fb 1 50 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmsy8 8 1 /Fc 1 1 df0 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmex10 10 1 /Fd 1 89 df88 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmmi8 8 2 /Fe 2 111 df<1307EB0F80EB1FC0A2EB0F80EB070090C7FCA9EA01E0EA07F8EA0E3CEA 1C3E123812301270EA607EEAE07C12C013FC485A120012015B12035BA21207EBC04014C0 120F13801381381F01801303EB0700EA0F06131EEA07F8EA01F0122E7EAC18>105 D<3907C007E0391FE03FF83918F8783E393879E01E39307B801F38707F00126013FEEAE0 FC12C05B00815C0001143E5BA20003147E157C5B15FC0007ECF8081618EBC00115F0000F 1538913803E0300180147016E0001F010113C015E390C7EAFF00000E143E251F7E9D2B> 110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmsy10 12 5 /Ff 5 100 df<007FB912E0BA12F0A26C18E03C04789A4D>0 D<121FEA3F80EA7FC0EAFF E0A5EA7FC0EA3F80EA1F000B0B789E1C>I<19E0F003F0180FF03FE0F0FF80943803FE00 EF0FF8EF3FE0EFFF80DC03FEC7FCEE0FF8EE3FE0EEFF80DB03FEC8FCED1FF8ED7FE09138 01FF80DA07FEC9FCEC1FF0EC7FC04948CAFCEB07FCEB1FF0EB7FC04848CBFCEA07FCEA1F F0EA7FC048CCFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF903800 7FC0EC1FF0EC07FC913801FF809138007FE0ED1FF8ED07FE923800FF80EE3FE0EE0FF8EE 03FE933800FF80EF3FE0EF0FF8EF03FE943800FF80F03FE0F00FF01803F000E01900B000 7FB912E0BA12F0A26C18E03C4E78BE4D>20 D<126012F0B3B3B3B3B3A5B512FE14FFA26C 13FE18646FCA2C>98 D<1406140FB3B3B3B3B3A5007FB5FCB6FCA26C13FE18647ECA2C> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmr8 8 3 /Fg 3 51 df48 D<130C133C137CEA03FC12FFEAFC7C1200B3 B113FE387FFFFEA2172C7AAB23>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmmi12 12 12 /Fh 12 117 df<0203B612E0021F15F091B7FC4916E0010716C090270FF80FF8C7FC9038 1FC00349486C7E017EC7FC49147E485A4848143E0007153F5B485AA2485AA2123F90C8FC 5E48157E127EA216FE00FE5D5A15015EA24B5A007C5D15074B5A5E6C4AC8FC153E6C5C5D 390F8003F03907C007C02601F03FC9FC38007FFCEB1FE0342C7DAA37>27 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A78891B>58 D<121EEA7F8012FF13C0A2 13E0A3127FEA1E601200A413E013C0A312011380120313005A1206120E5A5A5A12600B1D 78891B>I<1618163C167CA2167816F8A216F01501A216E01503A216C01507A21680150F A2ED1F00A2151E153EA2153C157CA2157815F8A25D1401A24A5AA25D1407A25D140FA292 C7FC5CA2141E143EA2143C147CA25CA25C1301A25C1303A25C1307A25C130FA291C8FC5B A2133EA2133C137CA2137813F8A25B1201A25B1203A2485AA25B120FA290C9FC5AA2121E 123EA2123C127CA2127812F8A25A126026647BCA31>61 D97 DII<141E143F5C 5CA3147E143891C7FCAE133EEBFF803801C3C0380781E0380601F0120E121CEA18031238 1230A2EA700700605BA2EAE00F00C05BEA001F5CA2133F91C7FCA25B137E13FE5BA21201 5BEC03800003140013F01207495A1406140E140CEBC01C141814385C00035BEBE1C0C6B4 5A013EC7FC19437DC121>105 D<14FE137FA3EB01FC13001301A25CA21303A25CA21307 A25CA2130FA25CA2131FA25C163F013FECFFC0923803C0E09138000703ED1E0F491338ED 701F017E13E0EC01C001FE018013C00203EB07004948C8FC140E00015B5C495A5C3803FB C001FFC9FC8014F83807F1FE9038F03F809038E00FE06E7E000F130381EBC001A2001FED 01C017801380A2003F15031700010013F05E481506160E007E150C161C00FE01005BED78 7048EC3FE00038EC0F802B467BC433>107 D<01F8EB03FCD803FEEB1FFFD8071F90387C 0FC03B0E0F80E007E03A0C07C3C003001CD9C7007F001801CE1301003801DC80003013D8 EB0FF800705B00605BA200E0491303D8C01F5D5C12001607013F5D91C7FCA2160F495D13 7E161F5F13FE49143F94C7FC187000014B136049147E16FE4C13E0000317C049150104F8 1380170300071700495D170EEE781C000FED7C3849EC1FF0D80380EC07C0342D7DAB3A> 110 D115 D<141C147EA314FE5CA313015CA313035CA313075CA2007FB512FCB6FC15F839000FC000 A2131F5CA3133F91C7FCA35B137EA313FE5BA312015BA312035BA21570000714605B15E0 15C0000F130101C013801403EC070000071306140E5C6C6C5A000113F03800FFC0013FC7 FC1E3F7EBD23>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmti12 12 27 /Fi 27 123 df<13F0EA03F8EA07FC120FA6EA03CCEA001C1318A213381330A2137013E0 13C0120113801203EA0700120E5A5A5A5A5A0E1D6BC41E>39 D<007FB5FCB6FCA214FEA2 1805789723>45 D97 DIII< EC0FE0EC7FF8903801F83E903807C00F90391F800780EB3F00017E14C0491303485A4848 1307000715805B000F140F484814005D4848133E15FCEC07F0007FEBFFC0D9FFFEC7FC14 C090C9FC5A5AA55AA4ED0180ED03C0007CEC0780A2007EEC0F00003E141E157C6C14F06C EB03E03907800F802603C07EC7FC3801FFF838003FC0222D75AB2D>II<15FCEC03 FF91390F83838091393E01CFC091387C00EF4A13FF4948137F010315804948133F495A13 1F4A1400133F91C75A5B167E13FE16FE1201495CA215011203495CA21503A2495CA21507 A25EA2150F151F5E0001143F157F6C6C13FF913801DF8090387C039F90383E0F3FEB0FFC D903F090C7FC90C7FC5DA2157EA215FEA25DA2001C495A127F48495A14074A5A485C023F C8FC00F8137E387C01F8381FFFE0000390C9FC2A407BAB2D>I<14FE137FA3EB01FC1300 1301A25CA21303A25CA21307A25CA2130FA25CA2131FA25C157F90393F83FFC091388F81 F091381E00F802387F4948137C5C4A137EA2495A91C7FCA25B484814FE5E5BA200031401 5E5BA2000714035E5B1507000F5DA249130F5E001F1678031F1370491480A2003F023F13 F0EE00E090C7FC160148023E13C01603007E1680EE070000FEEC1E0FED1F1E48EC0FF800 38EC03E02D467AC432>I<143C147E14FE1301A3EB00FC14701400AE137C48B4FC3803C7 80380703C0000F13E0120E121C13071238A21278EA700F14C0131F00F0138012E0EA003F 1400A25B137EA213FE5B12015BA212035B141E0007131C13E0A2000F133CEBC038A21478 EB807014F014E0EB81C0EA0783EBC7803803FE00EA00F8174378C11E>I<16F0ED03F8A2 1507A316F0ED01C092C7FCAEEC01F0EC07FCEC1E1EEC380F0270138014E0130114C0EB03 800107131F1400A2130E153F131E011C140090C7FC5DA2157EA215FEA25DA21401A25DA2 1403A25DA21407A25DA2140FA25DA2141FA25DA2143FA292C7FCA25C147EA214FE001C5B 127F48485A495AA248485A495AD8F81FC8FCEA707EEA3FF8EA0FC0255683C11E>I<14FE 137FA3EB01FC13001301A25CA21303A25CA21307A25CA2130FA25CA2131FA25C167E013F 49B4FC92380783C09138000E07ED3C1F491370ED603F017E13E0EC01C09026FE03801380 913907000E00D9FC0E90C7FC5C00015B5C495AEBF9C03803FB8001FFC9FCA214F03807F3 FCEBF07F9038E01FC06E7E000F130781EBC003A2001F150FA20180140EA2003F151E161C 010013E0A2485DA2007E1578167000FE01015B15F1489038007F800038021FC7FC2A467A C42D>IIIIII<91381F800C91387FE01C903901F0703C903907C03878 90390F801CF890381F001D013E130F017E14F05B48481307A2484814E012075B000F140F 16C0485AA2003F141F491480A3007F143F90C71300A35D00FE147EA315FE5DA2007E1301 A24A5A1407003E130FA26C495A143B380F80F33807C3E73901FF87E038007E071300140F 5DA3141F5DA3143F92C7FCA25CA25C017F13FEA25D263F76AB2D>III<1470EB01F8A313035CA313075CA313 0F5CA3131F5CA2007FB512E0B6FC15C0D8003FC7FCA25B137EA313FE5BA312015BA31203 5BA312075BA3120F5BA2EC0780001F140013805C140E003F131EEB001C143C14385C6C13 F0495A6C485AEB8780D807FEC7FCEA01F81B3F78BD20>I<137C48B414072603C780EB1F 80380703C0000F7F000E153F121C0107150012385E1278D8700F147E5C011F14FE00F05B 00E05DEA003FEC0001A2495C137E150313FE495CA215071201495CA2030F133800031678 49ECC070A3031F13F0EE80E0153F00011581037F13C06DEBEF8300000101148090397C03 C787903A3E0F07C70090391FFE01FE903903F000782D2D78AB34>I<017C143848B414FC 3A03C78001FE380703C0000F13E0120E001C14000107147E1238163E1278D8700F141E5C 131F00F049131C12E0EA003F91C7123C16385B137E167801FE14705BA216F0000115E05B 150116C0A24848EB0380A2ED0700A2150E12015D6D5B000014786D5B90387C01E090383F 0780D90FFFC7FCEB03F8272D78AB2D>I<017CEE038048B4020EEB0FC02603C780013FEB 1FE0380703C0000E7F5E001C037E130F01071607123804FE130300785DEA700F4A150101 1F130100F001804914C012E0EA003FDA000314034C14805B137E0307140701FE1700495C A2030F5C0001170E495CA260A24848495A60A2601201033F5C7F4B6C485A000002F71303 6D9039E7E0078090267E01C349C7FC903A1F0781F81E903A0FFF007FF8D901FCEB0FE03B 2D78AB41>I<137C48B414072603C780EB1F80380703C0000F7F000E153F001C16001307 12385E0078157EEA700F5C011F14FE00F0495B12E0EA003FEC00015E5B137E150301FE5C 5BA2150700015D5BA2150F00035D5BA2151F5EA2153F12014BC7FC6D5B00005BEB7C0390 383E0F7EEB1FFEEB03F090C712FE5DA214015D121F397F8003F0A24A5A4848485A5D4813 1F00F049C8FC0070137E007813F8383801F0381E07C06CB4C9FCEA01FC294078AB2F> 121 D<027C130749B4130F49EB800E010F141E49EBC03CEDE03890393F03F07890397C00 FDF00178EB3FE00170EB03C001F0148049130790C7EA0F00151E5D5D5D4A5A4A5A4A5A4A C7FC141E5C5C5C495A495A495A49C8FC011E14F04914E05B491301485A4848EB03C0D807 B0130701FEEB0F80390FCF801F3A1F07E07F00393E03FFFED83C015B486C5B00705C00F0 EB7FC048011FC7FC282D7BAB28>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmr12 12 62 /Fj 62 123 df<0103B612FCA390C701F0C8FC6F5A6F5AA8913801FFF0023FEBFF80903A 01FF3FDFF0D907F0EBC1FCD91FC0EBC07FD93F00EC1F8001FEED0FE048486F7E48486F7E 48486F7E48486F7E001F834982003F1880007F18C0A249163F00FF18E0A8007F18C06D16 7FA2003F1880001F18006D5E000F5F6C6C4B5A6C6C4B5A6C6C4B5A6C6C4B5A013FED1F80 D91FC0027FC7FCD907F0EBC1FCD901FFEBDFF0D9003FB51280020101F0C8FC9138003FC0 A84B7E4B7E0103B612FCA33B447BC346>8 D<9239FFC001FC020F9038F80FFF913B3F80 3E3F03C0913BFC00077E07E0D903F890390FFC0FF0494890383FF81F4948EB7FF0495A49 4814E049C7FCF00FE04991393FC0038049021F90C7FCAFB912F0A3C648C7D81FC0C7FCB3 B2486CEC3FF0007FD9FC0FB512E0A33C467EC539>11 D<4AB4FC020F13E091387F80F890 3901FC001C49487FD907E0130F4948137F011FECFF80495A49C7FCA25B49EC7F00163E93 C7FCACEE3F80B8FCA3C648C7FC167F163FB3B0486CEC7FC0007FD9FC1FB5FCA330467EC5 36>I<913801FFC0020FEBFB8091387F803F903801FC00494813FFEB07E0EB1FC0A2495A 49C7FC167F49143F5BAFB8FCA3C648C7123FB3B2486CEC7FC0007FD9FC1FB5FCA330467E C536>II<121EEA7F8012FF13C0A213E0A3127FEA1E 601200A413E013C0A312011380120313005A1206120E5A5A5A12600B1D78C41B>39 D<140C141C1438147014E0EB01C01303EB0780EB0F00A2131E5BA25B13F85B12015B1203 A2485AA3485AA348C7FCA35AA2123EA2127EA4127CA312FCB3A2127CA3127EA4123EA212 3FA27EA36C7EA36C7EA36C7EA212017F12007F13787FA27F7FA2EB0780EB03C01301EB00 E014701438141C140C166476CA26>I<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA2 1378137C133C133E131E131FA2EB0F80A3EB07C0A3EB03E0A314F0A21301A214F8A41300 A314FCB3A214F8A31301A414F0A21303A214E0A3EB07C0A3EB0F80A3EB1F00A2131E133E 133C137C13785BA2485A485AA2485A48C7FC120E5A5A5A5A5A16647BCA26>I<16C04B7E B3AB007FBAFCBB1280A26C1900C8D801E0C9FCB3AB6F5A41407BB84C>43 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380120313005A 1206120E5A5A5A12600B1D78891B>II<121EEA7F80A2EAFFC0A4 EA7F80A2EA1E000A0A78891B>I<14FF010713E090381F81F890383E007C01FC133F4848 EB1F8049130F4848EB07C04848EB03E0A2000F15F0491301001F15F8A2003F15FCA390C8 FC4815FEA54815FFB3A46C15FEA56D1301003F15FCA3001F15F8A26C6CEB03F0A36C6CEB 07E0000315C06D130F6C6CEB1F806C6CEB3F00013E137C90381F81F8903807FFE0010090 C7FC28447CC131>48 D<143014F013011303131F13FFB5FC13E713071200B3B3B0497E49 7E007FB6FCA3204278C131>II<49B4 FC010F13E0013F13FC9038FE01FE3A01F0007F80D803C0EB3FC048C7EA1FE0120EED0FF0 EA0FE0486C14F8A215077F5BA26C48130FEA03C0C813F0A3ED1FE0A2ED3FC01680ED7F00 15FE4A5AEC03F0EC1FC0D90FFFC7FC15F090380001FCEC007FED3F80ED1FC0ED0FE016F0 ED07F816FC150316FEA2150116FFA3121EEA7F80487EA416FE491303A2007EC713FC0070 1407003015F80038140F6C15F06CEC1FE06C6CEB3FC0D803E0EB7F803A01FE01FE003900 7FFFF8010F13E0010190C7FC28447CC131>II<121EEA7F80A2EAFFC0A4EA7F 80A2EA1E00C7FCB3A5121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A2B78AA1B>58 D<007FBAFCBB1280A3CEFCB0BB1280A36C190041187BA44C>61 D63 D<16C04B7EA34B7EA34B7EA34B7EA3ED19FEA3ED30FFA203707FED607FA203E07F EDC03FA2020180ED801FA2DA03007F160FA20206801607A24A6D7EA34A6D7EA34A6D7EA2 0270810260147FA202E08191B7FCA249820280C7121FA249C87F170FA20106821707A249 6F7EA3496F7EA3496F7EA201788313F8486C83D80FFF03037FB500E0027FEBFFC0A34247 7DC649>65 DIII70 D72 DI76 DIIII82 D<49B41303010FEBE007013F13 F89039FE00FE0FD801F8131FD807E0EB079F49EB03DF48486DB4FC48C8FC4881003E8112 7E82127C00FC81A282A37E82A27EA26C6C91C7FC7F7FEA3FF813FE381FFFE06C13FE6CEB FFE06C14FC6C14FF6C15C0013F14F0010F80010180D9001F7F14019138001FFF03031380 816F13C0167F163F161F17E000C0150FA31607A37EA36C16C0160F7E17806C151F6C1600 6C5D6D147ED8FBC05CD8F9F0495AD8F07C495A90393FC00FE0D8E00FB51280010149C7FC 39C0003FF02B487BC536>I<003FB912F8A3903BF0001FF8001F01806D481303003EC715 0048187C0078183CA20070181CA30060180CA5481806A5C81600B3B3A54B7EED7FFE49B7 7EA33F447DC346>I87 D97 DII<167FED3FFFA315 018182B3EC7F80903803FFF090380FC07C90383F000E017E1307496D5AD803F87F48487F 5B000F81485AA2485AA2127FA290C8FC5AAB7E7FA2123FA26C7EA2000F5D7F6C6C5B0003 5C6C6C9038077F806C6C010E13C0013F011C13FE90380FC0F8903803FFE09026007F0013 002F467DC436>IIIIII<143C14FFA249 1380A46D1300A2143C91C7FCADEC7F80EB3FFFA31300147F143FB3B3AA123E127F39FF80 7F00A2147EA25C6C485A383C01F06C485A3807FF80D801FEC7FC195785C21E>II< EA01FC12FFA3120712031201B3B3B3A5487EB512F8A315457DC41C>II<3901FC01FE00FF9038 07FFC091381E07F091383801F8000701707F0003EBE0002601FDC07F5C01FF147F91C7FC A25BA35BB3A8486CECFF80B5D8F83F13FEA32F2C7DAB36>II<3901FC03FC00FF90380FFF8091383C07E091387001F83A07FDE000FE 00010180137F01FFEC3F8091C7EA1FC04915E049140F17F0160717F8160317FCA3EE01FE ABEE03FCA3EE07F8A217F0160F6D15E0EE1FC06D143F17806EEB7E00D9FDC05B9039FCF0 03F891383C0FE091381FFF80DA03FCC7FC91C9FCAE487EB512F8A32F3F7DAB36>I<9138 7F8003903903FFE00790380FE07890393F801C0F90387E000E496D5AD803F8EB039F0007 EC01BF4914FF48487F121F5B003F81A2485AA348C8FCAB6C7EA3123F7F121F6D5C120F6D 5B12076C6C5B6C6C497E6C6C130E013F131C90380FC0F8903803FFE09038007F0091C7FC AEEEFF80033F13FEA32F3F7DAB33>I<3903F803F000FFEB1FFCEC3C3EEC707F0007EBE0 FF3803F9C000015B13FBEC007E153C01FF13005BA45BB3A748B4FCB512FEA3202C7DAB26 >I<90383FE0183901FFFC383907E01F78390F0003F8001E1301481300007C1478127800 F81438A21518A27EA27E6C6C13006C7E13FC383FFFE06C13FC6C13FF6C14C06C14E0C614 F0011F13F81300EC0FFC140300C0EB01FE1400157E7E153EA27EA36C143C6C147C15786C 14F86CEB01F039F38003E039F1F00F8039E07FFE0038C00FF01F2E7DAC26>I<1306A513 0EA4131EA3133E137EA213FE12011207001FB512F0B6FCA2C648C7FCB3A4150CAA017E13 1C017F1318A26D133890381F8030ECC070903807E0E0903801FFC09038007F001E3E7EBC 26>IIIIII<003FB612E0A290 38C0003F90C713C0003CEC7F800038ECFF00A20030495A0070495AA24A5A0060495AA24A 5A4A5AA2C7485A4AC7FC5B5C495A13075C495A131F4A1360495A495AA249C712C0485AA2 485A485A1501485A48481303A24848EB07804848131F00FF14FF90B6FCA2232B7DAA2B> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmbx12 14.4 23 /Fk 23 123 df46 D<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7FCB3 B3B3A6007FB712FEA52F4E76CD43>49 DI58 D<171F4D7E4D7EA24D7EA34C7FA2 4C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C7E03018116F8830303814C 7E03078116E083030F814C7E031F81168083033F8293C77E4B82157E8403FE824B800201 835D840203834B800207835D844AB87EA24A83A3DA3F80C88092C97E4A84A2027E8202FE 844A82010185A24A820103854A82010785A24A82010F855C011F717FEBFFFCB600F8020F B712E0A55B547BD366>65 D73 D97 D<913801FFF8021FEBFF8091B612F0010315FC010F9038C00FFE903A1FFE0001FFD97FFC 491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC486F1300705A4892C8FC5B A312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F6CEE1F806C6DEC3F006C6D 147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A01001580023F49C7FC020113E0 33387CB63C>99 D<4DB47E0407B5FCA5EE001F1707B3A4913801FFE0021F13FC91B6FC01 0315C7010F9038E03FE74990380007F7D97FFC0101B5FC49487F4849143F484980485B83 485B5A91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F6C6D5C7E6C6D5C6C6D49B5 FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B5128F0101ECFE0FD9003F13 F8020301C049C7FC41547CD24B>I<913803FFC0023F13FC49B6FC010715C04901817F90 3A3FFC007FF849486D7E49486D7E4849130F48496D7E48178048497F18C0488191C7FC48 17E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E14 037E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0F FFC03FF8010390B55A010015C0021F49C7FC020113F034387CB63D>I<137F497E000313 E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0B5FCA512017EB3B3A6B612 E0A51B547BD325>105 D108 DII<913801FFE0021F13FE91B6 12C0010315F0010F9038807FFC903A1FFC000FFED97FF86D6C7E49486D7F48496D7F4849 6D7F4A147F48834890C86C7EA24883A248486F7EA3007F1880A400FF18C0AC007F1880A3 003F18006D5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE 011F90C7FC903A0FFF807FFC6D90B55A010015C0023F91C8FC020113E03A387CB643>I< 903A3FF001FFE0B5010F13FE033FEBFFC092B612F002F301017F913AF7F8007FFE0003D9 FFE0EB1FFFC602806D7F92C76C7F4A824A6E7F4A6E7FA2717FA285187F85A4721380AC1A 0060A36118FFA2615F616E4A5BA26E4A5B6E4A5B6F495B6F4990C7FC03F0EBFFFC9126FB FE075B02F8B612E06F1480031F01FCC8FC030313C092CBFCB1B612F8A5414D7BB54B>I< 90397FE003FEB590380FFF80033F13E04B13F09238FE1FF89139E1F83FFC0003D9E3E013 FEC6ECC07FECE78014EF150014EE02FEEB3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612 FCA52F367CB537>114 D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307 D81FE0130148487F4980127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15 F86C14FF16C06C15F06C816C816C81C681013F1580010F15C01300020714E0EC003F0307 13F015010078EC007F00F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC 7F0001FEEB01FE9039FFC00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB6 35>I<143EA6147EA414FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FC A426003FFEC8FCB3A9EE07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEB FFF86D6C5B021F5B020313802A4D7ECB34>II<007FB5 00F090387FFFFEA5C66C48C7000F90C7FC6D6CEC07F86D6D5C6D6D495A6D4B5A6F495A6D 6D91C8FC6D6D137E6D6D5B91387FFE014C5A6E6C485A6EEB8FE06EEBCFC06EEBFF806E91 C9FCA26E5B6E5B6F7E6F7EA26F7F834B7F4B7F92B5FCDA01FD7F03F87F4A486C7E4A486C 7E020F7FDA1FC0804A486C7F4A486C7F02FE6D7F4A6D7F495A49486D7F01076F7E49486E 7E49486E7FEBFFF0B500FE49B612C0A542357EB447>120 DI<001FB8FC1880A3912680007F130001FCC7B5FC01F0495B495D49495B495B4B5B48C75C 5D4B5B5F003E4A90C7FC92B5FC4A5B5E4A5B5CC7485B5E4A5B5C4A5B93C8FC91B5FC495B 5D4949EB0F805B495B5D495B49151F4949140092C7FC495A485E485B5C485E485B4A5C48 495B4815074849495A91C712FFB8FCA37E31357CB43C>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmti12 17.28 9 /Fl 9 117 df46 D<92B912F04A18FEF3FFC06E19F0DB007F90C700017F70489138003FFE 7048ED0FFF043F04037F757F4D6F7F767E047F173F767E4D707EA204FF717EA24D707EA2 4B1A80885FA24B1AC0A25F885D1EE094CBFCA25D645EA2151FA25EA2153F645E1EC0157F A24C5FA215FF1E804C5FA25C1E004C5FA24A62A24C173F655C525A93CBFCA24A4F5AA24B 4D5BA2021F62515B5D5190C7FC023F611B0F4B4D5A64027F183F515A4B60515A02FF4D5B 5090C8FC4B4C5A1A0F49F01FF8505A4B4C5A505A494D5B070790C9FC4BED1FFC4F5A4993 3801FFE04904071380013FDC7FFECAFC007FB912F8BA12E096CBFC18F0636276E16A>68 D83 D97 D101 D<15FC903801FFFE133F 15FCA3EB003FEC1FF8140F141FA215F0A2143FA215E0A2147FA215C0A214FFA21580A25B A21500A25BA25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA25CA213FFA2 5CA25AA291C7FCA25AA25BA21207A25BA2120FA25BA2121FA25BA2123FEC01C0EBE003A2 007F1307158013C0A2140F00FF140013805C141EA2007F133E143C147C1478003F13F838 1F81F0EBC3E03807FFC06C5BD8007EC7FC1F6573E324>108 D<4BB4FC031F13E0037F13 F8913901FF01FE913907F8007FDA1FE0EB3F804A48EB1FC0DAFF8014E04948C7EA0FF049 48EC07F81307494815FC49481403495A017F16FE495A5C5A4890C813FFA25A5B120F495D 121FA2485AA25F007F17FE5BA2171F00FF17FC5BA2173F18F85BEF7FF0A218E017FF18C0 A2494A138018005E5F6C6C4A5A4C5AA2003F4B5A6D4A5A001F4B5A000F4BC7FC6D495A6C 6C495A6C6CEB0FF06C6C495A3A007F80FF806DB448C8FC010F13F001011380384070BE48 >111 D114 D<15F0EC01FC14031407A3140FA25DA2 141FA25DA2143FA25DA2147FA25DA214FFA25DA25B007FB612FEB7FCA216FCD8000390C7 FC5CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA25CA213FFA25CA25AA291 C8FCA25AA25BA2120716704914F0A2000F140116E049130316C01507001F158049130F16 005D153E000F143C5D15F84A5A0007495A6C6C485AEC1F802600FFFEC7FCEB7FF8EB0FE0 275A72D82F>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmr17 17.28 12 /Fm 12 123 df<170FA34D7EA24D7EA34D7EA34D7EA34C7F17DFA29338039FFC178FA293 38070FFE1707040F7FEE0E03A2041E80EE1C01A2043C80EE3800A24C80187FA24C80183F A24B4880181F0303814C130FA203078193C71207A24B81030E80A24B8284A24B8284A24B 82197F03F0824B153FA20201834B151FA202038392B8FCA24A83A292C91207020E8385A2 4A8485023C84023882A20278840270177FA202F0844A173FA24948841A1FA24948841A0F A249CB7F1A074985865B496C85497E48486C4D7F000F01F8051F13F0B60407B612F0A45C 657DE463>65 D78 D97 D101 D<133C13FF487F487FA66C5B6C90C7FC133C90C8FCB3A2EB03C0EA07FF127FA41201EA00 7FA2133FB3B3AC497E497EB612E0A41B5F7DDE23>105 D109 DII<9039078003F8D807FFEB0FFFB5 013F13C092387C0FE0913881F01F9238E03FF00001EB838039007F8700148FEB3F8E029C EB1FE0EE0FC00298EB030002B890C7FCA214B014F0A25CA55CB3B0497EEBFFF8B612FCA4 2C3F7CBE33>114 D<9139FFE00180010FEBFC03017FEBFF073A01FF001FCFD803F8EB03 EFD807E0EB01FF48487F4848147F48C8123F003E151F007E150F127CA200FC1507A31603 7EA27E7F6C7E6D91C7FC13F8EA3FFE381FFFF06CEBFF806C14F86C14FF6C15C06C6C14F0 011F80010714FED9007F7F02031480DA003F13C01503030013E0167F00E0ED1FF0160F17 F86C15071603A36C1501A37EA26C16F016037E17E06D14076DEC0FC06D1580D8FDF0141F D8F8F8EC7F00013E14FC3AF01FC00FF80107B512E0D8E001148027C0003FF8C7FC2D417D BF34>I<1438A71478A414F8A31301A31303A21307130F131FA2137F13FF1203000F90B6 FCB8FCA3260007F8C8FCB3AE17E0AE6D6CEB01C0A316036D6C148016076D6C14006E6C5A 91383FC01E91381FF07C6EB45A020313E09138007F802B597FD733>I<001FB81280A391 C70001130001F85C01E05D01804A5A160F90C8485A001E5E4C5A48157F5F4C5A5D94C7FC 00384A5A15074B5A5E4B5A153F5EC8485A15FF5E4A90C8FC5C5D4A5A140F4A5A5D4A5A14 7F5D4A48EB03805B92C7FC495A13075C4948EC0700131F495A5C495A13FF4A5C4890C8FC 5A495D485A000F5E48485D4915FE48481401007F150749147FB8FCA3313E7DBD3A>122 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 1289 107 a Fm(Notes)44 b(on)f(Amortization)1629 289 y Fl(D.)50 b(Sle)-7 b(ator)150 866 y Fk(1.)60 b(In)l(tro)t(duction) 150 1051 y Fj(A)30 b Fi(data)h(structur)-5 b(e)39 b Fj(is)29 b(a)g(w)m(a)m(y)i(of)e(represen)m(ting)h(information)d(in)h(a)i (computer)f(and)h(a)f(set)h(of)f(pro-)150 1172 y(cedures)37 b(for)e(accessing)h(and)f(up)s(dating)f(the)i(information.)48 b(These)37 b(pro)s(cedures)g(for)e(accessing)150 1292 y(and)e(up)s(dating)e(the)i(information)d(are)i(called)g(the)h Fi(op)-5 b(er)g(ations)40 b Fj(on)32 b(the)h(data)f(structure.)296 1412 y(There)44 b(are)e(t)m(w)m(o)g(fundamen)m(tally)f(di\013eren)m(t)h (w)m(a)m(ys)i(in)d(whic)m(h)i(data)f(structures)h(are)f(used.)150 1533 y(They)c(are)e(used)i(as)e(part)g(of)g(an)g(information)d(retriev) -5 b(al)35 b(system,)j(and)f(they)g(are)f(used)i(as)e(one)150 1653 y(comp)s(onen)m(t)d(of)f(an)g(algorithm)e(whose)j(purp)s(ose)h(is) e(to)g(solv)m(e)h(some)f(other)h(problem.)296 1773 y(Wh)m(y)f(do)f(w)m (e)g(ha)m(v)m(e)h(data)f(structures?)44 b(In)31 b(the)g(\014rst)g (application)d(the)j(purp)s(ose)h(of)e(the)h(data)150 1894 y(structure)h(is)e(ob)m(vious,)h(for)f(the)g(data)g(structure)i (itself)d(is)h(solving)f(the)i(problem)e(that)h(w)m(e)i(w)m(an)m(t)150 2014 y(to)38 b(solv)m(e.)60 b(In)38 b(the)h(second)g(application,)e (the)i(reason)f(for)g(ha)m(ving)g(data)f(structures)j(is)e(not)f(so)150 2135 y(ob)m(vious.)46 b(In)34 b(this)f(case)i(our)e(motiv)-5 b(ation)30 b(for)j(creating)g(them)g(is)g(to)g(aid)g(in)f(our)i (conception)f(of)150 2255 y(the)26 b(algorithm.)38 b(By)26 b(using)f(a)g(data)g(structure)i(as)f(a)f(comp)s(onen)m(t)g(of)g(an)h (algorithm,)e(w)m(e)i(split)e(the)150 2375 y(problem)37 b(of)h(creating)f(or)h(expressing)h(the)g(algorithm)c(in)m(to)i(t)m(w)m (o)i(parts.)60 b(Once)39 b(the)g(in)m(terface)150 2496 y(b)s(et)m(w)m(een)29 b(these)g(t)m(w)m(o)f(parts)f(has)h(b)s(een)g(sp) s(eci\014ed,)h(these)g(t)m(w)m(o)f(comp)s(onen)m(ts)g(of)f(the)g (problem)f(can)150 2616 y(b)s(e)33 b(solv)m(ed)g(\(or)f(expressed\))j (separately)-8 b(.)296 2737 y(The)34 b(in)m(terface)e(b)s(et)m(w)m(een) j(a)d(data)g(structure)h(and)g(the)g(algorithm)c(that)j(uses)i(it)d (consists)i(of)150 2857 y(t)m(w)m(o)g(parts:)269 3038 y(1.)49 b(A)44 b(set)g(of)g(op)s(erations)f(that)h(allo)m(w)e(the)i (algorithm)d(to)j(access)h(and)f(up)s(date)h(the)f(data)394 3158 y(structure.)269 3354 y(2.)49 b(Constrain)m(ts)29 b(that)f(sa)m(y)i(ho)m(w)f(m)m(uc)m(h)g(time)f(\(or)g(space\))i(eac)m (h)f(op)s(eration)e(is)i(allo)m(w)m(ed)e(to)i(use)394 3474 y(in)j(order)g(for)g(the)h(algorithm)d(to)i(p)s(erform)g(with)g (the)h(desired)g(e\016ciency)-8 b(.)150 3655 y(The)29 b(structure)g(of)e(this)h(in)m(terface)f(implies)f(that)h(the)h(data)g (structure)h(m)m(ust)f(p)s(erform)f(in)g(an)g(on-)150 3776 y(line)k(fashion,)h(that)g(is,)g(it)g(m)m(ust)g(p)s(erform)g(the)h (curren)m(t)g(op)s(eration)e(b)s(efore)i(it)e(kno)m(ws)j(what)f(the)150 3896 y(future)h(op)s(erations)e(will)f(b)s(e.)45 b(F)-8 b(urthermore,)33 b(no)g(assumptions)g(are)g(made)g(ab)s(out)g(the)g (pattern)150 4016 y(of)43 b(op)s(erations)f(done)h(b)m(y)i(the)e (algorithm.)72 b(The)44 b(data)f(structure)h(should)f(ha)m(v)m(e)i(the) e(desired)150 4137 y(p)s(erformance)32 b(for)g(an)m(y)h(sequence.)296 4257 y(This)27 b(note)g(describ)s(es)h(a)e(tec)m(hnique)i(that)f(has)g (b)s(een)g(used)h(to)f(design)f(impro)m(v)m(ed)h(data)f(struc-)150 4378 y(tures,)31 b(and)g(to)e(analyze)h(their)g(p)s(erformance.)42 b(These)32 b(adv)-5 b(ances)31 b(w)m(ere)h(not)e(made)f(b)m(y)i(c)m (hanging)150 4498 y(the)e(in)m(terface)f(b)s(et)m(w)m(een)j(the)d(data) g(structure)i(and)f(the)f(algorithm)d(that)k(uses)g(it.)42 b(Rather,)29 b(they)150 4618 y(w)m(ere)36 b(made)f(b)m(y)h(allo)m(wing) c(the)j(data)g(structure)h(to)f(tak)m(e)g(full)e(adv)-5 b(an)m(tage)35 b(of)g(the)g(\015exibilit)m(y)e(of)150 4739 y(this)f(in)m(terface.)296 4859 y(The)38 b(\014rst)e(observ)-5 b(ation)36 b(is)g(the)h(follo)m(wing:)48 b(Although)35 b(the)i(p)s(erformance)f(b)s(ounds)h(on)f(the)150 4979 y(data)29 b(structure)h(are)g(sp)s(eci\014ed)g(b)m(y)g(the)g(in)m (terface,)g(these)g(b)s(ounds)g(do)f(not)g(ha)m(v)m(e)i(to)e(b)s(e)g (satis\014ed)150 5100 y(b)m(y)37 b(the)f(data)g(structure)h(for)f(ev)m (ery)i(single)d(op)s(eration.)52 b(All)35 b(that)g(is)h(actually)f (needed)i(is)f(that)150 5220 y(the)i(cost)h(of)e(sequence)k(of)d(op)s (erations)f(b)s(e)h(b)s(ounded)h(b)m(y)g(the)f(sum)g(of)g(the)g(sp)s (eci\014ed)h(b)s(ounds.)150 5341 y(An)34 b(analysis)f(of)g(the)h(w)m (orst)g(case)h(cost)f(of)f(a)g Fi(se)-5 b(quenc)g(e)41 b Fj(of)33 b(op)s(erations)f(is)i(called)e(an)i Fi(amortize)-5 b(d)150 5461 y(analysis)8 b Fj(.)1922 5710 y(1)p eop %%Page: 2 2 2 1 bop 296 107 a Fj(F)-8 b(or)34 b(example)h(supp)s(ose)h(a)f (sequence)j(of)c(op)s(erations)g Fh(\033)2363 122 y Fg(1)2403 107 y Fh(;)17 b(\033)2502 122 y Fg(2)2542 107 y Fh(;)g Ff(\001)g(\001)g(\001)d Fh(;)j(\033)2817 122 y Fe(n)2899 107 y Fj(is)35 b(to)f(b)s(e)i(appled)e(to)h(a)150 227 y(data)i(structure.)58 b(Sa)m(y)38 b(that)f(the)g(in)m(terface)g (requires)h(that)f(the)h(time)d(tak)m(en)j(b)m(y)g(op)s(eration)e Fh(\033)3715 242 y Fe(i)150 348 y Fj(b)s(e)k(at)f(most)g Fh(b)p Fj(\()p Fh(\033)796 363 y Fe(i)825 348 y Fj(\).)64 b(In)40 b(order)f(for)g(the)h(data)f(structure)i(to)e(satisfy)h(the)f (requiremen)m(t)h(of)f(the)150 468 y(in)m(terface,)33 b(it)e(is)h Fi(not)42 b Fj(necessary)35 b(that:)1669 688 y Fh(t)p Fj(\()p Fh(\033)1797 703 y Fe(i)1826 688 y Fj(\))27 b Ff(\024)i Fh(b)p Fj(\()p Fh(\033)2131 703 y Fe(i)2160 688 y Fj(\))p Fh(;)150 908 y Fj(rather,)k(what)g(is)f (required)h(is)f(that)1571 1072 y Fe(n)1533 1097 y Fd(X)1580 1279 y Fe(i)1669 1180 y Fh(t)p Fj(\()p Fh(\033)1797 1195 y Fe(i)1826 1180 y Fj(\))27 b Ff(\024)2035 1072 y Fe(n)1997 1097 y Fd(X)2045 1279 y Fe(i)2133 1180 y Fh(b)p Fj(\()p Fh(\033)2267 1195 y Fe(i)2296 1180 y Fj(\))p Fh(:)150 1465 y Fj(If)g(the)h(data)f(structure)i(has)e(this)g(prop)s(ert)m(y)-8 b(,)29 b(then)f(the)g(op)s(eration)e Fh(\033)2667 1480 y Fe(i)2723 1465 y Fj(is)h(said)f(to)h(tak)m(e)i Fi(amortize)-5 b(d)150 1585 y(time)77 b Fh(b)p Fj(\()p Fh(\033)548 1600 y Fe(i)577 1585 y Fj(\).)59 b(\(This)38 b(de\014nition)f(of)g(the)h (amortized)f(time)f(of)i(an)f(op)s(eration)g(is)g(sligh)m(tly)f(more) 150 1706 y(restricted)k(than)f(that)h(used)g(in)f(the)h(sequel.)65 b(Ho)m(w)m(ev)m(er,)43 b(an)m(y)d(b)s(ounds)h(satisfying)d(the)i(ab)s (o)m(v)m(e)150 1826 y(inequalit)m(y)32 b(certainly)f(satisfy)i(our)f (more)g(lib)s(eral)e(de\014nition)h(giv)m(en)i(b)s(elo)m(w.\))296 1946 y(The)45 b(second)f(imp)s(ortan)m(t)d(observ)-5 b(ation)43 b(is)g(that)g(although)m(t)f(the)i(data)f(structure)i (cannot)150 2067 y(kno)m(w)24 b(the)e(future)h(op)s(erations,)h(it)d (is)h(allo)m(w)m(ed)g(to)g(use)h(the)g(information)c(it)j(has)h(ab)s (out)f(op)s(erations)150 2187 y(that)31 b(w)m(ere)i(done)f(in)f(the)h (past.)43 b(It)32 b(turns)g(out)g(that)f(a)g(useful)h(tec)m(hnique)h (in)d(constructing)i(data)150 2307 y(structures)44 b(that)e(are)g (e\016cien)m(t)h(in)e(the)i(amortized)e(sense)j(is)d(to)h(ha)m(v)m(e)h (the)g(structure)g(adjust)150 2428 y(itself)29 b(based)i(on)f(past)g (requests.)45 b(Informally)-8 b(,)28 b(w)m(e)j(call)e(suc)m(h)i(a)f (data)g(structure)h Fi(self-adjusting)9 b Fj(.)296 2548 y(Amortized)29 b(analysis)h(and)g(self-adjustmen)m(t)g(ha)m(v)m(e)h(b)s (een)g(used)g(to)f(devise)h(a)f(v)-5 b(ariet)m(y)30 b(of)g(e\016-)150 2669 y(cien)m(t)f(new)g(data)g(structures.)44 b(In)29 b(the)g(next)g(section)g(w)m(e)h(illustrate)c(the)k(concepts)g(of)e (amortized)150 2789 y(analysis)k(with)g(a)g(simple)f(example.)150 3078 y Fk(2.)60 b(Amortized)46 b(analysis:)61 b(an)45 b(example)150 3263 y Fj(T)-8 b(o)26 b(illustrate)e(the)j(concepts)g(of) f(amortized)f(analysis)g(I)i(shall)d(use)j(a)f(simple)f(example.)41 b(Supp)s(ose)150 3383 y(that)27 b(the)h(cost)f(of)g(incremen)m(ting)g (a)g(binary)f(n)m(um)m(b)s(er)i(is)f(the)h(n)m(um)m(b)s(er)f(of)g(bits) g(in)f(it)h(that)g(c)m(hange.)150 3503 y(What)33 b(is)f(the)h(cost)g (of)f(incremen)m(ting)f(a)i(binary)f(n)m(um)m(b)s(er)h(from)e(0)i(to)f Fh(n)p Fj(?)296 3624 y(It)47 b(is)e(easy)j(to)d(see)j(that)e(on)g(eac)m (h)h(incremen)m(t)f(op)s(eration)f(the)i(lo)m(w)e(order)i(bit)e(c)m (hanges.)150 3744 y(Th)m(us,)38 b(the)d(n)m(um)m(b)s(er)h(of)f(times)f (this)h(bit)f(c)m(hanges)j(is)e Fh(n)p Fj(.)52 b(The)36 b(2's)f(bit)g(c)m(hanges)i(on)e(the)g(second)150 3864 y(incremen)m(t)c(op)s(eration,)f(and)h(on)g(alternate)g(subsequen)m(t)j (op)s(erations,)d(th)m(us)h(it)e(c)m(hanges)i(a)f(total)150 3985 y(of)h Ff(b)p Fh(n=)p Fj(2)p Ff(c)c(\024)g Fh(n=)p Fj(2)33 b(times.)42 b(Similarly)-8 b(,)29 b(the)k Fh(i)p Fj(th)g(bit)f(c)m(hanges)i(at)e(most)g Fh(n=)p Fj(2)2912 3949 y Fe(i)p Fc(\000)p Fg(1)3062 3985 y Fj(times.)43 b(Th)m(us)34 b(the)150 4105 y(total)d(cost)i(of)f(this)g(sequence)k(of) c(incremen)m(ts)h(is)f(at)g(most)1469 4343 y Fh(n)22 b Fj(+)1657 4275 y Fh(n)p 1657 4320 59 4 v 1662 4411 a Fj(2)1747 4343 y(+)1855 4275 y Fh(n)p 1855 4320 V 1860 4411 a Fj(4)1946 4343 y(+)g Ff(\001)17 b(\001)g(\001)25 b Fj(=)j(2)p Fh(n:)150 4588 y Fj(Th)m(us,)34 b(b)m(y)g(the)e (de\014nition)g(of)g(amortized)f(cost,)i(the)g(incremen)m(t)g(op)s (eration)e(has)i(an)f(amortized)150 4709 y(cost)g(of)e(2.)43 b(Notice)31 b(that)g(some)g(individual)d(incremen)m(t)k(op)s(eration)d (ma)m(y)i(cause)i Ff(b)p Fj(log)17 b Fh(n)p Ff(c)31 b Fj(bits)g(to)150 4829 y(c)m(hange.)510 4793 y Fg(1)296 4949 y Fj(Another)25 b(w)m(a)m(y)g(to)f(pro)m(v)m(e)h(this)f(result)g (is)f(m)m(y)i(means)f(of)f(the)i Fi(b)-5 b(anker's)26 b(view)50 b Fj(of)24 b(amortization.)150 5070 y(Supp)s(ose)41 b(that)f(eac)m(h)h(time)d(a)i(bit)f(of)h(the)g(binary)g(n)m(um)m(b)s (er)g(c)m(hanges)i(it)d(costs)i(us)f(one)h(dollar.)150 5190 y(Also,)34 b(supp)s(ose)i(that)e(w)m(e)i(main)m(tain)c(a)i(bank)h (accoun)m(t)g(suc)m(h)h(that)e(for)g(eac)m(h)i(bit)d(of)h(the)h(binary) p 150 5258 1438 4 v 262 5319 a Fb(1)299 5350 y Fa(The)28 b(sym)n(b)r(ol)f(\\log")g(denotes)g(the)h(binary)f(logarithm.)1922 5710 y Fj(2)p eop %%Page: 3 3 3 2 bop 150 107 a Fj(n)m(um)m(b)s(er)30 b(that)g(is)f(a)g(1)h(w)m(e)h (k)m(eep)g(a)e(dollar)f(in)h(the)h(accoun)m(t.)43 b(Initially)27 b(there)k(is)e(no)g(money)h(in)f(the)150 227 y(accoun)m(t.)296 348 y(What)39 b(happ)s(ens)h(when)g(the)g(binary)e(n)m(um)m(b)s(er)h (is)g(incremen)m(ted?)63 b(A)39 b(sequence)i(of)e(zero)g(or)150 468 y(more)e(1's)i(all)d(c)m(hange)j(to)e(0's,)j(and)e(then)h(a)f(0)f (c)m(hanges)j(to)e(a)f(1.)60 b(F)-8 b(or)37 b(eac)m(h)i(bit)e(that)h(c) m(hanges)150 588 y(from)g(a)i(1)f(to)h(a)f(0,)j(w)m(e)e(tak)m(e)h(a)e (dollar)f(from)g(the)i(accoun)m(t)h(to)e(pa)m(y)i(for)e(it.)64 b(F)-8 b(or)39 b(the)h(bit)f(that)150 709 y(c)m(hanges)e(from)d(a)h(0)h (to)f(a)g(1,)h(w)m(e)h(m)m(ust)f(pa)m(y)g(for)f(c)m(hanging)g(the)h (bit,)g(and)f(w)m(e)i(m)m(ust)f(also)e(put)i(a)150 829 y(dollar)i(in)h(the)h(bank)h(to)e(main)m(tain)f(the)i(relationship)e(b) s(et)m(w)m(een)k(the)e(bank)h(accoun)m(t)f(and)g(the)150 949 y(n)m(um)m(b)s(er.)j(Th)m(us)33 b(our)f(out)f(of)g(p)s(o)s(c)m(k)m (et)h(cost)g(to)f(pa)m(y)h(for)f(the)g(incremen)m(t)h(is)e(exactly)i(t) m(w)m(o)g(dollars,)150 1070 y(no)42 b(matter)g(ho)m(w)h(big)e(the)i(n)m (um)m(b)s(er)g(is)f(or)g(ho)m(w)h(man)m(y)f(carries)g(o)s(ccur.)74 b(In)42 b(a)g(sequence)k(of)c Fh(n)150 1190 y Fj(incremen)m(t)30 b(op)s(erations,)g(our)g(total)f(cost)i(is)e(2)p Fh(n)h Fj(dollars)f(and)h(w)m(e)h(are)g(left)e(with)h(a)g(non-negativ)m(e)150 1311 y(bank)j(accoun)m(t.)44 b(Therefore)34 b(the)f(total)e(cost)i(of)f (all)f(the)i(incremen)m(ts)g(is)f(at)g(most)g(2)p Fh(n)p Fj(.)296 1431 y(This)i(tec)m(hnique)i(can)e(b)s(e)g(applied)f(in)g(a)h (m)m(uc)m(h)h(more)e(general)g(w)m(a)m(y)-8 b(.)49 b(The)35 b(idea)e(is)h(to)g(mak)m(e)150 1551 y(a)29 b(rule)g(that)g(sa)m(ys)i (ho)m(w)f(m)m(uc)m(h)f(money)h(m)m(ust)f(b)s(e)h(k)m(ept)g(in)f(the)h (bank)f(as)h(a)f(function)g(of)g(the)g(state)150 1672 y(of)k(the)i(data)e(structure.)49 b(Then)35 b(a)f(b)s(ound)g(is)g (obtained)f(on)h(ho)m(w)h(m)m(uc)m(h)f(money)g(is)g(required)g(to)150 1792 y(pa)m(y)f(for)f(an)h(op)s(eration)e(and)i(main)m(tain)d(the)j (appropriate)f(amoun)m(t)g(of)g(money)g(in)g(the)h(bank.)296 1913 y(The)28 b Fi(physist's)h(view)36 b Fj(of)26 b(amortization)d (uses)28 b(di\013eren)m(t)f(terminology)d(to)i(describ)s(e)h(the)g (same)150 2033 y(idea.)50 b(This)36 b(is)e(the)i(form)m(ulation)c(I)j (shall)f(use)i(in)e(this)h(course.)52 b(A)35 b Fi(p)-5 b(otential)37 b(function)42 b Fj(\010\()p Fh(s)p Fj(\))35 b(is)150 2153 y(a)d(mapping)f(from)g(data)h(state)h(structure)g(states) h(to)e(the)g(reals.)43 b(\(This)33 b(tak)m(es)h(the)e(place)g(of)g(the) 150 2274 y(bank)h(accoun)m(t)h(in)d(the)i(bank)m(er's)i(view.\))296 2394 y(Consider)44 b(a)e(sequence)k(of)d Fh(n)g Fj(op)s(erations)f Fh(\033)1983 2409 y Fg(1)2023 2394 y Fh(;)17 b(\033)2122 2409 y Fg(2)2161 2394 y Fh(;)g(:)g(:)g(:)f(;)h(\033)2435 2409 y Fe(n)2525 2394 y Fj(the)44 b(data)e(structure.)76 b(Let)43 b(the)150 2514 y(sequence)c(of)d(states)h(through)f(whic)m(h)h (the)g(data)f(structure)h(passes)h(b)s(e)f Fh(s)2909 2529 y Fg(0)2948 2514 y Fh(;)17 b(s)3038 2529 y Fg(1)3077 2514 y Fh(;)g(:)g(:)g(:)f(;)h(s)3342 2529 y Fe(n)3389 2514 y Fj(.)54 b(Notice)150 2635 y(that)36 b(op)s(eration)f Fh(\033)860 2650 y Fe(i)924 2635 y Fj(c)m(hanges)j(the)e(state)h(from)e Fh(s)1983 2650 y Fe(i)p Fc(\000)p Fg(1)2137 2635 y Fj(to)h Fh(s)2306 2650 y Fe(i)2334 2635 y Fj(.)54 b(Let)36 b(the)h(cost)f(of)g (op)s(eration)f Fh(\033)3579 2650 y Fe(i)3643 2635 y Fj(b)s(e)150 2755 y Fh(c)192 2770 y Fe(i)220 2755 y Fj(.)44 b(De\014ne)33 b(the)g(amortized)e(cost)i Fh(ac)1510 2770 y Fe(i)1571 2755 y Fj(of)f(op)s(eration)f Fh(\033)2173 2770 y Fe(i)2234 2755 y Fj(b)m(y)j(the)f(follo)m(wing)d(form)m(ula:) 1353 2975 y Fh(ac)1446 2990 y Fe(i)1534 2975 y Fj(=)61 b Fh(c)1713 2990 y Fe(i)1763 2975 y Fj(+)22 b(\010\()p Fh(s)2015 2990 y Fe(i)2043 2975 y Fj(\))g Ff(\000)h Fj(\010\()p Fh(s)2357 2990 y Fe(i)p Fc(\000)p Fg(1)2476 2975 y Fj(\))p Fh(;)1078 b Fj(\(1\))150 3194 y(or)711 3314 y(\(amortized)31 b(cost)q(\))60 b(=)g(\(actual)31 b(cost)q(\))22 b(+)g(\(c)m(hange)34 b(in)d(p)s(oten)m(tial)o(\))p Fh(:)150 3489 y Fj(If)g(w)m(e)h(sum)e(b)s (oth)h(sides)g(of)f(this)h(equation)f(o)m(v)m(er)i(all)d(the)i(op)s (erations,)g(w)m(e)g(obtain)f(the)h(follo)m(wing)150 3609 y(form)m(ula:)640 3745 y Fd(X)687 3928 y Fe(i)776 3828 y Fh(ac)869 3843 y Fe(i)958 3828 y Fj(=)1110 3745 y Fd(X)1158 3928 y Fe(i)1230 3828 y Fj(\()p Fh(c)1310 3843 y Fe(i)1360 3828 y Fj(+)22 b(\010\()p Fh(s)1612 3843 y Fe(i)1641 3828 y Fj(\))g Ff(\000)h Fj(\010\()p Fh(s)1955 3843 y Fe(i)p Fc(\000)p Fg(1)2073 3828 y Fj(\))60 b(=)h(\010\()p Fh(s)2462 3843 y Fe(n)2509 3828 y Fj(\))22 b Ff(\000)h Fj(\010\()p Fh(s)2823 3843 y Fg(0)2862 3828 y Fj(\))f(+)3020 3745 y Fd(X)3068 3928 y Fe(i)3157 3828 y Fh(c)3199 3843 y Fe(i)3227 3828 y Fh(:)150 4111 y Fj(Rearranging)31 b(w)m(e)j(get)1209 4149 y Fd(X)1256 4331 y Fe(i)1345 4232 y Fh(c)1387 4247 y Fe(i)1475 4232 y Fj(=)60 b(\()1649 4149 y Fd(X)1697 4331 y Fe(i)1786 4232 y Fh(ac)1879 4247 y Fe(i)1907 4232 y Fj(\))22 b(+)g(\010\()p Fh(s)2219 4247 y Fg(0)2259 4232 y Fj(\))g Ff(\000)h Fj(\010\()p Fh(s)2573 4247 y Fe(n)2620 4232 y Fj(\))p Fh(:)934 b Fj(\(2\))150 4476 y(If)33 b(\010\()p Fh(s)402 4491 y Fg(0)441 4476 y Fj(\))28 b Ff(\024)g Fj(\010\()p Fh(s)766 4491 y Fe(n)813 4476 y Fj(\))33 b(\(as)g(will)d(frequen)m(tly)j(b)s(e)g (the)g(case\))h(w)m(e)f(get)1635 4612 y Fd(X)1683 4795 y Fe(i)1771 4695 y Fh(c)1813 4710 y Fe(i)1869 4695 y Ff(\024)1974 4612 y Fd(X)2022 4795 y Fe(i)2111 4695 y Fh(ac)2204 4710 y Fe(i)2232 4695 y Fh(:)1360 b Fj(\(3\))150 4979 y(Th)m(us,)45 b(if)39 b(w)m(e)j(can)f(b)s(ound)h(the)f(amortized)e (cost)j(of)e(eac)m(h)i(of)f(the)g(op)s(erations,)h(and)f(the)g(\014nal) 150 5100 y(p)s(oten)m(tial)32 b(is)h(at)h(least)f(as)h(large)e(as)i (the)h(initial)29 b(p)s(oten)m(tial,)k(then)h(the)g(b)s(ound)g(w)m(e)h (obtained)e(for)150 5220 y(the)g(amortized)e(cost)i(applies)f(to)g(the) h(actual)f(cost.)296 5341 y(W)-8 b(e)32 b(can)g(no)m(w)g(apply)g(this)f (tec)m(hnique)i(to)e(the)h(problem)e(of)i(computing)e(the)i(cost)g(of)f (binary)150 5461 y(coun)m(ting.)44 b(Let)33 b(the)g(p)s(oten)m(tial)e (\010)i(b)s(e)g(the)g(n)m(um)m(b)s(er)h(of)e(1's)h(in)f(the)h(curren)m (t)h(n)m(um)m(b)s(er.)44 b(Our)33 b(\014rst)1922 5710 y(3)p eop %%Page: 4 4 4 3 bop 150 107 a Fj(goal)29 b(is)g(to)h(sho)m(w)h(that)f(with)g(this)g (p)s(oten)m(tial)e(the)j(amortized)e(cost)h(of)g(an)g(incremen)m(t)g (op)s(eration)150 227 y(is)i(2.)296 348 y(Consider)40 b(the)f Fh(i)p Fj(th)g(incremen)m(t)g(op)s(eration)f(that)g(c)m(hanges) i(the)g(n)m(um)m(b)s(er)f(from)f Fh(i)26 b Ff(\000)h Fj(1)39 b(to)f Fh(i)p Fj(.)150 468 y(Let)e Fh(k)j Fj(b)s(e)d(the)g(n)m (um)m(b)s(er)g(of)f(carries)h(that)f(o)s(ccur)h(as)g(a)f(result)h(of)f (the)h(incremen)m(t.)53 b(The)37 b(cost)f(of)150 588 y(the)h(op)s(eration)e(is)h Fh(k)28 b Fj(+)d(1.)54 b(The)38 b(c)m(hange)f(in)f(p)s(oten)m(tial)f(caused)i(b)m(y)h(the)f(op)s (eration)e(is)h Ff(\000)p Fh(k)28 b Fj(+)d(1.)150 709 y(\(The)36 b(n)m(um)m(b)s(er)f(of)f(bits)h(that)f(c)m(hange)i(from)e(1) g(to)h(0)f(is)g Fh(k)k Fj(and)d(one)g(bit)f(c)m(hanges)i(from)e(0)g(to) h(1.\))150 829 y(Therefore)f(the)f(amortized)e(cost)i(of)f(the)h(op)s (eration)e(is)1357 1049 y Fh(ac)1450 1064 y Fe(i)1506 1049 y Fj(=)d Fh(k)d Fj(+)d(1)g(+)g(\()p Ff(\000)p Fh(k)k Fj(+)c(1\))27 b(=)h(2)p Fh(:)150 1269 y Fj(Since)38 b(the)h(\014nal)e (p)s(oten)m(tial)f(is)i(more)g(than)g(the)g(initial)d(p)s(oten)m(tial,) i(w)m(e)j(can)e(apply)g(inequalit)m(y)150 1389 y(\(3\))32 b(to)g(obtain:)1515 1547 y Fd(X)1563 1730 y Fe(i)1652 1630 y Fh(c)1694 1645 y Fe(i)1750 1630 y Ff(\024)1855 1547 y Fd(X)1903 1730 y Fe(i)1992 1630 y Fh(ac)2085 1645 y Fe(i)2141 1630 y Fj(=)27 b(2)p Fh(n:)296 1869 y Fj(Notice)34 b(that)g(in)f(this)h(form)m(ulation,)e(the)j(de\014nition)e(of)h(the)g (amortized)f(cost)i(of)e(an)h(op)s(era-)150 1990 y(tion)e(dep)s(ends)i (on)f(the)h(c)m(hoice)f(of)f(the)i(p)s(oten)m(tial)d(function.)44 b(In)33 b(fact,)g(an)m(y)h(c)m(hoice)f(of)f(p)s(oten)m(tial)150 2110 y(function)44 b(whatso)s(ev)m(er)j(de\014nes)f(an)f(amortized)f (cost)h(of)f(eac)m(h)i(op)s(eration.)79 b(Ho)m(w)m(ev)m(er,)50 b(these)150 2230 y(amortized)33 b(b)s(ounds)j(will)d(not)h(b)s(e)h (useful)g(unless)h(\010\()p Fh(s)2173 2245 y Fg(0)2212 2230 y Fj(\))24 b Ff(\000)g Fj(\010\()p Fh(s)2529 2245 y Fe(n)2577 2230 y Fj(\))34 b(is)h(also)f(b)s(ounded)h(appropri-)150 2351 y(ately)-8 b(.)296 2471 y(W)g(e)38 b(ha)m(v)m(e)h(giv)m(en)e(t)m (w)m(o)h(di\013eren)m(t)g(de\014nitions)f(of)g(amortized)f(cost,)j(one) e(in)g(Section)g(1,)i(and)150 2592 y(the)c(other)f(in)f(equation)h(1.) 48 b(Whic)m(h)35 b(de\014nition)e(applies)g(in)h(a)g(discussion)g(will) e(dep)s(end)j(on)f(the)150 2712 y(con)m(text)j(of)e(the)h(discussion.) 53 b(If)35 b(w)m(e)i(discuss)g(amortized)d(cost)i(in)f(the)h(con)m (text)h(of)e(a)g(p)s(oten)m(tial)150 2832 y(function,)j(then)f(the)g (amortized)f(cost)h(is)g(that)f(de\014ned)j(b)m(y)e(equation)g(1.)56 b(If)37 b(it)f(is)g(outside)h(the)150 2953 y(con)m(text)g(of)e(a)g(p)s (oten)m(tial)e(function,)j(then)g(the)g(meaning)e(of)h(amortized)f (cost)i(is)f(that)g(giv)m(en)g(in)150 3073 y(Section)d(1.)296 3193 y(Most)k(of)f(the)h(art)f(of)g(doing)f(an)h(amortized)f(analysis)h (is)g(in)f(c)m(ho)s(osing)h(the)h(righ)m(t)e(p)s(oten)m(tial)150 3314 y(function.)43 b(Once)33 b(a)g(p)s(oten)m(tial)d(function)j(is)f (c)m(hosen)i(w)m(e)f(m)m(ust)g(do)g(t)m(w)m(o)g(things:)269 3517 y(1.)49 b(Pro)m(v)m(e)32 b(that)f(with)f(the)h(c)m(hosen)i(p)s (oten)m(tial)c(function,)h(the)i(amortized)d(costs)j(of)e(the)h(op)s (er-)394 3638 y(ations)h(satisfy)g(the)h(desired)g(b)s(ounds.)269 3841 y(2.)49 b(Bound)33 b(the)g(quan)m(tit)m(y)g(\010\()p Fh(s)1419 3856 y Fg(0)1459 3841 y Fj(\))22 b Ff(\000)h Fj(\010\()p Fh(s)1773 3856 y Fe(n)1820 3841 y Fj(\))32 b(appropriately)-8 b(.)1922 5710 y(4)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF