(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvipsk 5.86 p1.5d Copyright 1996-2001 ASCII Corp.(www-ptex@ascii.co.jp) %%based on dvipsk 5.86 Copyright 1999 Radical Eye Software (www.radicaleye.com) %%Title: quicksort.dvi %%Pages: 9 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips quicksort.dvi -t letter -o quicksort.ps %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2003.01.21:1548 %%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 /dir 0 def/dyy{/dir 0 def}B/dyt{/dir 1 def}B/dty{/dir 2 def}B/dtt{/dir 3 def}B/p{dir 2 eq{-90 rotate show 90 rotate}{dir 3 eq{-90 rotate show 90 rotate}{show}ifelse}ifelse}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 %%BeginProcSet: pstricks.pro %! % PostScript prologue for pstricks.tex. % Version 97 patch 3, 98/06/01 % For distribution, see pstricks.tex. % /tx@Dict 200 dict def tx@Dict begin /ADict 25 dict def /CM { matrix currentmatrix } bind def /SLW /setlinewidth load def /CLW /currentlinewidth load def /CP /currentpoint load def /ED { exch def } bind def /L /lineto load def /T /translate load def /TMatrix { } def /RAngle { 0 } def /Atan { /atan load stopped { pop pop 0 } if } def /Div { dup 0 eq { pop } { div } ifelse } def /NET { neg exch neg exch T } def /Pyth { dup mul exch dup mul add sqrt } def /PtoC { 2 copy cos mul 3 1 roll sin mul } def /PathLength@ { /z z y y1 sub x x1 sub Pyth add def /y1 y def /x1 x def } def /PathLength { flattenpath /z 0 def { /y1 ED /x1 ED /y2 y1 def /x2 x1 def } { /y ED /x ED PathLength@ } {} { /y y2 def /x x2 def PathLength@ } /pathforall load stopped { pop pop pop pop } if z } def /STP { .996264 dup scale } def /STV { SDict begin normalscale end STP } def /DashLine { dup 0 gt { /a .5 def PathLength exch div } { pop /a 1 def PathLength } ifelse /b ED /x ED /y ED /z y x add def b a .5 sub 2 mul y mul sub z Div round z mul a .5 sub 2 mul y mul add b exch Div dup y mul /y ED x mul /x ED x 0 gt y 0 gt and { [ y x ] 1 a sub y mul } { [ 1 0 ] 0 } ifelse setdash stroke } def /DotLine { /b PathLength def /a ED /z ED /y CLW def /z y z add def a 0 gt { /b b a div def } { a 0 eq { /b b y sub def } { a -3 eq { /b b y add def } if } ifelse } ifelse [ 0 b b z Div round Div dup 0 le { pop 1 } if ] a 0 gt { 0 } { y 2 div a -2 gt { neg } if } ifelse setdash 1 setlinecap stroke } def /LineFill { gsave abs CLW add /a ED a 0 dtransform round exch round exch 2 copy idtransform exch Atan rotate idtransform pop /a ED .25 .25 % DG/SR modification begin - Dec. 12, 1997 - Patch 2 %itransform translate pathbbox /y2 ED a Div ceiling cvi /x2 ED /y1 ED a itransform pathbbox /y2 ED a Div ceiling cvi /x2 ED /y1 ED a % DG/SR modification end Div cvi /x1 ED /y2 y2 y1 sub def clip newpath 2 setlinecap systemdict /setstrokeadjust known { true setstrokeadjust } if x2 x1 sub 1 add { x1 % DG/SR modification begin - Jun. 1, 1998 - Patch 3 (from Michael Vulis) % a mul y1 moveto 0 y2 rlineto stroke /x1 x1 1 add def } repeat grestore } % def a mul y1 moveto 0 y2 rlineto stroke /x1 x1 1 add def } repeat grestore pop pop } def % DG/SR modification end /BeginArrow { ADict begin /@mtrx CM def gsave 2 copy T 2 index sub neg exch 3 index sub exch Atan rotate newpath } def /EndArrow { @mtrx setmatrix CP grestore end } def /Arrow { CLW mul add dup 2 div /w ED mul dup /h ED mul /a ED { 0 h T 1 -1 scale } if w neg h moveto 0 0 L w h L w neg a neg rlineto gsave fill grestore } def /Tbar { CLW mul add /z ED z -2 div CLW 2 div moveto z 0 rlineto stroke 0 CLW moveto } def /Bracket { CLW mul add dup CLW sub 2 div /x ED mul CLW add /y ED /z CLW 2 div def x neg y moveto x neg CLW 2 div L x CLW 2 div L x y L stroke 0 CLW moveto } def /RoundBracket { CLW mul add dup 2 div /x ED mul /y ED /mtrx CM def 0 CLW 2 div T x y mul 0 ne { x y scale } if 1 1 moveto .85 .5 .35 0 0 0 curveto -.35 0 -.85 .5 -1 1 curveto mtrx setmatrix stroke 0 CLW moveto } def /SD { 0 360 arc fill } def /EndDot { { /z DS def } { /z 0 def } ifelse /b ED 0 z DS SD b { 0 z DS CLW sub SD } if 0 DS z add CLW 4 div sub moveto } def /Shadow { [ { /moveto load } { /lineto load } { /curveto load } { /closepath load } /pathforall load stopped { pop pop pop pop CP /moveto load } if ] cvx newpath 3 1 roll T exec } def /NArray { aload length 2 div dup dup cvi eq not { exch pop } if /n exch cvi def } def /NArray { /f ED counttomark 2 div dup cvi /n ED n eq not { exch pop } if f { ] aload /Points ED } { n 2 mul 1 add -1 roll pop } ifelse } def /Line { NArray n 0 eq not { n 1 eq { 0 0 /n 2 def } if ArrowA /n n 2 sub def n { Lineto } repeat CP 4 2 roll ArrowB L pop pop } if } def /Arcto { /a [ 6 -2 roll ] cvx def a r /arcto load stopped { 5 } { 4 } ifelse { pop } repeat a } def /CheckClosed { dup n 2 mul 1 sub index eq 2 index n 2 mul 1 add index eq and { pop pop /n n 1 sub def } if } def /Polygon { NArray n 2 eq { 0 0 /n 3 def } if n 3 lt { n { pop pop } repeat } { n 3 gt { CheckClosed } if n 2 mul -2 roll /y0 ED /x0 ED /y1 ED /x1 ED x1 y1 /x1 x0 x1 add 2 div def /y1 y0 y1 add 2 div def x1 y1 moveto /n n 2 sub def n { Lineto } repeat x1 y1 x0 y0 6 4 roll Lineto Lineto pop pop closepath } ifelse } def /Diamond { /mtrx CM def T rotate /h ED /w ED dup 0 eq { pop } { CLW mul neg /d ED /a w h Atan def /h d a sin Div h add def /w d a cos Div w add def } ifelse mark w 2 div h 2 div w 0 0 h neg w neg 0 0 h w 2 div h 2 div /ArrowA { moveto } def /ArrowB { } def false Line closepath mtrx setmatrix } def % DG modification begin - Jan. 15, 1997 %/Triangle { /mtrx CM def translate rotate /h ED 2 div /w ED dup 0 eq { %pop } { CLW mul /d ED /h h d w h Atan sin Div sub def /w w d h w Atan 2 %div dup cos exch sin Div mul sub def } ifelse mark 0 d w neg d 0 h w d 0 %d /ArrowA { moveto } def /ArrowB { } def false Line closepath mtrx %setmatrix } def /Triangle { /mtrx CM def translate rotate /h ED 2 div /w ED dup CLW mul /d ED /h h d w h Atan sin Div sub def /w w d h w Atan 2 div dup cos exch sin Div mul sub def mark 0 d w neg d 0 h w d 0 d /ArrowA { moveto } def /ArrowB { } def false Line closepath mtrx % DG/SR modification begin - Jun. 1, 1998 - Patch 3 (from Michael Vulis) % setmatrix } def setmatrix pop } def % DG/SR modification end /CCA { /y ED /x ED 2 copy y sub /dy1 ED x sub /dx1 ED /l1 dx1 dy1 Pyth def } def /CCA { /y ED /x ED 2 copy y sub /dy1 ED x sub /dx1 ED /l1 dx1 dy1 Pyth def } def /CC { /l0 l1 def /x1 x dx sub def /y1 y dy sub def /dx0 dx1 def /dy0 dy1 def CCA /dx dx0 l1 c exp mul dx1 l0 c exp mul add def /dy dy0 l1 c exp mul dy1 l0 c exp mul add def /m dx0 dy0 Atan dx1 dy1 Atan sub 2 div cos abs b exp a mul dx dy Pyth Div 2 div def /x2 x l0 dx mul m mul sub def /y2 y l0 dy mul m mul sub def /dx l1 dx mul m mul neg def /dy l1 dy mul m mul neg def } def /IC { /c c 1 add def c 0 lt { /c 0 def } { c 3 gt { /c 3 def } if } ifelse /a a 2 mul 3 div 45 cos b exp div def CCA /dx 0 def /dy 0 def } def /BOC { IC CC x2 y2 x1 y1 ArrowA CP 4 2 roll x y curveto } def /NC { CC x1 y1 x2 y2 x y curveto } def /EOC { x dx sub y dy sub 4 2 roll ArrowB 2 copy curveto } def /BAC { IC CC x y moveto CC x1 y1 CP ArrowA } def /NAC { x2 y2 x y curveto CC x1 y1 } def /EAC { x2 y2 x y ArrowB curveto pop pop } def /OpenCurve { NArray n 3 lt { n { pop pop } repeat } { BOC /n n 3 sub def n { NC } repeat EOC } ifelse } def /AltCurve { { false NArray n 2 mul 2 roll [ n 2 mul 3 sub 1 roll ] aload /Points ED n 2 mul -2 roll } { false NArray } ifelse n 4 lt { n { pop pop } repeat } { BAC /n n 4 sub def n { NAC } repeat EAC } ifelse } def /ClosedCurve { NArray n 3 lt { n { pop pop } repeat } { n 3 gt { CheckClosed } if 6 copy n 2 mul 6 add 6 roll IC CC x y moveto n { NC } repeat closepath pop pop } ifelse } def /SQ { /r ED r r moveto r r neg L r neg r neg L r neg r L fill } def /ST { /y ED /x ED x y moveto x neg y L 0 x L fill } def /SP { /r ED gsave 0 r moveto 4 { 72 rotate 0 r L } repeat fill grestore } def /FontDot { DS 2 mul dup matrix scale matrix concatmatrix exch matrix rotate matrix concatmatrix exch findfont exch makefont setfont } def /Rect { x1 y1 y2 add 2 div moveto x1 y2 lineto x2 y2 lineto x2 y1 lineto x1 y1 lineto closepath } def /OvalFrame { x1 x2 eq y1 y2 eq or { pop pop x1 y1 moveto x2 y2 L } { y1 y2 sub abs x1 x2 sub abs 2 copy gt { exch pop } { pop } ifelse 2 div exch { dup 3 1 roll mul exch } if 2 copy lt { pop } { exch pop } ifelse /b ED x1 y1 y2 add 2 div moveto x1 y2 x2 y2 b arcto x2 y2 x2 y1 b arcto x2 y1 x1 y1 b arcto x1 y1 x1 y2 b arcto 16 { pop } repeat closepath } ifelse } def /Frame { CLW mul /a ED 3 -1 roll 2 copy gt { exch } if a sub /y2 ED a add /y1 ED 2 copy gt { exch } if a sub /x2 ED a add /x1 ED 1 index 0 eq { pop pop Rect } { OvalFrame } ifelse } def /BezierNArray { /f ED counttomark 2 div dup cvi /n ED n eq not { exch pop } if n 1 sub neg 3 mod 3 add 3 mod { 0 0 /n n 1 add def } repeat f { ] aload /Points ED } { n 2 mul 1 add -1 roll pop } ifelse } def /OpenBezier { BezierNArray n 1 eq { pop pop } { ArrowA n 4 sub 3 idiv { 6 2 roll 4 2 roll curveto } repeat 6 2 roll 4 2 roll ArrowB curveto } ifelse } def /ClosedBezier { BezierNArray n 1 eq { pop pop } { moveto n 1 sub 3 idiv { 6 2 roll 4 2 roll curveto } repeat closepath } ifelse } def /BezierShowPoints { gsave Points aload length 2 div cvi /n ED moveto n 1 sub { lineto } repeat CLW 2 div SLW [ 4 4 ] 0 setdash stroke grestore } def /Parab { /y0 exch def /x0 exch def /y1 exch def /x1 exch def /dx x0 x1 sub 3 div def /dy y0 y1 sub 3 div def x0 dx sub y0 dy add x1 y1 ArrowA x0 dx add y0 dy add x0 2 mul x1 sub y1 ArrowB curveto /Points [ x1 y1 x0 y0 x0 2 mul x1 sub y1 ] def } def /Grid { newpath /a 4 string def /b ED /c ED /n ED cvi dup 1 lt { pop 1 } if /s ED s div dup 0 eq { pop 1 } if /dy ED s div dup 0 eq { pop 1 } if /dx ED dy div round dy mul /y0 ED dx div round dx mul /x0 ED dy div round cvi /y2 ED dx div round cvi /x2 ED dy div round cvi /y1 ED dx div round cvi /x1 ED /h y2 y1 sub 0 gt { 1 } { -1 } ifelse def /w x2 x1 sub 0 gt { 1 } { -1 } ifelse def b 0 gt { /z1 b 4 div CLW 2 div add def /Helvetica findfont b scalefont setfont /b b .95 mul CLW 2 div add def } if systemdict /setstrokeadjust known { true setstrokeadjust /t { } def } { /t { transform 0.25 sub round 0.25 add exch 0.25 sub round 0.25 add exch itransform } bind def } ifelse gsave n 0 gt { 1 setlinecap [ 0 dy n div ] dy n div 2 div setdash } { 2 setlinecap } ifelse /i x1 def /f y1 dy mul n 0 gt { dy n div 2 div h mul sub } if def /g y2 dy mul n 0 gt { dy n div 2 div h mul add } if def x2 x1 sub w mul 1 add dup 1000 gt { pop 1000 } if { i dx mul dup y0 moveto b 0 gt { gsave c i a cvs dup stringwidth pop /z2 ED w 0 gt {z1} {z1 z2 add neg} ifelse h 0 gt {b neg} {z1} ifelse rmoveto show grestore } if dup t f moveto g t L stroke /i i w add def } repeat grestore gsave n 0 gt % DG/SR modification begin - Nov. 7, 1997 - Patch 1 %{ 1 setlinecap [ 0 dx n div ] dy n div 2 div setdash } { 1 setlinecap [ 0 dx n div ] dx n div 2 div setdash } % DG/SR modification end { 2 setlinecap } ifelse /i y1 def /f x1 dx mul n 0 gt { dx n div 2 div w mul sub } if def /g x2 dx mul n 0 gt { dx n div 2 div w mul add } if def y2 y1 sub h mul 1 add dup 1000 gt { pop 1000 } if { newpath i dy mul dup x0 exch moveto b 0 gt { gsave c i a cvs dup stringwidth pop /z2 ED w 0 gt {z1 z2 add neg} {z1} ifelse h 0 gt {z1} {b neg} ifelse rmoveto show grestore } if dup f exch t moveto g exch t L stroke /i i h add def } repeat grestore } def /ArcArrow { /d ED /b ED /a ED gsave newpath 0 -1000 moveto clip newpath 0 1 0 0 b grestore c mul /e ED pop pop pop r a e d PtoC y add exch x add exch r a PtoC y add exch x add exch b pop pop pop pop a e d CLW 8 div c mul neg d } def /Ellipse { /mtrx CM def T scale 0 0 1 5 3 roll arc mtrx setmatrix } def /Rot { CP CP translate 3 -1 roll neg rotate NET } def /RotBegin { tx@Dict /TMatrix known not { /TMatrix { } def /RAngle { 0 } def } if /TMatrix [ TMatrix CM ] cvx def /a ED a Rot /RAngle [ RAngle dup a add ] cvx def } def /RotEnd { /TMatrix [ TMatrix setmatrix ] cvx def /RAngle [ RAngle pop ] cvx def } def /PutCoor { gsave CP T CM STV exch exec moveto setmatrix CP grestore } def /PutBegin { /TMatrix [ TMatrix CM ] cvx def CP 4 2 roll T moveto } def /PutEnd { CP /TMatrix [ TMatrix setmatrix ] cvx def moveto } def /Uput { /a ED add 2 div /h ED 2 div /w ED /s a sin def /c a cos def /b s abs c abs 2 copy gt dup /q ED { pop } { exch pop } ifelse def /w1 c b div w mul def /h1 s b div h mul def q { w1 abs w sub dup c mul abs } { h1 abs h sub dup s mul abs } ifelse } def /UUput { /z ED abs /y ED /x ED q { x s div c mul abs y gt } { x c div s mul abs y gt } ifelse { x x mul y y mul sub z z mul add sqrt z add } { q { x s div } { x c div } ifelse abs } ifelse a PtoC h1 add exch w1 add exch } def /BeginOL { dup (all) eq exch TheOL eq or { IfVisible not { Visible /IfVisible true def } if } { IfVisible { Invisible /IfVisible false def } if } ifelse } def /InitOL { /OLUnit [ 3000 3000 matrix defaultmatrix dtransform ] cvx def /Visible { CP OLUnit idtransform T moveto } def /Invisible { CP OLUnit neg exch neg exch idtransform T moveto } def /BOL { BeginOL } def /IfVisible true def } def end % END pstricks.pro %%EndProcSet %%BeginProcSet: pst-dots.pro %!PS-Adobe-2.0 %%Title: Dot Font for PSTricks 97 - Version 97, 93/05/07. %%Creator: Timothy Van Zandt tvz@princeton.edu %%Creation Date: May 7, 1993 10 dict dup begin /FontType 3 def /FontMatrix [ .001 0 0 .001 0 0 ] def /FontBBox [ 0 0 0 0 ] def /Encoding 256 array def 0 1 255 { Encoding exch /.notdef put } for Encoding dup (b) 0 get /Bullet put dup (c) 0 get /Circle put dup (C) 0 get /BoldCircle put dup (u) 0 get /SolidTriangle put dup (t) 0 get /Triangle put dup (T) 0 get /BoldTriangle put dup (r) 0 get /SolidSquare put dup (s) 0 get /Square put dup (S) 0 get /BoldSquare put dup (q) 0 get /SolidPentagon put dup (p) 0 get /Pentagon put (P) 0 get /BoldPentagon put /Metrics 13 dict def Metrics begin /Bullet 1000 def /Circle 1000 def /BoldCircle 1000 def /SolidTriangle 1344 def /Triangle 1344 def /BoldTriangle 1344 def /SolidSquare 886 def /Square 886 def /BoldSquare 886 def /SolidPentagon 1093.2 def /Pentagon 1093.2 def /BoldPentagon 1093.2 def /.notdef 0 def end /BBoxes 13 dict def BBoxes begin /Circle { -550 -550 550 550 } def /BoldCircle /Circle load def /Bullet /Circle load def /Triangle { -571.5 -330 571.5 660 } def /BoldTriangle /Triangle load def /SolidTriangle /Triangle load def /Square { -450 -450 450 450 } def /BoldSquare /Square load def /SolidSquare /Square load def /Pentagon { -546.6 -465 546.6 574.7 } def /BoldPentagon /Pentagon load def /SolidPentagon /Pentagon load def /.notdef { 0 0 0 0 } def end /CharProcs 20 dict def CharProcs begin /Adjust { 2 copy dtransform floor .5 add exch floor .5 add exch idtransform 3 -1 roll div 3 1 roll exch div exch scale } def /CirclePath { 0 0 500 0 360 arc closepath } def /Bullet { 500 500 Adjust CirclePath fill } def /Circle { 500 500 Adjust CirclePath .9 .9 scale CirclePath eofill } def /BoldCircle { 500 500 Adjust CirclePath .8 .8 scale CirclePath eofill } def /BoldCircle { CirclePath .8 .8 scale CirclePath eofill } def /TrianglePath { 0 660 moveto -571.5 -330 lineto 571.5 -330 lineto closepath } def /SolidTriangle { TrianglePath fill } def /Triangle { TrianglePath .85 .85 scale TrianglePath eofill } def /BoldTriangle { TrianglePath .7 .7 scale TrianglePath eofill } def /SquarePath { -450 450 moveto 450 450 lineto 450 -450 lineto -450 -450 lineto closepath } def /SolidSquare { SquarePath fill } def /Square { SquarePath .89 .89 scale SquarePath eofill } def /BoldSquare { SquarePath .78 .78 scale SquarePath eofill } def /PentagonPath { -337.8 -465 moveto 337.8 -465 lineto 546.6 177.6 lineto 0 574.7 lineto -546.6 177.6 lineto closepath } def /SolidPentagon { PentagonPath fill } def /Pentagon { PentagonPath .89 .89 scale PentagonPath eofill } def /BoldPentagon { PentagonPath .78 .78 scale PentagonPath eofill } def /.notdef { } def end /BuildGlyph { exch begin Metrics 1 index get exec 0 BBoxes 3 index get exec setcachedevice CharProcs begin load exec end end } def /BuildChar { 1 index /Encoding get exch get 1 index /BuildGlyph get exec } bind def end /PSTricksDotFont exch definefont pop % END pst-dots.pro %%EndProcSet %%BeginProcSet: pst-node.pro %! % PostScript prologue for pst-node.tex. % Version 97 patch 1, 97/05/09. % For distribution, see pstricks.tex. % /tx@NodeDict 400 dict def tx@NodeDict begin tx@Dict begin /T /translate load def end /NewNode { gsave /next ED dict dup 3 1 roll def exch { dup 3 1 roll def } if begin tx@Dict begin STV CP T exec end /NodeMtrx CM def next end grestore } def /InitPnode { /Y ED /X ED /NodePos { NodeSep Cos mul NodeSep Sin mul } def } def /InitCnode { /r ED /Y ED /X ED /NodePos { NodeSep r add dup Cos mul exch Sin mul } def } def /GetRnodePos { Cos 0 gt { /dx r NodeSep add def } { /dx l NodeSep sub def } ifelse Sin 0 gt { /dy u NodeSep add def } { /dy d NodeSep sub def } ifelse dx Sin mul abs dy Cos mul abs gt { dy Cos mul Sin div dy } { dx dup Sin mul Cos Div } ifelse } def /InitRnode { /Y ED /X ED X sub /r ED /l X neg def Y add neg /d ED Y sub /u ED /NodePos { GetRnodePos } def } def /DiaNodePos { w h mul w Sin mul abs h Cos mul abs add Div NodeSep add dup Cos mul exch Sin mul } def /TriNodePos { Sin s lt { d NodeSep sub dup Cos mul Sin Div exch } { w h mul w Sin mul h Cos abs mul add Div NodeSep add dup Cos mul exch Sin mul } ifelse } def /InitTriNode { sub 2 div exch 2 div exch 2 copy T 2 copy 4 index index /d ED pop pop pop pop -90 mul rotate /NodeMtrx CM def /X 0 def /Y 0 def d sub abs neg /d ED d add /h ED 2 div h mul h d sub Div /w ED /s d w Atan sin def /NodePos { TriNodePos } def } def /OvalNodePos { /ww w NodeSep add def /hh h NodeSep add def Sin ww mul Cos hh mul Atan dup cos ww mul exch sin hh mul } def /GetCenter { begin X Y NodeMtrx transform CM itransform end } def /XYPos { dup sin exch cos Do /Cos ED /Sin ED /Dist ED Cos 0 gt { Dist Dist Sin mul Cos div } { Cos 0 lt { Dist neg Dist Sin mul Cos div neg } { 0 Dist Sin mul } ifelse } ifelse Do } def /GetEdge { dup 0 eq { pop begin 1 0 NodeMtrx dtransform CM idtransform exch atan sub dup sin /Sin ED cos /Cos ED /NodeSep ED NodePos NodeMtrx dtransform CM idtransform end } { 1 eq {{exch}} {{}} ifelse /Do ED pop XYPos } ifelse } def /AddOffset { 1 index 0 eq { pop pop } { 2 copy 5 2 roll cos mul add 4 1 roll sin mul sub exch } ifelse } def /GetEdgeA { NodeSepA AngleA NodeA NodeSepTypeA GetEdge OffsetA AngleA AddOffset yA add /yA1 ED xA add /xA1 ED } def /GetEdgeB { NodeSepB AngleB NodeB NodeSepTypeB GetEdge OffsetB AngleB AddOffset yB add /yB1 ED xB add /xB1 ED } def /GetArmA { ArmTypeA 0 eq { /xA2 ArmA AngleA cos mul xA1 add def /yA2 ArmA AngleA sin mul yA1 add def } { ArmTypeA 1 eq {{exch}} {{}} ifelse /Do ED ArmA AngleA XYPos OffsetA AngleA AddOffset yA add /yA2 ED xA add /xA2 ED } ifelse } def /GetArmB { ArmTypeB 0 eq { /xB2 ArmB AngleB cos mul xB1 add def /yB2 ArmB AngleB sin mul yB1 add def } { ArmTypeB 1 eq {{exch}} {{}} ifelse /Do ED ArmB AngleB XYPos OffsetB AngleB AddOffset yB add /yB2 ED xB add /xB2 ED } ifelse } def /InitNC { /b ED /a ED /NodeSepTypeB ED /NodeSepTypeA ED /NodeSepB ED /NodeSepA ED /OffsetB ED /OffsetA ED tx@NodeDict a known tx@NodeDict b known and dup { /NodeA a load def /NodeB b load def NodeA GetCenter /yA ED /xA ED NodeB GetCenter /yB ED /xB ED } if } def /LPutLine { 4 copy 3 -1 roll sub neg 3 1 roll sub Atan /NAngle ED 1 t sub mul 3 1 roll 1 t sub mul 4 1 roll t mul add /Y ED t mul add /X ED } def /LPutLines { mark LPutVar counttomark 2 div 1 sub /n ED t floor dup n gt { pop n 1 sub /t 1 def } { dup t sub neg /t ED } ifelse cvi 2 mul { pop } repeat LPutLine cleartomark } def /BezierMidpoint { /y3 ED /x3 ED /y2 ED /x2 ED /y1 ED /x1 ED /y0 ED /x0 ED /t ED /cx x1 x0 sub 3 mul def /cy y1 y0 sub 3 mul def /bx x2 x1 sub 3 mul cx sub def /by y2 y1 sub 3 mul cy sub def /ax x3 x0 sub cx sub bx sub def /ay y3 y0 sub cy sub by sub def ax t 3 exp mul bx t t mul mul add cx t mul add x0 add ay t 3 exp mul by t t mul mul add cy t mul add y0 add 3 ay t t mul mul mul 2 by t mul mul add cy add 3 ax t t mul mul mul 2 bx t mul mul add cx add atan /NAngle ED /Y ED /X ED } def /HPosBegin { yB yA ge { /t 1 t sub def } if /Y yB yA sub t mul yA add def } def /HPosEnd { /X Y yyA sub yyB yyA sub Div xxB xxA sub mul xxA add def /NAngle yyB yyA sub xxB xxA sub Atan def } def /HPutLine { HPosBegin /yyA ED /xxA ED /yyB ED /xxB ED HPosEnd } def /HPutLines { HPosBegin yB yA ge { /check { le } def } { /check { ge } def } ifelse /xxA xA def /yyA yA def mark xB yB LPutVar { dup Y check { exit } { /yyA ED /xxA ED } ifelse } loop /yyB ED /xxB ED cleartomark HPosEnd } def /VPosBegin { xB xA lt { /t 1 t sub def } if /X xB xA sub t mul xA add def } def /VPosEnd { /Y X xxA sub xxB xxA sub Div yyB yyA sub mul yyA add def /NAngle yyB yyA sub xxB xxA sub Atan def } def /VPutLine { VPosBegin /yyA ED /xxA ED /yyB ED /xxB ED VPosEnd } def /VPutLines { VPosBegin xB xA ge { /check { le } def } { /check { ge } def } ifelse /xxA xA def /yyA yA def mark xB yB LPutVar { 1 index X check { exit } { /yyA ED /xxA ED } ifelse } loop /yyB ED /xxB ED cleartomark VPosEnd } def /HPutCurve { gsave newpath /SaveLPutVar /LPutVar load def LPutVar 8 -2 roll moveto curveto flattenpath /LPutVar [ {} {} {} {} pathforall ] cvx def grestore exec /LPutVar /SaveLPutVar load def } def /NCCoor { /AngleA yB yA sub xB xA sub Atan def /AngleB AngleA 180 add def GetEdgeA GetEdgeB /LPutVar [ xB1 yB1 xA1 yA1 ] cvx def /LPutPos { LPutVar LPutLine } def /HPutPos { LPutVar HPutLine } def /VPutPos { LPutVar VPutLine } def LPutVar } def /NCLine { NCCoor tx@Dict begin ArrowA CP 4 2 roll ArrowB lineto pop pop end } def /NCLines { false NArray n 0 eq { NCLine } { 2 copy yA sub exch xA sub Atan /AngleA ED n 2 mul dup index exch index yB sub exch xB sub Atan /AngleB ED GetEdgeA GetEdgeB /LPutVar [ xB1 yB1 n 2 mul 4 add 4 roll xA1 yA1 ] cvx def mark LPutVar tx@Dict begin false Line end /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } ifelse } def /NCCurve { GetEdgeA GetEdgeB xA1 xB1 sub yA1 yB1 sub Pyth 2 div dup 3 -1 roll mul /ArmA ED mul /ArmB ED /ArmTypeA 0 def /ArmTypeB 0 def GetArmA GetArmB xA2 yA2 xA1 yA1 tx@Dict begin ArrowA end xB2 yB2 xB1 yB1 tx@Dict begin ArrowB end curveto /LPutVar [ xA1 yA1 xA2 yA2 xB2 yB2 xB1 yB1 ] cvx def /LPutPos { t LPutVar BezierMidpoint } def /HPutPos { { HPutLines } HPutCurve } def /VPutPos { { VPutLines } HPutCurve } def } def /NCAngles { GetEdgeA GetEdgeB GetArmA GetArmB /mtrx AngleA matrix rotate def xA2 yA2 mtrx transform pop xB2 yB2 mtrx transform exch pop mtrx itransform /y0 ED /x0 ED mark ArmB 0 ne { xB1 yB1 } if xB2 yB2 x0 y0 xA2 yA2 ArmA 0 ne { xA1 yA1 } if tx@Dict begin false Line end /LPutVar [ xB1 yB1 xB2 yB2 x0 y0 xA2 yA2 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def /NCAngle { GetEdgeA GetEdgeB GetArmB /mtrx AngleA matrix rotate def xB2 yB2 mtrx itransform pop xA1 yA1 mtrx itransform exch pop mtrx transform /y0 ED /x0 ED mark ArmB 0 ne { xB1 yB1 } if xB2 yB2 x0 y0 xA1 yA1 tx@Dict begin false Line end /LPutVar [ xB1 yB1 xB2 yB2 x0 y0 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def /NCBar { GetEdgeA GetEdgeB GetArmA GetArmB /mtrx AngleA matrix rotate def xA2 yA2 mtrx itransform pop xB2 yB2 mtrx itransform pop sub dup 0 mtrx transform 3 -1 roll 0 gt { /yB2 exch yB2 add def /xB2 exch xB2 add def } { /yA2 exch neg yA2 add def /xA2 exch neg xA2 add def } ifelse mark ArmB 0 ne { xB1 yB1 } if xB2 yB2 xA2 yA2 ArmA 0 ne { xA1 yA1 } if tx@Dict begin false Line end /LPutVar [ xB1 yB1 xB2 yB2 xA2 yA2 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def /NCDiag { GetEdgeA GetEdgeB GetArmA GetArmB mark ArmB 0 ne { xB1 yB1 } if xB2 yB2 xA2 yA2 ArmA 0 ne { xA1 yA1 } if tx@Dict begin false Line end /LPutVar [ xB1 yB1 xB2 yB2 xA2 yA2 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def /NCDiagg { GetEdgeA GetArmA yB yA2 sub xB xA2 sub Atan 180 add /AngleB ED GetEdgeB mark xB1 yB1 xA2 yA2 ArmA 0 ne { xA1 yA1 } if tx@Dict begin false Line end /LPutVar [ xB1 yB1 xA2 yA2 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def /NCLoop { GetEdgeA GetEdgeB GetArmA GetArmB /mtrx AngleA matrix rotate def xA2 yA2 mtrx transform loopsize add /yA3 ED /xA3 ED /xB3 xB2 yB2 mtrx transform pop def xB3 yA3 mtrx itransform /yB3 ED /xB3 ED xA3 yA3 mtrx itransform /yA3 ED /xA3 ED mark ArmB 0 ne { xB1 yB1 } if xB2 yB2 xB3 yB3 xA3 yA3 xA2 yA2 ArmA 0 ne { xA1 yA1 } if tx@Dict begin false Line end /LPutVar [ xB1 yB1 xB2 yB2 xB3 yB3 xA3 yA3 xA2 yA2 xA1 yA1 ] cvx def /LPutPos { LPutLines } def /HPutPos { HPutLines } def /VPutPos { VPutLines } def } def % DG/SR modification begin - May 9, 1997 - Patch 1 %/NCCircle { 0 0 NodesepA nodeA \tx@GetEdge pop xA sub 2 div dup 2 exp r %r mul sub abs sqrt atan 2 mul /a ED r AngleA 90 add PtoC yA add exch xA add %exch 2 copy /LPutVar [ 4 2 roll r AngleA ] cvx def /LPutPos { LPutVar t 360 %mul add dup 5 1 roll 90 sub \tx@PtoC 3 -1 roll add /Y ED add /X ED /NAngle ED /NCCircle { NodeSepA 0 NodeA 0 GetEdge pop 2 div dup 2 exp r r mul sub abs sqrt atan 2 mul /a ED r AngleA 90 add PtoC yA add exch xA add exch 2 copy /LPutVar [ 4 2 roll r AngleA ] cvx def /LPutPos { LPutVar t 360 mul add dup 5 1 roll 90 sub PtoC 3 -1 roll add /Y ED add /X ED /NAngle ED % DG/SR modification end } def /HPutPos { LPutPos } def /VPutPos { LPutPos } def r AngleA 90 sub a add AngleA 270 add a sub tx@Dict begin /angleB ED /angleA ED /r ED /c 57.2957 r Div def /y ED /x ED } def /NCBox { /d ED /h ED /AngleB yB yA sub xB xA sub Atan def /AngleA AngleB 180 add def GetEdgeA GetEdgeB /dx d AngleB sin mul def /dy d AngleB cos mul neg def /hx h AngleB sin mul neg def /hy h AngleB cos mul def /LPutVar [ xA1 hx add yA1 hy add xB1 hx add yB1 hy add xB1 dx add yB1 dy add xA1 dx add yA1 dy add ] cvx def /LPutPos { LPutLines } def /HPutPos { xB yB xA yA LPutLine } def /VPutPos { HPutPos } def mark LPutVar tx@Dict begin false Polygon end } def /NCArcBox { /l ED neg /d ED /h ED /a ED /AngleA yB yA sub xB xA sub Atan def /AngleB AngleA 180 add def /tA AngleA a sub 90 add def /tB tA a 2 mul add def /r xB xA sub tA cos tB cos sub Div dup 0 eq { pop 1 } if def /x0 xA r tA cos mul add def /y0 yA r tA sin mul add def /c 57.2958 r div def /AngleA AngleA a sub 180 add def /AngleB AngleB a add 180 add def GetEdgeA GetEdgeB /AngleA tA 180 add yA yA1 sub xA xA1 sub Pyth c mul sub def /AngleB tB 180 add yB yB1 sub xB xB1 sub Pyth c mul add def l 0 eq { x0 y0 r h add AngleA AngleB arc x0 y0 r d add AngleB AngleA arcn } { x0 y0 translate /tA AngleA l c mul add def /tB AngleB l c mul sub def 0 0 r h add tA tB arc r h add AngleB PtoC r d add AngleB PtoC 2 copy 6 2 roll l arcto 4 { pop } repeat r d add tB PtoC l arcto 4 { pop } repeat 0 0 r d add tB tA arcn r d add AngleA PtoC r h add AngleA PtoC 2 copy 6 2 roll l arcto 4 { pop } repeat r h add tA PtoC l arcto 4 { pop } repeat } ifelse closepath /LPutVar [ x0 y0 r AngleA AngleB h d ] cvx def /LPutPos { LPutVar /d ED /h ED /AngleB ED /AngleA ED /r ED /y0 ED /x0 ED t 1 le { r h add AngleA 1 t sub mul AngleB t mul add dup 90 add /NAngle ED PtoC } { t 2 lt { /NAngle AngleB 180 add def r 2 t sub h mul t 1 sub d mul add add AngleB PtoC } { t 3 lt { r d add AngleB 3 t sub mul AngleA 2 t sub mul add dup 90 sub /NAngle ED PtoC } { /NAngle AngleA 180 add def r 4 t sub d mul t 3 sub h mul add add AngleA PtoC } ifelse } ifelse } ifelse y0 add /Y ED x0 add /X ED } def /HPutPos { LPutPos } def /VPutPos { LPutPos } def } def /Tfan { /AngleA yB yA sub xB xA sub Atan def GetEdgeA w xA1 xB sub yA1 yB sub Pyth Pyth w Div CLW 2 div mul 2 div dup AngleA sin mul yA1 add /yA1 ED AngleA cos mul xA1 add /xA1 ED /LPutVar [ xA1 yA1 m { xB w add yB xB w sub yB } { xB yB w sub xB yB w add } ifelse xA1 yA1 ] cvx def /LPutPos { LPutLines } def /VPutPos@ { LPutVar flag { 8 4 roll pop pop pop pop } { pop pop pop pop 4 2 roll } ifelse } def /VPutPos { VPutPos@ VPutLine } def /HPutPos { VPutPos@ HPutLine } def mark LPutVar tx@Dict begin /ArrowA { moveto } def /ArrowB { } def false Line closepath end } def /LPutCoor { NAngle tx@Dict begin /NAngle ED end gsave CM STV CP Y sub neg exch X sub neg exch moveto setmatrix CP grestore } def /LPut { tx@NodeDict /LPutPos known { LPutPos } { CP /Y ED /X ED /NAngle 0 def } ifelse LPutCoor } def /HPutAdjust { Sin Cos mul 0 eq { 0 } { d Cos mul Sin div flag not { neg } if h Cos mul Sin div flag { neg } if 2 copy gt { pop } { exch pop } ifelse } ifelse s add flag { r add neg } { l add } ifelse X add /X ED } def /VPutAdjust { Sin Cos mul 0 eq { 0 } { l Sin mul Cos div flag { neg } if r Sin mul Cos div flag not { neg } if 2 copy gt { pop } { exch pop } ifelse } ifelse s add flag { d add } { h add neg } ifelse Y add /Y ED } def end % END pst-node.pro %%EndProcSet %%BeginProcSet: special.pro %! TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N /vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N /rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N /@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{ /hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B /@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{ /urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known {userdict/md get type/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{ itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack} if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{ noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{ Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale }if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState save N userdict maxlength dict begin/magscale true def normalscale currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts /psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict begin/SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{ CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end} repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N /@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X /yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (quicksort.dvi) @start %DVIPSBitmapFont: Fa lasy10 10.95 1 /Fa 1 51 df<007FB812E0B912F0A300F0CAFCB3B3A8B9FCA36C17E0343478B844> 50 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmtt10 10.95 6 /Fb 6 115 df<120FEA3FC0EA7FE0A2EAFFF0A4EA7FE0A2EA3FC0EA0F000C0C6E8B30> 46 D<007FB5FCB61280A4150048C8FCB3B3B3A5B6FC1580A46C140019476DBE30> 91 D<007FB5FCB61280A47EC7123FB3B3B3A5007FB5FCB6FCA46C140019477DBE30> 93 D 97 D<387FFFF8B57EA47EEA0001B3B3A8007FB612F0B712F8 A46C15F025387BB730> 108 D 114 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmsl10 10.95 33 /Fc 33 122 df 39 D<121EEA3F80EA7FC012FFA413 80EA7F00123C0A0A788919> 46 D<13F0EA01FC1203EA07FEA313FCA2EA03F8EA01E0C7 FCB3121EEA3F80EA7FC012FFA41380EA7F00123C0F2778A619> 58 D<013FB7FC18E018FC903B007FE00007FE6E48903801FF809438007FC05DF03FE0F01FF0 A3027F16F892C8FCA54A16F04A153F19E0187F19C0F0FF8001014B13004A4A5A4D5AEF1F F04D5ADC03FFC7FC49B612F8EFFF8002F8C7EA3FE0EF0FF0EF07FC717E010715014A8171 1380A319C0130F5CA5011F4B13805C19005F601707013F4B5A4A4A5A4D5A4D5A017F9138 01FF8001FF020F90C7FCB812FC17F094C8FC3D3E7DBD40> 66 D I<013FB812E0A3903A007FF000016E48EB003F180F4B1407 1803A31801147F4B15C0A514FF92C71270A395C7FC17F0495D5C160116031607161F49B6 5AA39138FC003F160F160701075D4A1303A5010F4AC8FC5C93C9FCA4131F5CA5133F5CA3 137FEBFFF0B612F8A33B3E7DBD3B> 70 D<011FB512FC5BA29039003FF8006E5AA25DA5 143F5DA5147F5DA514FF92C7FCA55B5CA513035CA513075CA5130F5CA5131F5CA3133F49 7E007FB512F0A2B6FC263E7EBD21> 73 D<013FB512FEA25E9026007FF8C8FCEC3FE0A2 5DA5147F5DA514FF92C9FCA55B5CA513035CA513075CA21838A21870130F5CA218E0A301 1F15014A15C01703A21707EF0F80013F151F4A143F177FEFFF00017F140301FF143FB9FC 5FA2353E7DBD39> 76 D<90263FFFF093381FFFF85013F0629026007FF8EFF000023F4D 5AA2023B933801DFC0A2DA39FCED039FA2F1073F14790271040E5BEC70FE191C19381A7F 02F01670DAE07F94C7FC19E0A2F001C06201016D6C495A02C05FF00700A2180E6F6C1401 0103161C028003385BA218706F7EF0E00313070200DA01C05BA2923907F00380A2943807 00075B010E902603F80E5C5FA25F190F011E6D6C5A011C605FA2EEFDC0DB00FF141F013C 5D013860013C92C7FC017C5C01FE027E143F2607FF80017C4A7EB500FC037FB512E00478 5E4A1338553E7CBD53> I<013FB612FEEFFFE018F8903B007FF0000FFC6E48EB01FF7113 804BEC7FC0183F19E0F01FF0A2147F5D19F8A402FFED3FF092C8FCA219E0A2F07FC05B4A EDFF8019004D5A4D5AEF0FF80103ED3FE04A903801FF8091B648C7FC17F002FCCAFCA213 075CA5130F5CA5131F5CA5133F5CA3137F497EB612E0A25D3D3E7DBD3E> 80 D<0007B912F0A33C0FFE000FF8003F01F0160F01C04A13034848160190C7FC121EF000E0 48141F5E1238A212781270153F5E5AA3C81600157F5EA515FF93C9FCA55C5DA514035DA5 14075DA5140F5DA3141FEC7FFC0003B7FCA33C3D76BC42> 84 D 97 D I 100 D I< ED07F0ED3FFCEDFC1E913803F03F4A48B4FC4A481380141FEC3F81DA7F0113008102FE13 7C93C7FCA213015CA513035CA50007B512F8A3260007F0C8FCA3130F5CA5131F5CA5133F 5CA5137F91C9FCA55B5BA4EA03FF007F13FEB5FCA229407DBF1C> I<177C913907F803FE 91393FFE0F8F9139FC0F9C3F903901F007F8903907E003E0D90FC013F0011F903801F80C 02801400133FD97F007FA315035B495CA3017E495A5E150F6D5C6D495A90263F803EC7FC ECC0FC903871FFF09038E07F8091C9FC485AA47FA27F90B512F8EDFF806C15E016F86D80 48B6FC3A07E0000FFED80F801300003FC8127F003E815A00FC815AA25E163EA25E6C15FC 007C4A5A6C4A5A6CEC0FC0D80FC0013FC7FC3903F801FCC6B512F0010F90C8FC303D7FA8 2D> I<147FEB3FFFA313017FA25CA513015CA513035CA4ED07F80107EB1FFF9139F0781F C09138F1E00F9139F38007E0ECF70002FE14F0495A5CA25CA24A130F131F4A14E0A4161F 133F4A14C0A4163F137F91C71380A4167F5B491500A300015D486C491380B5D8F87F13FC A32E3F7DBE33> I<1478EB01FE130314FFA25B14FE130314FCEB00F01400ACEB03F8EA01 FF14F0A2EA001F130FA314E0A5131F14C0A5133F1480A5137F1400A55B5BA4EA03FF007F 13F0A2B5FC183E7DBD1A> I<147FEB3FFFA313017FA25CA513015CA513035CA501070103 B5FC02F014FEA26F13F06F1380EEFE00010F14F84A485AED03C04B5A031FC7FC153E011F 13784A5AECC3E0ECC7F0ECCFF814FF497F14F9ECE1FE14C04A7E4A7E4980017E133F8215 1F82150F01FE8049130782A2000181486C49B4FCB5D8F03F13F04B13E0A2303F7EBE30> 107 D<143FEB1FFF5BA213017FA214FEA5130114FCA5130314F8A5130714F0A5130F14E0 A5131F14C0A5133F1480A5137F1400A55B5BA4EA03FF007F13F8A2B5FC183F7DBE1A> I< 902707F007F8EB03FCD803FFD91FFF90380FFF80913CE0781FC03C0FE09126E1E00FEBF0 073E001FE38007E1C003F090260FE700EBE38002EEDAF70013F802FC14FE02D85C14F84A 5CA24A5C011F020F14074A4A14F0A5013F021F140F4A4A14E0A5017F023F141F91C74914 C0A549027F143F4992C71380A300014B147F486C496DEBFFC0B5D8F87FD9FC3F13FEA347 287DA74C> I<903907F007F8D803FFEB1FFF9139E0781FC09138E1E00F3B001FE38007E0 90380FE70002EE14F014FC14D814F85CA24A130F131F4A14E0A4161F133F4A14C0A4163F 137F91C71380A4167F5B491500A300015D486C491380B5D8F87F13FCA32E287DA733> I< EC0FF0ECFFFE903903F01F8090390FC007C049C66C7E013E6D7E01FC6D7E48488049147C 0003157E485A000F157F5B121FA2485AA2007F1680A2170048C85AA54B5AA25E5A6C4A5A 7E4B5A5E6C140F6C6C5C4B5A6C6C013EC7FC6C6C5B6C6C485A3900FC0FE090383FFF80D9 0FF8C8FC292A7BA82D> I<91387F01FE903A7FFF0FFFC09139FE3E03F09238F801F8903A 03FFE000FE6D49137F4B7F92C713804A15C04A141FA218E0A20103150F5C18F0A3171F01 0716E05CA3173F18C0130F4A147F1880A2EFFF004C5A011F5D16034C5A6E495AEE1FC06E 495AD93FDC017EC7FC91388F01F8913883FFE0028090C8FC92C9FC137FA291CAFCA45BA2 5BA31201487EB512F8A3343A81A733> I<91390FE003C0DAFFFC1380903903F81E079039 0FE0070F90391F80038FD97F0013DF01FE13014848903800FF00485A1207485A8248485C 123F495CA2485AA2150112FF90C75BA41503A25EA37E15077F003F4A5A151F6C6C133F6C 6C137F000714FF3903F003CF3A00FC0F8FE090383FFE0FEB0FF090C7FC151F5EA5153F5E A4157F4B7E023F13FEA32A3A7AA730> I<903907F01F80D803FFEB7FE09138E1E1F09138 E387F839001FE707EB0FE614EE02FC13F002D813E09138F801804AC7FCA25C131FA25CA4 133F5CA5137F91C8FCA55B5BA31201487EB512FEA325287EA724> I<9138FF81C0010713 E390381F807F90397C003F8049131F4848130F5B00031407A248481400A27FA27F6D90C7 FCEBFF8014FC6C13FF6C14C015F06C6C7F011F7F13079038007FFE140314010038130015 7EA2123C153E157E007C147CA2007E147815F8007F495A4A5A486C485A26F9E01FC7FC38 E0FFFC38C01FE0222A7DA824> II<01FE147F00FFEC7FFF4914FEA20007140300031401A34914FCA4150312074914F8A415 07120F4914F0A4150F121F4914E0A2151FA3153F4914C0157F15FFEC01DF3A0FC003BFE0 9138073FFF3803F01E3801FFF826003FE01380282977A733> I I I<90B539E007FFF05E18E0902707FE000313006D48EB01FC705A5F01014A5A5F16 036E5C0100140794C7FC160E805E805E1678ED8070023F13F05EED81C015C191381FC380 15C793C8FC15EF15EEEC0FFCA25DA26E5AA25DA26E5A5DA24AC9FC5C140E141E141C5C12 1C003F5B5A485B495A130300FE5B4848CAFCEA701EEA783CEA3FF0EA0FC0343A80A630> 121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd msbm10 10.95 1 /Fd 1 83 df<007FB612FCB812C06C16F83B03E007C07FFE0000903A0F001F7F80020E90 38078FC093380383E0EFC0F0040113788484EFE00E1600180F84A760180E0401131EEFC0 1C183C04035BEF81F093380787E093381F7FC04BB5C7FC020FB512FC17C004F7C8FC9139 0E1C078092381E03C0ED0E01030F7FED078003037FEEC078923801E0380300133C707EEE 780EEE380F93383C0780EE1E03040E7F93380F01E093380780F004031370EFC078706C7E 04007F717E943878078094383803C00003D90F8090383C01E0007FB500FE90381FFFFCB6 806C823E3E7EBD39> 82 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe eufm10 10.95 1 /Fe 1 81 df<02FFED0FC0010701E0EC7FF0011F01F849487E017F6D01077F90B56C131F 2601E03FEC3E0F2703C00FFFEB780326070003D980F07F486D903883C001001E6DEBC780 481600ED7FCF007CEC3FDE04FC804C15CC00FE021F16FE6C4B15F87213E06D4A15C06D01 0FED7F006C6C171E191C6C6C5F6D5F6C6C17F0000F4D5A6C6C16031807120300014D7E6C 5A855B854848707E485A49707ED80F8082001EC71780003883C8EE7FC0A2193F191FA219 0FA219071A80EC0FEFEC3FFF91B516004902F85C4902FF140E4903E0131E4903FC5B02C0 9138FFC0F890261F000FECFFF0133C013817C04902E35C04E091C7FC49ED1FFC0140ED03 F090C791C9FCA6151FA282A55EED3F8093CAFC153E1538151047537EBE4B> 80 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmss10 10.95 10 /Ff 10 115 df69 D 80 D 86 D 91 D 93 D 97 D<12FFA81200AF127FB3B3A4083F7ABE16> 105 D I<14FFD8FE0713E0011F7F017F7FB67E819038F80FFFEBE0 03D98000138090C7EA7FC0153F5AED1FE0A2150FA216F01507A8150F16E0A2151FA2ED3F C06C147F6DEBFF805CD9E00313009038F81FFE90B55A485C6D5B6D5B010F1380D901FEC7 FC90C9FCB1243B79A82F> 112 D<00FC137CEB03FC130F131F133F137FEBFFC038FDFE00 EAFFF85B5B5BA25BA290C7FCA25AB3A6162979A81F> 114 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmsy8 8 6 /Fg 6 107 df 0 D 20 D<12E012F812FEEA3F80EA0FE0EA03 F8EA00FEEB3F80EB0FE0EB03F8EB00FC143FEC0FC0EC07F0EC01FCEC007FED1FC0ED07F0 ED01FCED007FEE1FC01607161FEE7F00ED01FCED07F0ED1FC0037FC7FCEC01FCEC07F0EC 0FC0023FC8FC14FCEB03F8EB0FE0EB3F8001FEC9FCEA03F8EA0FE0EA3F80007ECAFC12F8 12E0CBFCAD007FB71280B812C0A22A3B7AAB37> I<137813FE1201A3120313FCA3EA07F8 A313F0A2EA0FE0A313C0121F1380A3EA3F00A3123E127E127CA35AA35A0F227EA413> 48 D<91B512C01307131FD97F80C7FC01FCC8FCEA01F0EA03C0485A48C9FC120E121E5A1238 12781270A212F05AA3B712C0A300E0C9FCA37E1270A212781238123C7E120E120F6C7E6C 7EEA01F0EA00FCEB7F80011FB512C013071300222B7AA52F> 50 D<12E0B3B3B3AD034378B114> 106 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmr8 8 15 /Fh 15 119 df<13031307130E131C1338137013F0EA01E013C01203EA0780A2EA0F00A2 121EA35AA45AA512F8A25AAB7EA21278A57EA47EA37EA2EA0780A2EA03C0120113E0EA00 F013701338131C130E1307130310437AB11B> 40 D<12C07E12707E7E7E120FEA078012 0313C0EA01E0A2EA00F0A21378A3133CA4131EA5131FA2130FAB131FA2131EA5133CA413 78A313F0A2EA01E0A2EA03C013801207EA0F00120E5A5A5A5A5A10437CB11B> I 43 D 48 D<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2172C7AAB23> I I 54 D 61 D 77 D<90383F80303901FFF0 703807C07C390F000EF0001E13074813034813011400127000F01470A315307EA26C1400 127E127FEA3FE013FE381FFFE06C13FC6C13FF00011480D8003F13E013039038003FF0EC 07F81401140015FC157C12C0153CA37EA215787E6C14706C14F06CEB01E039F78003C039 E3F00F0038E07FFE38C00FF01E2F7CAD27> 83 D 91 D 93 D<13FF000713C0380F01F0381C00F8003F137C80A2143F001E7FC7FCA4EB07FF137F3801 FE1FEA07F0EA1FC0EA3F80EA7F00127E00FE14065AA3143F7E007E137F007FEBEF8C391F 83C7FC390FFF03F83901FC01E01F207D9E23> 97 D<013F13F89038FFC3FE3903E1FF1E 3807807C000F140C391F003E00A2003E7FA76C133EA26C6C5A00071378380FE1F0380CFF C0D81C3FC7FC90C8FCA3121E121F380FFFF814FF6C14C04814F0391E0007F84813004814 7C12F848143CA46C147C007C14F86CEB01F06CEB03E03907E01F803901FFFE0038003FF0 1F2D7E9D23> 103 D<3AFFFC01FFC0A23A0FE0007E000007147C15380003143015706C6C 1360A26C6C5BA390387C0180A26D48C7FCA2EB3F07EB1F06A2EB0F8CA214DCEB07D8A2EB 03F0A36D5AA26D5A221E7F9C25> 118 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmti10 10.95 25 /Fi 25 122 df 40 D<14031580A2EC01C0EC00E0A21570A2157815 38153CA3151EA4151FA2150FA7151FA9153FA2153EA3157EA2157CA215FCA215F8A21401 A215F0A2140315E0A2140715C0A2EC0F80A2141F15005C143EA25CA25CA2495A5C130349 5A5C130F49C7FC131E5B137C5B5B485A485A485A48C8FC121E5A12705A5A205A7FC325> I<387FFFFCA3B5FCA21605799521> 45 D 79 D<147E49B47E903907C1C3809039 1F80EFC090383F00FF017E137F4914804848133F485AA248481400120F5B001F5C157E48 5AA215FE007F5C90C7FCA21401485C5AA21403EDF0385AA21407EDE078020F1370127C02 1F13F0007E013F13E0003E137FECF3E1261F01E313C03A0F8781E3803A03FF00FF00D800 FC133E252977A72E> 97 D I I I I<167C4BB4FC923807C78092380F83C0ED1F87161FED3F 3FA2157EA21780EE0E004BC7FCA414015DA414035DA30103B512F8A390260007E0C7FCA3 140F5DA5141F5DA4143F92C8FCA45C147EA414FE5CA413015CA4495AA4495AA4495A121E 127F5C12FF49C9FCA2EAFE1EEAF83C1270EA7878EA3FE0EA0F802A5383BF1C> I I<1478EB01FCA21303A314F8EB00E01400 AD137C48B4FC38038F80EA0707000E13C0121E121CEA3C0F1238A2EA781F00701380A2EA F03F140012005B137E13FE5BA212015BA212035B1438120713E0000F1378EBC070A214F0 EB80E0A2EB81C01383148038078700EA03FEEA00F8163E79BC1C> 105 D 108 D I I I<903903E001F890390FF807FE903A1E7C1E0F80903A1C3E 3C07C0013C137801389038E003E0EB783F017001C013F0ED80019038F07F0001E015F814 7E1603000113FEA2C75AA20101140717F05CA20103140F17E05CA20107EC1FC0A24A1480 163F010F15005E167E5E131F4B5A6E485A4B5A90393FB80F80DA9C1FC7FCEC0FFCEC03E0 49C9FCA2137EA213FEA25BA21201A25BA21203A2387FFFE0B5FCA22D3A80A72E> I 114 D I I<137C48B4141C26038F 80137EEA0707000E7F001E15FE121CD83C0F5C12381501EA781F007001805BA2D8F03F13 03140000005D5B017E1307A201FE5C5B150F1201495CA2151F0003EDC1C0491481A2153F 1683EE0380A2ED7F07000102FF13005C01F8EBDF0F00009038079F0E90397C0F0F1C9039 1FFC07F8903907F001F02A2979A731> I<017CEB01C048B4EB07F038038F80EA0707000E 01C013F8121E001C1403EA3C0F0038EC01F0A2D8781F130000705BA2EAF03F91C712E012 005B017E130116C013FE5B1503000115805BA2ED07001203495B150EA25DA25D15780001 14706D5B0000495A6D485AD97E0FC7FCEB1FFEEB03F0252979A72A> I<017C167048B491 387001FC3A038F8001F8EA0707000E01C015FE001E1403001CEDF000EA3C0F0038177C15 07D8781F4A133C00701380A2D8F03F130F020049133812005B017E011F14784C137013FE 5B033F14F0000192C712E05BA2170100034A14C049137E17031880A2EF070015FE170E00 010101141E01F86D131C0000D9039F5BD9FC076D5A903A3E0F07C1E0903A1FFC03FFC090 2703F0007FC7FC372979A73C> I<903903F001F890390FFC07FE90393C1E0E0F9026780F 1C138001F0EBB83FD801E013F89039C007F07FEA0380000714E0D9000F140048151C000E 4AC7FCA2001E131FA2C75BA2143F92C8FCA35C147EA314FE4A131CA30101143C001E1538 003F491378D87F811470018314F000FF5D9039077801C039FE0F7C033A7C0E3C07802778 3C1E1EC7FC391FF80FFC3907E003F029297CA72A> I<137C48B4143826038F8013FCEA07 07000E7F001E1401001C15F8EA3C0F12381503D8781F14F000701380A2D8F03F13070200 13E012005B017E130F16C013FE5B151F1201491480A2153F000315005BA25D157EA315FE 5D00011301EBF8030000130790387C1FF8EB3FF9EB07E1EB00035DA21407000E5CEA3F80 007F495AA24A5AD8FF0090C7FC143E007C137E00705B387801F0383803E0381E0FC06CB4 C8FCEA03F8263B79A72C> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmex10 10.95 11 /Fj 11 113 df<140E141E143C147814F01301EB03E0EB07C0A2EB0F80EB1F00A2133E13 7E137C13FC5B1201A2485AA3485AA2120F5BA2121FA25BA2123FA390C7FCA25AA6127E12 FEB3A4127E127FA67EA27FA3121FA27FA2120FA27F1207A26C7EA36C7EA212007F137C13 7E133E7FA2EB0F80EB07C0A2EB03E0EB01F013001478143C141E140E176C72832A> 0 D<12E07E12787E7E121F6C7E6C7EA26C7E6C7EA26C7E7F137C137E133E133FA2EB1F80A3 EB0FC0A214E01307A214F0A21303A214F8A31301A214FCA6130014FEB3A414FC1301A614 F8A21303A314F0A21307A214E0A2130F14C0A2EB1F80A3EB3F00A2133E137E137C13FC5B 485AA2485A485AA2485A48C7FC121E5A5A5A5A176C7C832A> I<12F0B3B3B3A5043B7381 1E> 12 D<17F01601EE03E0EE07C0EE0F80EE1F00163E5E16FC4B5A4B5A4B5A5E150F4B 5A4BC7FCA2157E5D14015D4A5AA24A5A140F5D141F5D143F4AC8FCA214FEA2495AA2495A A2495AA3495AA2495AA3495AA349C9FCA25B5BA312015BA21203A25BA21207A25BA2120F A35BA2121FA45BA2123FA65B127FAA48CAFCB3AE6C7EAA123F7FA6121FA27FA4120FA27F A31207A27FA21203A27FA21201A27F1200A37F7FA26D7EA36D7EA36D7EA26D7EA36D7EA2 6D7EA26D7EA2147FA26E7E141F81140F8114076E7EA26E7E811400157E81A26F7E6F7E15 07826F7E6F7E6F7E167C8282EE0F80EE07C0EE03E0EE01F016002CDA6D8343> 18 D<12F07E127C7E7E6C7E6C7E6C7E7F6C7E6C7E137E133E133F6D7E6D7EA26D7E6D7E8013 016D7EA2147E147F8081141F816E7EA26E7EA26E7EA26E7EA26E7EA3157FA26F7EA36F7E A36F7EA2821507A3821503A282A21501A282A21500A282A382A21780A4163FA217C0A616 1F17E0AAEE0FF0B3AEEE1FE0AA17C0163FA61780A2167FA41700A25EA35EA21501A25EA2 1503A25EA215075EA3150F5EA24B5AA34B5AA34BC7FCA215FEA34A5AA24A5AA24A5AA24A 5AA24A5A5D143F92C8FC5C147E5CA2495A13035C495A495AA2495A49C9FC133E137E5B48 5A485A5B485A485A48CAFC123E5A5A5A2CDA7D8343> I<1778EE01F81607161FEE7FE0EE FF8003031300ED07FC4B5A4B5A4B5A4B5A4B5A93C7FC4A5A14035D14075D140F5DA34A5A B3B3B3A9143F5DA2147F5DA24AC8FCA2495A13035C495A495A495A495A495A49C9FC485A EA07F8485AEA3FC0B4CAFC12FCA2B4FCEA3FC0EA0FF06C7EEA01FE6C7E6D7E6D7E6D7E6D 7E6D7E6D7E8013016D7EA26E7EA281143FA281141FB3B3B3A96E7EA38114078114038114 016E7E826F7E6F7E6F7E6F7E6F7E6FB4FC03001380EE7FE0EE1FF816071601EE00782DDA 758344> 26 D[<177CEE01FC1607160F163FEE7FF0EEFFE04B1380030713004B5A4B5A5E 4B5A4B5A4B5A5E5C4A90C7FC5D14075D140F5DA2141F5DA3143F5DB3B3B3B3A6147F5DA4 4A5AA34990C8FCA2495AA2495AA2495AA2495A495A5C137F495A4890C9FC485A485AEA0F F0EA3FE0485A48CAFC5AA27EEA7FC06C7EEA0FF0EA07FC6C7E6C7E6C7F6D7E133F806D7E 6D7EA26D7EA26D7EA26D7EA26D7FA36E7EA481143FB3B3B3B3A681141FA381140FA28114 07811403816E7F80826F7E6F7E6F7E826F7E6F7E030113806F13E0EE7FF0EE3FFC160F16 071601EE007C> 46 272 115 131 73 40 D 80 D<007C181FA200FEF03F80B3B3B3A86C187FA26C19 006D5FA2003F606D1601A26C6C4C5A6D1607000F606D160F6C6C4C5A6C6C4C5A6C6C6CED FFC06E5C6C01F002075B6D6C4A90C7FC6DB4EC7FFE6D9039F007FFFC010790B612F06D5E 010016806E92C8FC020F14F8020114C09126001FFCC9FC415B7B7F4C> 83 D 88 D<1C601CF01B01A2F303E0A2F307C0A2F30F80A2F31F00A21B3EA263A263A2631A01A250 5AA2505AA2505AA250C7FCA21A3EA262A262A24F5AA24F5AA24F5AA24F5AA24FC8FCA219 3EA261A261A24E5AA2611803130C011C4C5A133E01FE4C5A487E484DC9FC380F7F80001C 173E123826F03FC05D1240C66C6C5DA26D6C4A5AA24D5A6D7E4D5A6D7E4D5A6D7E4DCAFC A26D6C143EA26E6C5BA26E6C5BA24C5AEC1FE04C5AEC0FF05F913807F807A24C5AEC03FC 4CCBFCEC01FE163EEC00FF5EA26F5AA26F5AA26F5AA25E150F5E6FCCFC546D77835B> 112 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmmi8 8 14 /Fk 14 121 df<123C127EB4FCA21380A2127F123D1201A312031300A25A1206120E5A5A 5A126009157A8714> 59 D I< 15C0140114031580A214071500A25C140EA2141E141CA2143C143814781470A214F05CA2 13015CA213035C130791C7FCA25B130EA2131E131CA2133C1338A21378137013F05BA212 015BA212035BA2120790C8FC5A120EA2121E121CA2123C1238A212781270A212F05AA21A 437CB123> I<1670A216F01501A24B7EA21507150DA2151915391531ED61FC156015C0EC 0180A2EC03005C14064A7F167E5C5CA25C14E05C4948137F91B6FC5B0106C7123FA25B13 1C1318491580161F5B5B120112031207000FED3FC0D8FFF8903807FFFEA22F2F7DAE35> 65 D<913807F00691383FFE0E9138F80F9E903903E001FE903807800049C7127C131E49 143CA2491438A313F81630A26D1400A27FEB7F8014F86DB47E15F06D13FC01077F01007F 141F02011380EC003F151F150FA215071218A3150F00381500A2151EA2007C5C007E5C00 7F5C397B8003E039F1F00F8026E07FFEC7FC38C00FF0272F7CAD2B> 83 D<90260FFFFCEB7FFFA29026007FC0EB0FF06E48148018006E6C131E1718020F5C6F5B02 075C6F485A020349C7FCEDF8065E6E6C5A5E6E6C5A5EED7F8093C8FC6F7EA26F7E153F15 6FEDCFE0EC018791380307F0EC0703020E7F141C4A6C7E14704A6C7E495A4948137F49C7 FC010E6E7E5B496E7E5BD801F081D807F8143FD8FFFE0103B5FCA2382D7EAC3A> 88 D 101 D<1307EB0F80EB1FC0A2EB0F80EB070090C7FCA9EA01E0EA07F8EA0E3CEA1C3E12381230 1270EA607EEAE07C12C013FC485A120012015B12035BA21207EBC04014C0120F13801381 381F01801303EB0700EA0F06131EEA07F8EA01F0122E7EAC18> 105 D<15E0EC01F01403A3EC01C091C7FCA9147CEB03FE9038078F80EB0E07131C013813C013 30EB700F0160138013E013C0EB801F13001500A25CA2143EA2147EA2147CA214FCA25CA2 1301A25CA21303A25CA2130700385BEAFC0F5C49C7FCEAF83EEAF0F8EA7FF0EA1F801C3B 81AC1D> I<131FEA03FFA2EA003FA2133EA2137EA2137CA213FCA25BA2120115F89038F0 03FCEC0F0E0003EB1C1EEC387EEBE07014E03807E1C09038E3803849C7FC13CEEA0FDC13 F8A2EBFF80381F9FE0EB83F0EB01F81300481404150C123EA2007E141C1518007CEBF038 ECF83000FC1470EC78E048EB3FC00070EB0F801F2F7DAD25> I<137CEA0FFCA21200A213 F8A21201A213F0A21203A213E0A21207A213C0A2120FA21380A2121FA21300A25AA2123E A2127EA2127CA2EAFC08131812F8A21338133012F01370EAF860EA78E0EA3FC0EA0F000E 2F7DAD15> I<3907C007E0391FE03FF83918F8783E393879E01E39307B801F38707F0012 6013FEEAE0FC12C05B00815C0001143E5BA20003147E157C5B15FC0007ECF8081618EBC0 0115F0000F1538913803E0300180147016E0001F010113C015E390C7EAFF00000E143E25 1F7E9D2B> 110 D<3807C01F390FF07FC0391CF8E0E0383879C138307B8738707F07EA60 7E13FC00E0EB03804848C7FCA2128112015BA21203A25BA21207A25BA2120FA25BA2121F A290C8FC120E1B1F7E9D20> 114 D<013F137C9038FFC1FF3A01C1E383803A0380F703C0 390700F60F000E13FE4813FC12180038EC0700003049C7FCA2EA200100005BA313035CA3 01075B5D14C000385CD87C0F130600FC140E011F130C011B131C39F03BE038D8707113F0 393FE0FFC0260F803FC7FC221F7E9D28> 120 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmsy10 10.95 15 /Fl 15 107 df<007FB812F8B912FCA26C17F83604789847> 0 D<121EEA7F80A2EAFFC0 A4EA7F80A2EA1E000A0A799B19> I 15 D<0207B612F8023F15FC49B7FC4916F8D90FFCC9FCEB1FE0017FCA FC13FEEA01F8485A485A5B485A121F90CBFC123EA25AA21278A212F8A25AA87EA21278A2 127CA27EA27E7F120F6C7E7F6C7E6C7EEA00FE137FEB1FE0EB0FFC0103B712F86D16FCEB 003F020715F891CAFCAE001FB812F84817FCA26C17F8364878B947> 18 D<1818187CEF01FCEF07F8EF1FF0EF7FC0933801FF00EE07FCEE1FF0EE7FC04B48C7FCED 07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848 CAFCEA07FCEA1FF0EA7FC048CBFC5AEA7F80EA3FE0EA0FF8EA03FEC66C7EEB3FE0EB0FF8 EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8ED03FE923800FF80 EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FC170018381800AE007FB812F8B9 12FCA26C17F8364878B947> 20 D<126012F812FEEA7F80EA3FE0EA0FF8EA03FEC66C7E EB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8ED03 FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FC1701EF07F8EF1F F0EF7FC0933801FF00EE07FCEE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC 07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CB FC12FC1270CCFCAE007FB812F8B912FCA26C17F8364878B947> I25 D<19301978A2197C193CA2193E191EA2191F737EA2737E737EA2737E737E1A7C1A7E F21F80F20FC0F207F0007FBB12FCBDFCA26C1AFCCDEA07F0F20FC0F21F80F27E001A7C62 4F5A4F5AA24F5A4F5AA24FC7FC191EA2193E193CA2197C1978A2193050307BAE5B> 33 D<0207B512E0023F14F049B6FC4915E0D90FFCC8FCEB1FE0017FC9FC13FEEA01F8485A48 5A5B485A121F90CAFC123EA25AA21278A212F8A25AA2B812E017F0A217E000F0CAFCA27E A21278A2127CA27EA27E7F120F6C7E7F6C7E6C7EEA00FE137FEB1FE0EB0FFC0103B612E0 6D15F0EB003F020714E02C3678B13D> 50 D<1518153CA2157CA2903803FC7890380FFF F8EB3E0790387801F0EBF0004848487ED803C07FD807807FA2390F0003EFA248ECCF8000 1EEB07C7003E15C01587A2140F007E15E0007C1403A2141FA2141E00FC013E13F0A2143C A2147CA21478A214F8A214F01301A214E0A21303A214C0A21307A21480D87C0F14E0A214 00007E14075BA2D83E1E14C0A2133E001FEC0F80133CD80F7C1400A2495B0007141E0003 5C00015C4913F83900F801E03901FE07C090B5C7FCEBE3FCD803E0C8FCA25BA26C5A244D 7CC52D> 59 D<0060EE018000F0EE03C0B3B3A36C1607A200781780007C160FA26CEE1F 00003F5E6C6C157E6C6C5DD807F0EC03F8D803FCEC0FF06CB4EC3FE03B007FF003FF8001 1FB548C7FC010714F8010114E09026001FFEC8FC32397BB63D> 91 D I<153FEC03FFEC0FE0EC3F80EC7E00495A5C495A A2495AB3AA130F5C131F495A91C7FC13FEEA03F8EA7FE048C8FCEA7FE0EA03F8EA00FE13 3F806D7E130F801307B3AA6D7EA26D7E80EB007EEC3F80EC0FE0EC03FFEC003F205B7AC3 2D> 102 D<12FCEAFFC0EA07F0EA01FCEA007E6D7E131F6D7EA26D7EB3AA801303806D7E 1300147FEC1FC0EC07FEEC00FFEC07FEEC1FC0EC7F0014FC1301495A5C13075CB3AA495A A2495A133F017EC7FC485AEA07F0EAFFC000FCC8FC205B7AC32D> I<126012F0B3B3B3B3 B11260045B76C319> 106 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmmi10 10.95 31 /Fm 31 122 df 22 D<020FB512FE027F14FF49B7FC1307 011F15FE903A3FE03FE00090387F000F01FE6D7E4848130348488048481301485A5B121F 5B123F90C7FC5A127EA2150300FE5D5AA24B5AA2150F5E4B5AA2007C4AC7FC157E157C6C 5C001E495A001FEB07E0390F800F802603E07EC8FC3800FFF8EB3FC030287DA634> 27 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A798919> 58 D<121EEA7F8012FF13C0 A213E0A3127FEA1E601200A413E013C0A312011380120313005A120E5A1218123812300B 1C798919> I<183818FC1703EF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB 03FEC7FCED0FF8ED3FE0EDFF80DA03FEC8FCEC0FF8EC3FE0ECFF80D903FEC9FCEB0FF8EB 3FE0EBFF80D803FECAFCEA0FF8EA3FE0EA7F8000FECBFCA2EA7F80EA3FE0EA0FF8EA03FE C66C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0F F8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FC17001838 363678B147> I I<126012F8B4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB 07FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF923800 7FC0EE1FF0EE07FCEE01FF9338007FC0EF1FF0EF07F8EF01FCA2EF07F8EF1FF0EF7FC093 3801FF00EE07FCEE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0 EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270 363678B147> I<17075F84171FA2173F177FA217FFA25E5EA24C6C7EA2EE0E3F161E161C 1638A21670A216E0ED01C084ED0380171FED07005D150E5DA25D157815705D844A5A170F 4A5A4AC7FC92B6FC5CA2021CC7120F143C14384A81A24A140713015C495AA249C8FC5B13 0E131E4982137C13FED807FFED1FFEB500F00107B512FCA219F83E417DC044> 65 D<49B712F818FF19E090260001FEC7EA3FF0F007F84B6E7E727E850203815D1A80A20207 167F4B15FFA3020F17004B5C611803021F5E4B4A5A180FF01FE0023F4B5A4B4A5ADD01FE C7FCEF07F8027FEC7FE092B6C8FC18E092C7EA07F84AEC01FE4A6E7E727E727E13014A82 181FA213034A82A301075F4A153FA261010F167F4A5E18FF4D90C7FC011F5E4A14034D5A 013FED1FF04D5A4AECFFC0017F020790C8FCB812FC17F094C9FC413E7DBD45> I<49B9FC A3D9000190C7120718004B157F193F191E14035DA314075D191CA2140F5D17074D133C02 1F020E13384B1500A2171E023F141C4B133C177C17FC027FEB03F892B5FCA39139FF8003 F0ED00011600A2495D5CA2160101035D5CA293C9FC13075CA3130F5CA3131F5CA2133FA2 5C497EB612F8A3403E7DBD3A> 70 D<49B6D8C03FB512F81BF01780D900010180C7383F F00093C85B4B5EA2197F14034B5EA219FF14074B93C7FCA260140F4B5DA21803141F4B5D A21807143F4B5DA2180F4AB7FC61A20380C7121F14FF92C85BA2183F5B4A5EA2187F1303 4A5EA218FF13074A93C8FCA25F130F4A5DA21703131F4A5DA2013F1507A24A5D496C4A7E B6D8E01FB512FCA2614D3E7DBD4C> 72 D 83 D<48B912FCA25A913A0003FE000F01F84A1301D807E0EE00F8491307491778000F5D90C7 FC001E140FA2001C4B1470123C0038141FA200785D1270033F15F000F018E0485DC81600 157FA25EA215FFA293C9FCA25CA25DA21403A25DA21407A25DA2140FA25DA2141FA25DA2 143FA25DA2147FA214FF497F001FB612FCA25E3E3D7FBC35> I<027FB5D88007B512C091 B6FCA2020101F8C7EBF8009126007FE0EC7F804C92C7FC033F157C701478616F6C495A4E 5A6F6C495A4EC8FC180E6F6C5B606F6C5B6017016F6C485A4D5A6F018FC9FC179E17BCEE 7FF85F705AA3707EA283163F167FEEF7FCED01E7EEC3FEED0383ED070392380E01FF151E 4B6C7F5D5D4A486D7E4A5A4A486D7E92C7FC140E4A6E7E5C4A6E7E14F0495A49486E7E13 07D91F806E7ED97FC014072603FFE0EC1FFF007F01FC49B512FEB55CA24A3E7EBD4B> 88 D I 97 D I I I I<163EEEFFC0923803E1E0923807C0F0ED0F811687ED1F8F 160F153FA217E092387E038093C7FCA45DA514015DA30103B512FCA390260003F0C7FCA3 14075DA4140F5DA5141F5DA4143F92C8FCA45C147EA414FE5CA413015CA4495AA35CEA1E 07127F5C12FF495AA200FE90C9FCEAF81EEA703EEA7878EA1FF0EA07C02C537CBF2D> I< EB01FC13FF5CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA291C9FC15FE90 397F07FFC091381F03E090397E3801F09138F000F8EBFFE04A7F5C91C7FC485AA25BA248 4813015E5BA2000714035E5B1507120F5E49130F5E121F031F1370491480A2003F023F13 F0EE00E090C7FC160148023E13C01603007E1680EE070000FE5DED1F1E48EC0FF80038EC 03E02C407CBE34> 104 D<143C14FEA21301A314FCEB00701400AD137E3801FF803803C7 C0EA0703000F13E0120E121C13071238A2EA780F007013C0A2EAF01F14801200133F1400 5B137EA213FE5BA212015B0003130E13F0A20007131EEBE01CA2143CEBC0381478147014 E013C13803E3C03801FF00EA007C173E7EBC1F> I I I<01F8EB0FF0D803FEEB3FFC3A078F80 F03E3A0F0F83C01F3B0E07C7800F80001CEBCF0002FE80003C5B00385B495A127800705B A200F049131F011F5D00005BA2163F013F92C7FC91C7FC5E167E5B017E14FE5EA201FE01 01EB03804914F8A203031307000103F013005B170E16E000035E49153C17385F00079138 01F1E0496DB45AD801C0023FC7FC31297EA737> 110 D 112 D<91381F800C9138FFE01C903903F0707C90 390FC0387890391F801CF890383F000F137E4914F000011407485A485A16E0485A121F15 0F484814C0A3007F141F491480A300FF143F90C71300A35D48147EA315FE007E495A1403 A26C13074A5A381F801D000F13793807C1F33901FFC3F038007F03130014075DA3140F5D A3141F5DA2143F147F90381FFFFE5BA2263A7DA729> I<147014FC1301A25CA21303A25C A21307A25CA2130FA25CA2007FB512F0B6FC15E039001F8000133FA291C7FCA25BA2137E A213FEA25BA21201A25BA21203A25BA21207EC01C013E01403000F1480A2EBC007150014 0E141E5C000713385C3803E1E03801FF80D8003EC7FC1C3A7EB821> 116 D 120 D<137C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F001C 168013071238163FD8780F150000705BA2D8F01F5C4A137E1200133F91C712FE5E5B137E 150113FE495CA2150300015D5BA215075EA2150F151F00005D6D133F017C137F017E13FF 90393F03DF8090380FFF1FEB01FC90C7123F93C7FCA25DD80380137ED80FE013FE001F5C 4A5AA24848485A4A5A6CC6485A001C495A001E49C8FC000E137C380781F03803FFC0C648 C9FC2A3B7EA72D> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmbx12 12 41 /Fn 41 122 df 46 D 49 D I I<163FA2 5E5E5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E147E147C 14F8EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B48C7FC12 3E5A12FCB91280A5C8000F90C7FCAC027FB61280A531417DC038> I<0007150301E0143F 01FFEB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC 01C714C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D13804915C0497F6C4815 E0C8FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815E05B007EC74813 C0123E003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0C65D013F148001 0F01FCC7FC010113C02D427BC038> I 58 D 65 D I I I I I 73 D 76 D 80 D 82 D I<003FBA12E0A59026FE000FEB8003D87FE09338003FF049171F90C716 07A2007E1803007C1801A300781800A400F819F8481978A5C81700B3B3A20107B8FCA545 437CC24E> I 86 D<903801FFE0011F13FE017F6D7E48B612E03A03FE 007FF84848EB1FFC6D6D7E486C6D7EA26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC 91B6FC1307013F13F19038FFFC01000313E0000F1380381FFE00485A5B127F5B12FF5BA3 5DA26D5B6C6C5B4B13F0D83FFE013EEBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB 8007D90FFCC9FC322F7DAD36> 97 D I I I I I I I<137C48B4FC4813804813C0A24813E0A56C13C0A26C13806C 1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520> I 108 D<90277F8007FEEC0FFCB590263FFFC0 90387FFF8092B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC00FFE1F80 1FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A5D4A5DA3 4A5DB3A7B60081B60003B512FEA5572D7CAC5E> I<90397F8007FEB590383FFF8092B512 E0028114F8913987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D7E5CA25C A35CB3A7B60083B512FEA5372D7CAC3E> I I<90397FC00FF8B590B57E02C314E002CF14F89139DFC03FFC9139FF001F FE000301FCEB07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF3FFCACEF7FF8 A318F017FFA24C13E06E15C06E5B6E4913806E4913006E495A9139DFC07FFC02CFB512F0 02C314C002C091C7FCED1FF092C9FCADB67EA536407DAC3E> I<90387F807FB53881FFE0 028313F0028F13F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8 ED01E092C7FCA35CB3A5B612E0A5272D7DAC2E> 114 D<90391FFC038090B51287000314 FF120F381FF003383FC00049133F48C7121F127E00FE140FA215077EA27F01E090C7FC13 FE387FFFF014FF6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F020313E0 140000F0143FA26C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F009038F803FE 90B55A00FC5CD8F03F13E026E007FEC7FC232F7CAD2C> I II I 120 D I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmbx12 14.4 27 /Fo 27 122 df<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7 FCB3B3B3A6007FB712FEA52F4E76CD43> 49 D I<91 380FFFC091B512FC0107ECFF80011F15E090263FF8077F9026FF800113FC4848C76C7ED8 03F86E7E491680D807FC8048B416C080486D15E0A4805CA36C17C06C5B6C90C75AD801FC 1680C9FC4C13005FA24C5A4B5B4B5B4B13C04B5BDBFFFEC7FC91B512F816E016FCEEFF80 DA000713E0030113F89238007FFE707E7013807013C018E07013F0A218F8A27013FCA218 FEA2EA03E0EA0FF8487E487E487EB57EA318FCA25E18F891C7FC6C17F0495C6C4816E001 F04A13C06C484A1380D80FF84A13006CB44A5A6CD9F0075BC690B612F06D5D011F158001 0302FCC7FCD9001F1380374F7ACD43> I<177C17FEA2160116031607160FA2161F163F16 7FA216FF5D5DA25D5DED1FBFED3F3F153E157C15FCEC01F815F0EC03E01407EC0FC01580 EC1F005C147E147C5C1301495A495A5C495A131F49C7FC133E5B13FC485A5B485A120748 5A485A90C8FC123E127E5ABA12C0A5C96C48C7FCAF020FB712C0A53A4F7CCE43> I<171F 4D7E4D7EA24D7EA34C7FA24C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C 7E03018116F8830303814C7E03078116E083030F814C7E031F81168083033F8293C77E4B 82157E8403FE824B800201835D840203834B800207835D844AB87EA24A83A3DA3F80C880 92C97E4A84A2027E8202FE844A82010185A24A820103854A82010785A24A82010F855C01 1F717FEBFFFCB600F8020FB712E0A55B547BD366> 65 D I 80 D<93380FFFC00303B6FC031F15E092B712FC0203D9FC0013 FF020F01C0010F13C0023F90C7000313F0DA7FFC02007F902601FFF0ED3FFE49496F7E49 496F7F49496F7F4990C96C7F4948707F4948707F01FF854A177F48864849717EA2484971 1380A2481BC04A83481BE0A24A83481BF0A3481BF8A291CB7EA3B51AFCAF6C1BF8A26E5F A36C1BF0A36C6D4D13E0A36C1BC06E5F6C1B806E5F6CDB01FE16006C6D902607FF80495A 4C13E06C6D013F6D495A017F91267F03F85C6D6C90277C00FC015B6D6C49D97E035B6D01 806E485B6D6D48D91F8F5B6D01E0039F90C7FC6D01F06EB45A6DD9FCF85DDA3FFF6E13F0 020F6D4913C0020301FF90B5C8FC020091B512FC031F180C0303181EDB001FEBE3FE93C7 EA01FF74133E74137E7413FEF2F8077290B5FC1CFCA285A21CF8A2851CF07314E0A27314 C0731480731400735B9638007FF8F21FE0576A79D265> I<003FBC1280A59126C0003F90 38C0007F49C71607D87FF8060113C001E08449197F49193F90C8171FA2007E1A0FA3007C 1A07A500FC1BE0481A03A6C994C7FCB3B3AC91B912F0A553517BD05E> 84 D 97 D I<913801FFF8021FEBFF8091B612F0010315FC010F9038C00FFE903A1FFE0001 FFD97FFC491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC486F1300705A48 92C8FC5BA312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F6CEE1F806C6DEC 3F006C6D147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A01001580023F49C7FC 020113E033387CB63C> I<4DB47E0407B5FCA5EE001F1707B3A4913801FFE0021F13FC91 B6FC010315C7010F9038E03FE74990380007F7D97FFC0101B5FC49487F4849143F484980 485B83485B5A91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F6C6D5C7E6C6D5C6C 6D49B5FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B5128F0101ECFE0FD9 003F13F8020301C049C7FC41547CD24B> I<913803FFC0023F13FC49B6FC010715C04901 817F903A3FFC007FF849486D7E49486D7E4849130F48496D7E48178048497F18C0488191 C7FC4817E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F7EA218E06CEE01 F06E14037E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE 903A0FFFC03FF8010390B55A010015C0021F49C7FC020113F034387CB63D> I 103 D I<137F497E000313E0487FA2487FA76C5B A26C5BC613806DC7FC90C8FCADEB3FF0B5FCA512017EB3B3A6B612E0A51B547BD325> I< EB3FF0B5FCA51203C6FCB3A54CB512F8A59339003FFE00EF1FF0EF3FC04D5A4DC7FCEE03 FEEE07F84C5A4C5AEE7FC04CC8FC4B5A4B5AED0FF8ED1FE04B7E4B7EECF1FF02F37F02F7 7F91B6FC83159F030F7F02FE80DAF8077F4A7E6F7F6F7F83707E82707F84707F707F8270 7F84707F177F717E4D13C0B6D8F003B6FCA540537CD247> 107 D I I I<913801FFE0021F13FE91B612C0010315F0010F9038807FFC903A1FFC000FFED97F F86D6C7E49486D7F48496D7F48496D7F4A147F48834890C86C7EA24883A248486F7EA300 7F1880A400FF18C0AC007F1880A3003F18006D5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C 6D495B6C6D495B6D6C495BD93FFE011F90C7FC903A0FFF807FFC6D90B55A010015C0023F 91C8FC020113E03A387CB643> I<90397FE003FEB590380FFF80033F13E04B13F09238FE 1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02FEEB3FFC5CEE1F F8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537> 114 D<903903FFF00F013FEBFE1F 90B7FC120348EB003FD80FF81307D81FE0130148487F4980127F90C87EA24881A27FA27F 01F091C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C816C816C81C681013F158001 0F15C01300020714E0EC003F030713F015010078EC007F00F8153F161F7E160FA27E17E0 7E6D141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FFC00FFC6DB55AD8FC1F14E0D8 F807148048C601F8C7FC2C387CB635> I<143EA6147EA414FEA21301A313031307A2130F 131F133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE07C0AB011FEC0F8080A26DEC 1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C5B021F5B020313802A4D7ECB34> I I 121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmr10 10.95 75 /Fp 75 123 df 2 D<4AB4EB0FE0021F9038E03FFC913A7F00F8FC1ED901FC90383FF03FD907 F090397FE07F80494801FF13FF4948485BD93F805C137F0200ED7F00EF003E01FE6D91C7 FC82ADB97EA3C648C76CC8FCB3AE486C4A7E007FD9FC3FEBFF80A339407FBF35> 11 D I I I<001E130F397F803FC000FF137F01C013E0 A201E013F0A3007F133F391E600F3000001300A401E01370491360A3000114E04913C000 03130101001380481303000EEB070048130E0018130C0038131C003013181C1C7DBE2D> 34 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380120313 005A120E5A1218123812300B1C79BE19> 39 D<1430147014E0EB01C0EB03801307EB0F 00131E133E133C5B13F85B12015B1203A2485AA2120F5BA2121F90C7FCA25AA3123E127E A6127C12FCB2127C127EA6123E123FA37EA27F120FA27F1207A26C7EA212017F12007F13 787F133E131E7FEB07801303EB01C0EB00E014701430145A77C323> I<12C07E12707E7E 121E7E6C7E7F12036C7E7F12007F1378137CA27FA2133F7FA21480130FA214C0A3130714 E0A6130314F0B214E01307A614C0130FA31480A2131F1400A25B133EA25BA2137813F85B 12015B485A12075B48C7FC121E121C5A5A5A5A145A7BC323> I<1506150FB3A9007FB912 E0BA12F0A26C18E0C8000FC9FCB3A915063C3C7BB447> 43 D<121EEA7F8012FF13C0A2 13E0A3127FEA1E601200A413E013C0A312011380120313005A120E5A1218123812300B1C 798919> I I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A79 8919> I 48 D I I I<150E151E153EA2157EA215FE1401A21403EC07 7E1406140E141CA214381470A214E0EB01C0A2EB0380EB0700A2130E5BA25B5BA25B5B12 01485A90C7FC5A120E120C121C5AA25A5AB8FCA3C8EAFE00AC4A7E49B6FCA3283E7EBD2D > I<00061403D80780131F01F813FE90B5FC5D5D5D15C092C7FC14FCEB3FE090C9FCACEB 01FE90380FFF8090383E03E090387001F8496C7E49137E497F90C713800006141FC813C0 A216E0150FA316F0A3120C127F7F12FFA416E090C7121F12FC007015C012780038EC3F80 123C6CEC7F00001F14FE6C6C485A6C6C485A3903F80FE0C6B55A013F90C7FCEB07F8243F 7CBC2D> I I<1238123C123F90B612 FCA316F85A16F016E00078C712010070EC03C0ED078016005D48141E151C153C5DC81270 15F04A5A5D14034A5A92C7FC5C141EA25CA2147C147814F8A213015C1303A31307A3130F 5CA2131FA6133FAA6D5A0107C8FC26407BBD2D> I I I<121E EA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A 2779A619> I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3121E127FEAFF80A213C0 A4127F121E1200A412011380A3120313005A1206120E120C121C5A1230A20A3979A619> I<007FB912E0BA12F0A26C18E0CDFCAE007FB912E0BA12F0A26C18E03C167BA147> 61 D 63 D<15074B7EA34B7EA34B7EA34B7EA34B7E15E7A2913801C7FC15C3A2913803 81FEA34AC67EA3020E6D7EA34A6D7EA34A6D7EA34A6D7EA34A6D7EA349486D7E91B6FCA2 49819138800001A249C87EA24982010E157FA2011E82011C153FA2013C820138151FA201 7882170F13FC00034C7ED80FFF4B7EB500F0010FB512F8A33D417DC044> 65 D I II 70 D I I I 76 D I I I I I I I<003FB91280A3903AF0007FE001018090393FC0003F48C7ED1FC0007E1707127C 00781703A300701701A548EF00E0A5C81600B3B14B7E4B7E0107B612FEA33B3D7DBC42> I I 87 D 91 D<486C13C0000313010100 1380481303000EEB070048130E0018130C0038131C003013180070133800601330A300E0 1370481360A400CFEB678039FFC07FE001E013F0A3007F133FA2003F131F01C013E0390F 0007801C1C73BE2D> I I 97 D I<49B4 FC010F13E090383F00F8017C131E4848131F4848137F0007ECFF80485A5B121FA24848EB 7F00151C007F91C7FCA290C9FC5AAB6C7EA3003FEC01C07F001F140316806C6C13076C6C 14000003140E6C6C131E6C6C137890383F01F090380FFFC0D901FEC7FC222A7DA828> I< ED01FC15FFA3150715031501B114FF010713E190381F80F990387E003D49131FD803F813 07485A49130348481301121F123F5B127FA290C7FCA25AAA7E7FA2123FA26C7E000F1403 7F000714076C6C497E6C6C497ED8007C017913F890383F01F190380FFFC1903A01FE01FC 002D407DBE33> I I I<167C903903F801FF903A1FFF078F8090397E0FDE1F9038F803 F83803F001A23B07E000FC0600000F6EC7FC49137E001F147FA8000F147E6D13FE00075C 6C6C485AA23901F803E03903FE0FC026071FFFC8FCEB03F80006CAFC120EA3120FA27F7F 6CB512E015FE6C6E7E6C15E06C810003813A0FC0001FFC48C7EA01FE003E140048157E82 5A82A46C5D007C153E007E157E6C5D6C6C495A6C6C495AD803F0EB0FC0D800FE017FC7FC 90383FFFFC010313C0293D7EA82D> I I I<1478EB01FEA2EB03FF A4EB01FEA2EB00781400AC147FEB7FFFA313017F147FB3B3A5123E127F38FF807E14FEA2 14FCEB81F8EA7F01387C03F0381E07C0380FFF803801FC00185185BD1C> I I I<2701F801FE14FF00FF902707FFC00313 E0913B1E07E00F03F0913B7803F03C01F80007903BE001F87000FC2603F9C06D487F0001 01805C01FBD900FF147F91C75B13FF4992C7FCA2495CB3A6486C496CECFF80B5D8F87FD9 FC3F13FEA347287DA74C> I<3901F801FE00FF903807FFC091381E07E091387803F00007 9038E001F82603F9C07F0001138001FB6D7E91C7FC13FF5BA25BB3A6486C497EB5D8F87F 13FCA32E287DA733> I<14FF010713E090381F81F890387E007E01F8131F4848EB0F8048 48EB07C04848EB03E0000F15F04848EB01F8A2003F15FCA248C812FEA44815FFA96C15FE A36C6CEB01FCA3001F15F86C6CEB03F0A26C6CEB07E06C6CEB0FC06C6CEB1F80D8007EEB 7E0090383F81FC90380FFFF0010090C7FC282A7EA82D> I<3901FC03FC00FF90381FFF80 91387C0FE09039FDE003F03A07FFC001FC6C496C7E6C90C7127F49EC3F805BEE1FC017E0 A2EE0FF0A3EE07F8AAEE0FF0A4EE1FE0A2EE3FC06D1580EE7F007F6E13FE9138C001F890 39FDE007F09039FC780FC0DA3FFFC7FCEC07F891C9FCAD487EB512F8A32D3A7EA733> I< 02FF131C0107EBC03C90381F80F090397F00387C01FC131CD803F8130E4848EB0FFC1507 48481303121F485A1501485AA448C7FCAA6C7EA36C7EA2001F14036C7E15076C6C130F6C 7E6C6C133DD8007E137990383F81F190380FFFC1903801FE0190C7FCAD4B7E92B512F8A3 2D3A7DA730> I<3901F807E000FFEB1FF8EC787CECE1FE3807F9C100031381EA01FB1401 EC00FC01FF1330491300A35BB3A5487EB512FEA31F287EA724> I<90383FC0603901FFF8 E03807C03F381F000F003E1307003C1303127C0078130112F81400A27E7E7E6D1300EA7F F8EBFFC06C13F86C13FE6C7F6C1480000114C0D8003F13E0010313F0EB001FEC0FF800E0 1303A214017E1400A27E15F07E14016C14E06CEB03C0903880078039F3E01F0038E0FFFC 38C01FE01D2A7DA824> I<131CA6133CA4137CA213FCA2120112031207001FB512C0B6FC A2D801FCC7FCB3A215E0A912009038FE01C0A2EB7F03013F138090381F8700EB07FEEB01 F81B397EB723> I I I< B53BC3FFFE03FFF8A3290FFE003FE00013C06C486D48EB3F806C4817006D010F141E0001 6F131C15076D163C00004A6C1338A2017F5E4B7E151DD93F805DED3DFC1538D91FC04A5A ED78FE9238707E03D90FE0017F5BEDE03F02F0140701070387C7FC9138F1C01F02F9148F 010315CE9138FB800F02FF14DE6D15FCED00076D5DA24A1303027E5CA2027C1301023C5C 023813003D287EA642> I I I<001FB61280A2EB E0000180140049485A001E495A121C4A5A003C495A141F00385C4A5A147F5D4AC7FCC648 5AA2495A495A130F5C495A90393FC00380A2EB7F80EBFF005A5B48481307120749140048 5A48485BA248485B4848137F00FF495A90B6FCA221277EA628> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmbx12 17.28 15 /Fq 15 117 df 45 D<16F04B7E1507151F153FEC01FF140714 7F010FB5FCB7FCA41487EBF007C7FCB3B3B3B3007FB91280A6395E74DD51> 49 D 52 D<01C0EE01C0D801F8160F01FF167F02F0EC07FFDAFF8090B5FC92B71280190060606060 60606095C7FC17FC5F17E0178004FCC8FC16E09026FC3FFCC9FC91CBFCADED3FFE0203B5 12F0020F14FE023F6E7E91B712E001FDD9E00F7F9027FFFE00037F02F801007F02E06EB4 FC02806E138091C8FC496F13C04917E07113F0EA00F090C914F8A219FC83A219FEA419FF A3EA03F0EA0FFC487E487E487FA2B57EA319FEA35C4D13FC6C90C8FC5B4917F8EA3FF001 804B13F06D17E0001F5E6C6C17C06D4B1380D807FC92B512006C6C4A5B6C6C6C01075B6C 01E0011F5BD97FFE90B55A6DB712C0010F93C7FC6D15FC010115F0D9003F1480020301F0 C8FC406078DD51> I 58 D 65 D 103 D<903807FF80B6FCA6C6FC7F7FB3A8EF1FFF94 B512F0040714FC041F14FF4C8193267FE07F7F922781FE001F7FDB83F86D7FDB87F07FDB 8FC0814C7F039FC78015BE03BC8003FC825DA25DA25DA45DB3B2B7D8F007B71280A65164 7BE35A> I I< 903807FF80B6FCA6C6FC7F7FB3B3B3B3ADB712E0A623647BE32C> 108 D<902607FF80D91FFFEEFFF8B691B500F00207EBFF80040702FC023F14E0041F02FF91B6 12F84C6F488193267FE07F6D4801037F922781FE001F9027E00FF0007FC6DA83F86D9026 F01FC06D7F6DD987F06D4A487F6DD98FC0DBF87EC7804C6D027C80039FC76E488203BEEE FDF003BC6E4A8003FC04FF834B5FA24B5FA24B94C8FCA44B5EB3B2B7D8F007B7D8803FB6 12FCA67E417BC087> I<923807FFE092B6FC020715E0021F15F8027F15FE494848C66C6C 7E010701F0010F13E04901C001037F49496D7F4990C87F49486F7E49486F7E48496F1380 4819C04A814819E048496F13F0A24819F8A348496F13FCA34819FEA4B518FFAD6C19FEA4 6C6D4B13FCA36C19F8A26C6D4B13F0A26C19E06C6D4B13C0A26C6D4B13806C6D4B13006D 6C4B5A6D6D495B6D6D495B010701F0010F13E06D01FE017F5B010090B7C7FC023F15FC02 0715E0020092C8FC030713E048437CC151> 111 D 114 D<913A3FFF8007800107B5EAF81F011FECFE7F017F91B5FC48B8FC48EBE0014890 C7121FD80FFC1407D81FF0801600485A007F167F49153FA212FF171FA27F7F7F6D92C7FC 13FF14E014FF6C14F8EDFFC06C15FC16FF6C16C06C16F06C826C826C826C82013F168001 0F16C01303D9007F15E0020315F0EC001F1500041F13F81607007C150100FC81177F6C16 3FA2171F7EA26D16F0A27F173F6D16E06D157F6D16C001FEEDFF806D0203130002C0EB0F FE02FCEB7FFC01DFB65A010F5DD8FE0315C026F8007F49C7FC48010F13E035437BC140> I I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmbx10 10.95 21 /Fr 21 121 df 45 D I<140F143F5C495A130F48B5FCB6FCA313F7 EAFE071200B3B3A8007FB612F0A5243C78BB34> 49 D<903803FF80013F13F890B512FE 00036E7E4881260FF80F7F261FC0037F4848C67F486C6D7E6D6D7E487E6D6D7EA26F1380 A46C5A6C5A6C5A0007C7FCC8FC4B1300A25E153F5E4B5AA24B5A5E4A5B4A5B4A48C7FC5D 4A5AEC1FE04A5A4A5A9139FF000F80EB01FC495A4948EB1F00495AEB1F8049C7FC017E5C 5B48B7FC485D5A5A5A5A5AB7FC5EA4293C7BBB34> I<903801FFE0010F13FE013F6D7E90 B612E04801817F3A03FC007FF8D807F06D7E82D80FFC131F6D80121F7FA56C5A5E6C4813 3FD801F05CC8FC4B5A5E4B5A4A5B020F5B902607FFFEC7FC15F815FEEDFFC0D9000113F0 6E6C7E6F7E6F7E6F7E1780A26F13C0A217E0EA0FC0487E487E487E487EA317C0A25D4915 80127F49491300D83FC0495A6C6C495A3A0FFE01FFF86CB65A6C5DC61580013F49C7FC01 0313E02B3D7CBB34> I I< 00071538D80FE0EB01F801FE133F90B6FC5E5E5E5E93C7FC5D15F85D15C04AC8FC0180C9 FCA9ECFFC0018713FC019F13FF90B67E020113E09039F8007FF0496D7E01C06D7E5B6CC7 7FC8120F82A31780A21207EA1FC0487E487E12FF7FA21700A25B4B5A6C5A01805C6CC712 3F6D495AD81FE0495A260FFC075B6CB65A6C92C7FCC614FC013F13F0010790C8FC293D7B BB34> I I<121F7F13F890B712 F0A45A17E017C0178017005E5E5A007EC7EA01F84B5A007C4A5A4B5A4B5A93C7FC485C15 7E5DC7485A4A5AA24A5A140F5D141F143F5D147FA214FF92C8FC5BA25BA3495AA3130FA5 131FAA6D5A6D5A6D5A2C3F7ABD34> I I<903801FFE0010F13 FC013F13FF90B612C04801E07F489038003FF048486D7E000F6E7E485A6F7E123F484880 81178012FFA217C0A517E0A4007F5CA4003F5C6C7E5D6C7E00075C3903FF80FB6C13FF6C 6C13F36D13C3010F018313C090380008031400A24B1380EA03F0487E486C1500487E4B5A A25E151F4B5A495C6C48EBFFE049485B2607FC0F5B6CB6C7FC6C14FC6C14F06D13C0D90F FEC8FC2B3D7CBB34> I I 69 D 76 D<903807FFC0013F13F848 B6FC48812607FE037F260FF8007F6DEB3FF0486C806F7EA36F7EA26C5A6C5AEA01E0C8FC 153F91B5FC130F137F3901FFFE0F4813E0000F1380381FFE00485A5B485A12FF5BA4151F 7F007F143F6D90387BFF806C6C01FB13FE391FFF07F36CEBFFE100031480C6EC003FD91F F890C7FC2F2B7DA933> 97 D 99 D 101 D<13FFB5FCA512077EB3B3AFB512FCA516 3F7CBE1D> 108 D<01FFD91FF8ECFFC0B590B5010713F80203DAC01F13FE4A6E487FDA0F E09026F07F077F91261F003FEBF8010007013EDAF9F0806C0178ECFBC04A6DB4486C7FA2 4A92C7FC4A5CA34A5CB3A4B5D8FE07B5D8F03FEBFF80A551297CA858> I<01FFEBFFE0B5 000713FC021FEBFF80027F80DAFF8113F09139FC007FF8000701F06D7E6C496D7E4A130F 4A6D7E1880A27013C0A38218E0AA4C13C0A318805E18005E6E5C6E495A6E495A02FCEBFF F0DAFF035B92B55A029F91C7FC028713FC028113C00280C9FCACB512FEA5333B7DA83A> 112 D 120 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(1) p 0 -191 3900 4 v 0 66 4018 4 v 0 503 4 437 v Fq 59 230 a(15-451:) 51 b(Algorithms) p Fp 59 421 a(Lecture) 30 b(3:) h(Quic) m(ksort) p 4014 503 V 0 506 4018 4 v Fo 0 888 a(1) 135 b(Probabilit) l(y) 46 b(and) f(Algorithms) p Fn 0 1133 a(1.1) 112 b(Av) m(erage) 38 b(Case) g(Running) f(Time) p Fp 0 1344 a(Giv) m(en) 30 b(an) h(algorithm) p Fm 29 w(A) p Fp 30 w(and) f(some) h(input) p Fm 28 w(x) p Fp 31 w(w) m(e) f(w) m(an) m(t) i(to) f(measure) f(the) h(\\running) d (time".) p Fl 136 1573 a(\017) p Fp 46 w(Time:) i(the) g(n) m(um) m(b) s (er) g(of) g(steps) g(in) f(the) i(execution) g(of) f(the) h (algorithm.) 0 1802 y(W) -8 b(ritten) p Fm 31 w(T) p Fk 392 1816 a(A) p Fp 464 1802 a(\() p Fm(x) p Fp(\)) q(.) 0 1954 y(Usually) 29 b(one) h(lumps) f(together) i(all) f(inputs) e(of) j (the) f(same) h(size) f(and) g(sets) p Fm 1223 2136 a(T) p Fk 1276 2150 a(A) p Fp 1348 2136 a(\() p Fm(n) p Fp(\)) c(=) f(max) p Fj 1764 2062 a(\000) p Fm 1821 2136 a(T) p Fk 1874 2150 a(A) p Fp 1946 2136 a(\() p Fm(x) p Fp(\)) p Fj 2094 2059 a(\014) 2094 2113 y(\014) p Fm 2149 2136 a(x) p Fp 31 w(has) 30 b(size) p Fm 30 w(n) p Fj 2636 2062 a(\001) p Fp 0 2318 a(This) 22 b(is) i(the) p Fi 24 w(worst-c) -5 b(ase) 29 b(c) -5 b(omplexity) p Fp 26 w(since) 23 b(w) m(e) i(tak) m (e) h(the) e(maxim) m(um) f(o) m(v) m(er) j(all) d(inputs) f(of) i (length) p Fm 24 w(n) p Fp(.) g(P) m(oten) m(tially) 0 2430 y(more) 31 b(in) m(teresting) e(is) h(the) p Fi 30 w(aver) -5 b(age-c) g(ase) 34 b(c) -5 b(omplexity) p Fm 1433 2621 a(T) p Fh 1499 2576 a(a) n(vg) p Fk 1486 2649 a(A) p Fp 1625 2621 a(\() p Fm 1 w(n) p Fp(\)) 25 b(=) p Fj 1894 2534 a(X) p Fg 1872 2736 a(j) p Fk -1 w(x) p Fg(j) p Fh(=) p Fk(n) p Fm 2063 2621 a(p) p Fk 2109 2635 a(x) p Fl 2173 2621 a(\001) p Fm 21 w(T) p Fk 2272 2635 a(A) p Fp 2344 2621 a(\() p Fm(x) p Fp(\)) 0 2902 y(where) p Fm 30 w(p) p Fk 309 2916 a(x) p Fp 383 2902 a(is) k(the) i(probabilit) m(y) d(of) i(input) p Fm 29 w(x) p Fp(.) g(The) g(a) m(v) m(erage) j(space) e(complexit) m(y) f(is) f(de\014ned) h(similarly) -8 b(.) 27 b(Clearly) p Fm 1606 3083 a(T) p Fh 1672 3039 a(a) n(vg) p Fk 1659 3112 a(A) p Fp 1797 3083 a(\() p Fm 1 w(n) p Fp(\)) p Fl 25 w(\024) p Fm 25 w(T) p Fk 2097 3097 a(A) p Fp 2169 3083 a(\() p Fm 1 w(n) p Fp(\)) 0 3265 y(but) j(the) g(w) m(orst-case) i (complexit) m(y) e(ma) m(y) h(b) s(e) f(strictly) g(higher.) 0 3417 y(Note) 35 b(that) f(the) g(sample) f(space) i(here) e(consists) h (of) g(all) e(instances) i(of) f(size) p Fm 34 w(n) p Fp(,) h(and) f(it) g(ma) m(y) i(not) f(b) s(e) f(at) h(all) f(clear) 0 3530 y(what) p Fm 35 w(p) p Fk 278 3544 a(x) p Fp 357 3530 a(is) i(a) g(realistic) f(setting.) i(But,) g(w) m(e) g(still) d (can) j(hop) s(e) e(to) j(get) f(some) g(useful) d(information) h(b) m (y) h(assuming) 0 3643 y(some) c(distribution) 26 b(\(suc) m(h) 31 b(as) g(the) f(uniform) e(distribution\).) p Fn 0 3922 a(1.2) 112 b(Probabilistic) 34 b(Algorithms) p Fp 0 4133 a(Another) d(imp) s(ortan) m(t) f(source) h(of) g(probabilit) m(y) d (problems) i(in) f(the) i(theory) g(of) g(algorithms) f(are) i (algorithms) d(that) 0 4246 y(use) e(randomized) f(computations:) h (the) h(execution) f(of) h(the) f(algorithm) g(is) f(not) h (deterministic) f(as) h(usual,) f(but) h(the) 0 4358 y(algorithm) i(ma) m(y) i(rely) f(on) g(the) h(\015ip) d(of) j(a) g (coin) f(to) h(determine) e(the) i(next) f(step.) 0 4510 y(In) g(the) h(simple) e(case,) j(the) f(output) f(will) e(b) s(e) i (alw) m(a) m(ys) i(b) s(e) e(the) h(same,) g(regardless) f(of) h(what) g (probabilistic) c(c) m(hoices) 0 4623 y(the) 36 b(algorithm) e(has) h (made) h(during) d(the) i(actual) h(computation.) g(Ho) m(w) m(ev) m (er,) h(the) f(length) f(of) g(the) h(computation) 0 4736 y(ma) m(y) 28 b(dep) s(end) d(v) m(ery) i(crucially) e(on) i (these) h(nondeterministic) c(c) m(hoices.) k(If) f(the) g(algorithm) f (is) g(prop) s(erly) f(designed,) 0 4849 y(then) 35 b(the) h(running) d (time) i(will) e(b) s(e) i(short) g(for) g(most) h(of) g(these) g(c) m (hoices.) g(Quic) m(ksort) f(is) g(a) h(t) m(ypical) f(example) g(for) 0 4962 y(this) 29 b(t) m(yp) s(e) i(of) f(algorithm.) 0 5114 y(A) 35 b(more) g(drastic) g(use) g(of) g(nondeterminism) d(is) i (to) i(ha) m(v) m(e) h(the) e(output) g(dep) s(end) e(on) i(the) g(c) m (hoices) h(made) f(during) 0 5227 y(the) i(computation.) f(F) -8 b(or) 37 b(example,) g(one) f(migh) m(t) h(c) m(hec) m(k) h(whether) d (a) i(n) m(um) m(b) s(er) e(is) h(prime) f(in) g(this) g(fashion.) g (The) 0 5340 y(crucial) 29 b(problem) g(here) h(is) g(to) h(guaran) m (tee) h(that) f(the) f(probabilit) m(y) e(for) i(a) h(wrong) f(answ) m (er) g(is) g(small.) p 90 rotate dyy eop %%Page: 2 2 2 1 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(2) p 0 -191 3900 4 v Fo 0 91 a(2) 135 b(Probabilit) l(y) 46 b(Theory) f(Basics) p Fn 0 337 a(2.1) 112 b(Sample) 37 b(Spaces) p Fp 0 547 a(W) -8 b(e) 39 b(need) e(a) h(few) g(basic) f (concepts) h(from) g(probabilit) m(y) d(theory) -8 b(.) 38 b(Think) e(ab) s(out) h(conducting) g(a) h(\(ph) m(ysical\)) f(ex-) 0 660 y(p) s(erimen) m(t) i(suc) m(h) i(as) g(\015ipping) c(a) k(coin,) g (or) f(rolling) f(t) m(w) m(o) j(dice.) e(The) g(collection) g(of) h (all) f(p) s(ossible) e(outcomes) k(of) 0 773 y(the) 35 b(exp) s(erimen) m(t) g(is) f(called) h(a) p Fi 35 w(sample) k(sp) -5 b(ac) g(e) p Fm 37 w(S) p Fp 40 w(and) 34 b(its) h(elemen) m(ts) h(are) f(the) p Fi 36 w(elementary) j(events) p Fp(.) e(Often) f(one) 0 886 y(considers) p Fi 30 w(\(c) -5 b(omp) g(ound\)) 36 b(events) p Fp 31 w(whic) m(h) 29 b(are) j(simply) c(collections) j(of) g(elemen) m(tary) g(ev) m(en) m(ts,) i(i.e.,) e(subsets) g(of) g(the) 0 999 y(sample) i(space.) h(F) -8 b(or) 35 b(example,) f(w) m(e) g(could) f(consider) f(all) h(outcomes) i(of) f(the) g(t) m(w) m(o-dice) h(exp) s (erimen) m(t) d(where) i(the) 0 1112 y(sum) 24 b(of) h(the) g(t) m(w) m (o) h(dice) e(is) g(8,) h(less) f(than) h(10,) h(ev) m(en) f(and) f(so) h(on.) g(F) -8 b(or) 26 b(the) f(time) f(b) s(eing) g(w) m(e) h(assume) f(that) i(the) f(sample) 0 1225 y(space) p Fm 31 w(S) p Fp 35 w(is) 30 b(\014nite.) 0 1377 y(W) -8 b(e) 27 b(w) m(an) m(t) f (to) g(asso) s(ciate) g(a) g(probabilit) m(y) d(for) i(the) h(o) s (ccurrence) f(of) h(eac) m(h) h(ev) m(en) m(t.) g(T) -8 b(o) 26 b(this) e(end) h(w) m(e) h(use) f(a) p Fi 26 w(pr) -5 b(ob) g(ability) 0 1490 y(me) g(asur) g(e) p Ff 32 w(Pr) p Fp 1 w([]) 31 b(that) g(assigns) e(a) i(real) f(n) m(um) m (b) s(er) f(to) i(eac) m(h) h(ev) m(en) m(t:) p Ff 1623 1688 a(Pr) p Fp 1 w([]) 26 b(:) p Fe 25 w(P) p Fp(\() p Fm(S) p Fp 5 w(\)) p Fl 27 w(!) p Fd 25 w(R) p Fm 1 w(:) p Fp 0 1885 a(In) 39 b(order) f(for) h(suc) m(h) g(a) h(function) e(to) i (re\015ect) g(our) f(in) m(tuitiv) m(e) f(understanding) f(of) i (probabilit) m(y) e(w) m(e) j(require) e(the) 0 1998 y(follo) m(wing) 29 b(prop) s(erties:) p Fl 136 2243 a(\017) p Fp 46 w(0) p Fl 26 w(\024) p Ff 25 w(Pr) p Fp 1 w([) p Fm(A) p Fp(]) d(=) p Fl(\024) p Fp 25 w(1) p Fl 136 2429 a(\017) p Ff 46 w(Pr) p Fp 2 w([) p Fm(S) p Fp 5 w(]) f(=) g(1) p Fl 136 2614 a(\017) p Fm 46 w(A) p Fl 21 w(\\) p Fm 19 w(B) p Fp 30 w(=) p Fl 25 w(;) p Fp 31 w(implies) p Ff 28 w(Pr) p Fp 1 w([) p Fm(A) p Fl 21 w([) p Fm 19 w(B) p Fp 5 w(]) g(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(A) p Fp(]) c(+) p Ff 20 w(Pr) p Fp 1 w([) p Fm(B) p Fp 5 w(]) p Fl 136 2799 a(\017) p Fp 46 w(If) p Fm 30 w(A) p Fk 386 2813 a(i) p Fl 435 2799 a(\\) p Fm 20 w(A) p Fk 584 2813 a(j) p Fp 646 2799 a(=) p Fl 24 w(;) p Fp 31 w(for) 30 b(all) p Fm 30 w(i) 25 b(<) g(j) p Fp 36 w(then) p Ff 30 w(Pr) p Fp 2 w([) p Fj 1631 2731 a(S) p Fk 1707 2826 a(i) p Fg(\025) p Fh(0) p Fm 1840 2799 a(A) p Fk 1908 2813 a(i) p Fp 1936 2799 a(]) h(=) p Fj 2083 2731 a(P) p Fk 2179 2826 a(i) p Fg(\025) p Fh(0) p Ff 2312 2799 a(Pr) p Fp 2 w([) p Fm(A) p Fk 2496 2813 a(i) p Fp 2524 2799 a(]) 0 3044 y(Here) p Fl 42 w(;) p Fp 42 w(is) 40 b(the) i(imp) s(ossible) c(ev) m(en) m(t,) 43 b(and) p Fm 41 w(S) p Fp 46 w(the) f(certain) f(ev) m(en) m(t,) i(so) f (that) g(the) g(probabilities) c(are) k(0) f(and) g(1,) 0 3157 y(resp) s(ectiv) m(ely) -8 b(.) 39 b(The) f(t) m(w) m(o) i (conditions) d(ab) s(out) h(m) m(utually) f(exclusiv) m(e) h(ev) m(en) m (ts) i(state) g(that) f(probabilities) c(simply) 0 3270 y(add) 30 b(up.) 0 3422 y(Since) f(ev) m(en) m(ts) j(are) e(subsets) f (of) i(the) f(sample) f(space) i(w) m(e) g(can) f(express) g(logical) f (constructs) h(in) f(terms) h(of) h(Bo) s(olean) 0 3535 y(op) s(erations) 41 b(on) g(sets.) g(F) -8 b(or) 42 b(example,) g(the) f(ev) m(en) m(t) p Fm 43 w(A) p Fl 27 w(\\) p Fm 27 w(B) p Fp 46 w(corresp) s(onds) f(to) i(\\ev) m(en) m (t) p Fm 43 w(A) p Fp 41 w(and) f(also) g(ev) m(en) m(t) p Fm 43 w(B) p Fp 5 w(".) 0 3648 y(Lik) m(ewise,) p 391 3575 69 4 v Fm 30 w(A) p Fp 25 w(=) p Fm 25 w(S) p Fl 25 w(\000) p Fm 20 w(A) p Fp 31 w(expresses) 30 b(the) g(ev) m(en) m(t) i(\\not) f(ev) m(en) m(t) p Fm 32 w(A) p Fp(".) g(Note) h(that) p Fl 136 3893 a(\017) p Ff 46 w(Pr) p Fp 2 w([) p 343 3820 V Fm(A) p Fp(]) 26 b(=) f(1) p Fl 20 w(\000) p Ff 20 w(Pr) p Fp 2 w([) p Fm(A) p Fp(].) p Fl 136 4079 a(\017) p Ff 46 w(Pr) p Fp 2 w([) p Fm(A) p Fl 20 w([) p Fm 20 w(B) p Fp 5 w(]) g(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(A) p Fp(]) 20 b(+) p Ff 20 w(Pr) p Fp 2 w([) p Fm(B) p Fp 5 w(]) p Fl 20 w(\000) p Ff 20 w(Pr) p Fp 1 w([) p Fm(A) p Fl 21 w(\\) p Fm 20 w(B) p Fp 4 w(].) 0 4324 y(If) 38 b(follo) m(ws) f(that) i(the) g(imp) s(ossible) 34 b(ev) m(en) m(t) 40 b(has) e(probabilit) m(y) e(0:) p Ff 39 w(Pr) p Fp 1 w([) p Fl(;) p Fp(]) k(=) e(1) p Fl 26 w(\000) p Ff 25 w(Pr) p Fp 1 w([) p Fm(S) p Fp 5 w(]) h(=) f(0.) h(The) f(last) g (equation) 0 4437 y(generalizes) 24 b(to) h(union) d(of) i(more) g (than) g(t) m(w) m(o) i(terms,) e(but) f(is) g(a) i(bit) e(clumsy) g (to) h(state) i(\(see) f(the) f(inclusion-exclusion) 0 4550 y(principle) j(in) i(com) m(binatorics\).) i(A) m(t) g(an) m(y) g (rate,) g(w) m(e) g(ha) m(v) m(e) h(Bo) s(de's) e(inequalit) m(y:) p Ff 845 4747 a(Pr) p Fp 1 w([) p Fm(A) p Fh 1028 4761 a(1) p Fl 1088 4747 a([) p Fm 20 w(A) p Fh 1237 4761 a(2) p Fl 1297 4747 a([) p Fm 20 w(:) 15 b(:) g(:) p Fl 21 w([) p Fm 20 w(A) p Fk 1653 4762 a(k) p Fp 1695 4747 a(]) p Fl 26 w(\024) p Ff 25 w(Pr) p Fp 1 w([) p Fm(A) p Fh 2025 4761 a(1) p Fp 2065 4747 a(]) 21 b(+) p Ff 20 w(Pr) p Fp 1 w([) p Fm(A) p Fh 2385 4761 a(2) p Fp 2425 4747 a(]) f(+) p Fm 20 w(:) 15 b(:) g(:) p Fp 21 w(+) p Ff 20 w(Pr) p Fp 2 w([) p Fm(A) p Fk 2962 4762 a(k) p Fp 3005 4747 a(]) p Fm(:) p Fp 0 4945 a(F) -8 b(or) 31 b(conjunctions) e(of) i(ev) m(en) m(ts) h(one) e(can) h(sho) m (w) f(Bonferroni's) g(inequalit) m(y:) p Ff 650 5142 a(Pr) p Fp 2 w([) p Fm(A) p Fh 834 5156 a(1) p Fl 894 5142 a(\\) p Fm 20 w(A) p Fh 1043 5156 a(2) p Fl 1102 5142 a(\\) p Fm 20 w(:) 15 b(:) g(:) p Fl 22 w(\\) p Fm 19 w(A) p Fk 1458 5157 a(k) p Fp 1501 5142 a(]) p Fl 26 w(\025) p Ff 25 w(Pr) p Fp 1 w([) p Fm(A) p Fh 1831 5156 a(1) p Fp 1871 5142 a(]) 20 b(+) p Ff 20 w(Pr) p Fp 2 w([) p Fm(A) p Fh 2191 5156 a(2) p Fp 2231 5142 a(]) g(+) p Fm 20 w(:) 15 b(:) g(:) p Fp 21 w(+) p Ff 20 w(Pr) p Fp 1 w([) p Fm(A) p Fk 2767 5157 a(k) p Fp 2811 5142 a(]) p Fl 20 w(\000) p Fp 20 w(\() p Fm(k) p Fl 24 w(\000) p Fp 20 w(1\)) p Fm(:) p 90 rotate dyy eop %%Page: 3 3 3 2 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(3) p 0 -191 3900 4 v Fp 0 91 a(F) -8 b(or) 41 b(ini\014nite) c (sample) i(spaces) h(one) h(has) e(to) i(con) m(tend) g(with) e(some) h (mathematical) g(problems) f(that) h(w) m(e) h(ha) m(v) m(e) 0 204 y(blithely) 31 b(ignored.) j(F) -8 b(or) 34 b(\014nite) f(and) g (coun) m(tably) h(in\014nite) d(spaces) k(one) f(can) g(indeed) e(form) i(the) g(necessary) g(sums) 0 317 y(to) 46 b(obtain) f(the) g (probabilit) m(y) e(of) i(a) h(comp) s(ound) d(ev) m(en) m(t.) k(The) e (sum) p Ff 44 w(Pr) p Fp 2 w([) p Fm(A) p Fp(]) 50 b(=) p Fj 2809 249 a(P) p Fk 2905 344 a(e) p Fg(2) p Fk(A) p Ff 3057 317 a(Pr) p Fp 1 w([) p Fm(e) p Fp(]) c(con) m(v) m(erges) i (since) p Fj 0 362 a(P) p Fk 96 457 a(e) p Fg(2) p Fk(S) p Ff 242 430 a(Pr) p Fp 1 w([) p Fm(e) p Fp(]) 26 b(=) f(1) h(and) f(the) h(terms) g(are) g(non-negativ) m(e.) h(But) f(for) f(uncoun) m(table) g (spaces) h(one) g(has) g(to) g(use) f(in) m(tegrals) 0 543 y(rather) e(than) g(sums.) g(W) -8 b(orse,) 25 b(one) e(often) h (has) f(to) h(mak) m(e) h(to) f(with) e(measures) h(that) h(are) g(not) f(de\014ned) f(for) h(all) g(subsets) p Fm 0 656 a(A) p Fl 30 w(\022) p Fm 30 w(S) p Fp 5 w(,) 34 b(but) f(only) f(for) h(a) h (large) f(class) g(of) h(suc) m(h) f(sets.) h(In) f(practice) g(these) h (di\016culties) d(are) j(irrelev) -5 b(an) m(t) 32 b(\(see) j(an) m(y) 0 769 y(text) c(on) g(measure) f(theory\).) p Fn 0 1049 a(2.2) 112 b(Computing) 37 b(Probabilit) m(y) p Fp 0 1260 a(The) c(axioms) f(from) h(ab) s(o) m(v) m(e) h(do) f(not) h (actually) f(determine) f(the) h(n) m(umerical) f(v) -5 b(alues) 32 b(of) i(a) f(probabilit) m(y) e(measure.) 0 1373 y(Ho) m(w) m(ev) m(er,) i(they) d(reduce) g(ev) m(erything) h(to) g (the) f(probabilit) m(y) e(of) j(the) f(basic) g(ev) m(en) m(ts:) p Ff 1607 1569 a(Pr) p Fp 1 w([) p Fm(A) p Fp(]) c(=) p Fj 1938 1483 a(X) p Fk 1937 1680 a(e) p Fg(2) p Fk(A) p Ff 2085 1569 a(Pr) p Fp 1 w([) p Fm(e) p Fp(]) p Fm(:) p Fp 0 1840 a(If) i(all) g(the) h(elemen) m(tary) h(ev) m(en) m(ts) g(ha) m(v) m(e) g(the) f(same) h(probabilit) m(y) c(w) m(e) j(sp) s(eak) g (ab) s(out) g(a) p Fi 29 w(uniform) j(pr) -5 b(ob) g(ability) 34 b(distri-) 0 1953 y(bution) p Fp(.) d(It) f(follo) m(ws) g(from) g(the) g(\014rst) g(prop) s(ert) m(y) g(that) h(in) e(this) g(case) p Ff 1766 2141 a(Pr) p Fp 2 w([) p Fm(e) p Fp(]) d(=) f(1) p Fm(=) p Fl 15 w(j) p Fm 1 w(S) p Fl 5 w(j) p Fp 0 2354 a(and) 30 b(therefore) p Ff 1612 2567 a(Pr) p Fp 1 w([) p Fm(A) p Fp(]) c(=) p Fl 25 w(j) p Fm(A) p Fl(j) p Fm 16 w(=) p Fl 15 w(j) p Fm 1 w(S) p Fl 5 w(j) p Fm 15 w(:) p Fp 0 2755 a(F) -8 b(or) 31 b(example,) f(assuming) f(that) i (our) f(t) m(w) m(o) i(dice) e(are) h(fair) e(the) i(probabilit) m(y) c (of) k(getting) g(a) g(sum) e(of) i(8) g(is) e(1) p Fm(=) p Fp(9.) 0 2986 y(In) d(the) i(non-uniform) c(case) 29 b(w) m(e) e(assume) g(that) h(w) m(e) f(ha) m(v) m(e) i(kno) m(wledge) e (ab) s(out) g(the) g(v) -5 b(alues) 26 b(of) p Ff 28 w(Pr) p Fp 1 w([) p Fm(e) p Fp(].) i(F) -8 b(or) 28 b(example,) 0 3098 y(for) h(a) h(coin) e(w) m(e) i(ma) m(y) g(assume) f(that) g(the) h (probabilit) m(y) c(of) k(heads) f(is) p Fm 28 w(p) p Fp 29 w(where) f(0) p Fm 26 w(<) d(p) g(<) p Fp 25 w(1.) 30 b(Then) e(the) h(probabilit) m(y) 0 3211 y(for) h(tails) g(is) f (forced) h(to) i(b) s(e) d(1) p Fl 21 w(\000) p Fm 20 w(q) p Fp 3 w(.) p Fn 0 3491 a(2.3) 112 b(Random) 38 b(V) -9 b(ariables) p Fp 0 3702 a(The) 34 b(outcome) j(of) e(an) g(exp) s(erimen) m(t) f(is) g(often) h(asso) s(ciated) g(with) f(a) h(n) m (umerical) f(quan) m(tit) m(y) -8 b(,) 36 b(suc) m(h) e(as) i(the) f (sum) f(of) 0 3815 y(rolled) d(dice.) i(F) -8 b(or) 34 b(a) f(coin) g(\015ip) e(w) m(e) i(ma) m(y) h(think) d(of) j(heads) e (as) h(pro) s(ducing) e(1) i(and) g(tails) f(as) h(pro) s(ducing) e(0.) i(Or) f(w) m(e) 0 3928 y(could) d(measure) i(the) f(distance) g(of) h (a) g(thro) m(wn) e(dart) i(to) g(the) f(cen) m(ter) i(of) e(the) h (target.) 0 4080 y(Corresp) s(ondingly) c(one) j(de\014nes) g(a) p Fi 31 w(r) -5 b(andom) 35 b(variable) p Fp 31 w(as) c(a) f(function) p Fm 1725 4268 a(X) p Fp 33 w(:) p Fm 25 w(S) p Fl 30 w(!) p Fd 26 w(R) p Fm 1 w(:) p Fp 0 4456 a(Note) 23 b(that) f(one) g(can) g (add) f(random) g(v) -5 b(ariables:) 20 b(\() p Fm(X) p Fp 10 w(+) p Fm 3 w(Y) p Fp 20 w(\)\() p Fm(e) p Fp(\)) 26 b(=) p Fm 25 w(X) p Fp 7 w(\() p Fm(e) p Fp(\)) s(+) p Fm 3 w(Y) p Fp 21 w(\() p Fm(e) p Fp(\).) c(Lik) m(ewise,) f(w) m(e) h (can) g(m) m(ultiply) d(b) m(y) j(are) 0 4569 y(real,) 32 b(or) h(p) s(erform) e(other) i(arithmetic) e(op) s(erations) h(with) f (random) h(v) -5 b(ariables.) 31 b(W) -8 b(e) 34 b(w) m(on't) f(deal) f (with) f(v) -5 b(ariables) 0 4682 y(that) 28 b(can) f(assume) g(uncoun) m(tably) f(man) m(y) h(v) -5 b(alues.) 27 b(The) g(function) p Fm 26 w(F) p Fk 2317 4696 a(X) p Fp 2384 4682 a(\() p Fm(x) p Fp(\)) f(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(X) p Fp 33 w(=) p Fm 25 w(x) p Fp(]) f(=) p Ff 25 w(Pr) p Fp 1 w([) p Fl(f) p Fm 15 w(e) p Fj 3390 4605 a(\014) 3390 4659 y(\014) p Fm 3445 4682 a(X) p Fp 7 w(\() p Fm(e) p Fp(\)) i(=) p Fm 25 w(x) p Fl 15 w(g) p Fp 1 w(]) 0 4795 y(is) i(the) p Fi 31 w(pr) -5 b(ob) g(ability) 35 b(density) e (function) p Fp 31 w(of) p Fm 30 w(X) p Fp 38 w(and) d(describ) s(es) e (the) j(lik) m(eliho) s(o) s(d) c(of) k(hitting) e(a) h(particular) f (v) -5 b(alue.) 0 4947 y(The) 39 b(most) g(imp) s(ortan) m(t) f (concept) i(asso) s(ciated) g(with) d(random) i(v) -5 b(ariables) 37 b(is) i(the) g(a) m(v) m(erage) j(v) -5 b(alue,) 38 b(or) p Fi 39 w(exp) -5 b(e) g(cte) g(d) 0 5060 y(value) p Fp 30 w(\(sometimes) 31 b(also) g(called) e(the) p Fi 31 w(me) -5 b(an) p Fp(\).) 32 b(It) e(is) g(de\014ned) f(b) m(y) p Ff 1500 5262 a(E) p Fp([) p Fm(X) p Fp 7 w(]) e(=) p Fj 1809 5175 a(X) p Fk 1811 5372 a(e) p Fg(2) p Fk(S) p Ff 1955 5262 a(Pr) p Fp 2 w([) p Fm(e) p Fp(]) p Fl 21 w(\001) p Fm 20 w(X) p Fp 7 w(\() p Fm(e) p Fp(\)) p 90 rotate dyy eop %%Page: 4 4 4 3 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(4) p 0 -191 3900 4 v Fp 0 91 a(If) p Fm 39 w(X) p Fp 47 w(is) 38 b(clear) i(from) f(con) m(text) i(one) f(often) g(writes) p Fm 38 w(\026) p Fp 40 w(for) f(the) h(exp) s(ected) f(v) -5 b(alue.) 40 b(One) f(can) g(easily) g(sho) m(w) g(that) 0 204 y(exp) s(ectation) 31 b(is) e(linear) g(in) g(the) i(sense) f(that) p Ff 1379 373 a(E) p Fp([) p Fm(aX) p Fp 28 w(+) p Fm 20 w(bY) p Fp 20 w(]) 25 b(=) p Fm 25 w(a) p Ff(E) p Fp([) p Fm(X) p Fp 7 w(]) d(+) p Fm 20 w(b) p Ff(E) p Fp([) p Fm(Y) p Fp 20 w(]) 0 542 y(where) p Fm 30 w(a) p Fp 30 w(and) p Fm 30 w(b) p Fp 30 w(are) 31 b(real) f(constan) m(ts.) 0 772 y(Another) j(imp) s(ortan) m(t) g(consideration) f(is) g(the) h (spread) g(of) g(v) -5 b(alues) 33 b(of) g(the) g(random) g(v) -5 b(ariable) 32 b(around) g(its) h(mean.) 0 885 y(The) p Fi 30 w(varianc) -5 b(e) p Fp 31 w(of) p Fm 31 w(X) p Fp 38 w(is) 29 b(de\014ned) g(to) i(b) s(e) p Ff 1481 1053 a(V) p Fp 1 w([) p Fm(X) p Fp 7 w(]) c(=) p Ff 25 w(E) p Fp([\() p Fm(X) p Fl 28 w(\000) p Ff 20 w(E) p Fp([) p Fm(X) p Fp 7 w(]\)) p Fh 2327 1016 a(2) p Fp 2368 1053 a(]) p Fm(:) p Fp 0 1222 a(It) j(follo) m(ws) g(from) g (linearit) m(y) f(that) p Ff 1497 1335 a(V) p Fp 1 w([) p Fm(X) p Fp 7 w(]) d(=) p Ff 25 w(E) p Fp([) p Fm(X) p Fh 1974 1297 a(2) p Fp 2015 1335 a(]) p Fl 20 w(\000) p Ff 20 w(E) p Fp([) p Fm(X) p Fp 7 w(]) p Fh 2337 1297 a(2) p Fm 2378 1335 a(:) p Fp 0 1484 a(Since) f(v) -5 b(ariance) 27 b(measures) f(the) h(square) f(of) g(the) h(deviation) e (from) h(the) h(mean) f(one) h(often) g(also) f(uses) g(the) p Fi 27 w(standar) -5 b(d) 0 1597 y(deviation) p Fp 31 w(de\014ned) 30 b(to) h(b) s(e) p Fm 29 w(\033) p Fp 29 w(=) p Fj 1115 1519 a(p) p 1206 1519 195 4 v Ff 1206 1597 a(V) p Fp 1 w([) p Fm(X) p Fp 7 w(]) q(.) p Fr 0 1827 a(Example:) p Fp 29 w(Rolling) e(a) h(Die) 0 1979 y(Here) e(is) f(a) h(rather) f(to) s(o) h(fastidious) e(explanation) h (of) h(the) f(a) m(v) m(erage) k(v) -5 b(alue) 27 b(obtained) g(b) m(y) g(rolling) e(one) j(fair) f(die.) g(W) -8 b(e) 0 2092 y(can) 32 b(think) e(of) i(the) f(sample) g(as) p Fm 32 w(S) p Fp 32 w(=) p Fl 27 w(f) p Fp 1 w(one) p Fm(;) p Fp 15 w(t) m(w) m(o) p Fm 2 w(;) 15 b(:) g(:) g(:) h(;) p Fp 15 w(six) p Fl(g) p Fp 32 w(\(actually) -8 b(,) 32 b(an) g(six-elemen) m(t) f(set) h(will) d(do\).) j(Since) f(the) 0 2205 y(die) g(is) g(fair) g(w) m(e) i(ha) m(v) m(e) p Ff 33 w(Pr) p Fp 2 w([) p Fm(e) p Fp(]) c(=) e(1) p Fm(=) p Fp(6) 34 b(for) d(all) p Fm 31 w(e) p Fl 29 w(2) p Fm 28 w(S) p Fp 5 w(.) h(No) m(w) h(de\014ne) e(the) h(random) f(v) -5 b(ariable) p Fm 31 w(X) p Fp 40 w(to) 33 b(b) s(e) e(the) h(n) m(um) m (b) s(er) 0 2318 y(of) f(sp) s(ots.) f(Then) f(the) i(mean) f(is) p Ff 1116 2495 a(E) p Fp([) p Fm(X) p Fp 7 w(]) c(=) p Fj 1424 2409 a(X) p Fk 1427 2606 a(e) p Fg(2) p Fk(S) p Ff 1571 2495 a(Pr) p Fp 1 w([) p Fm(e) p Fp(]) p Fl 21 w(\001) p Fm 21 w(X) p Fp 7 w(\() p Fm(e) p Fp(\)) h(=) p Fj 2151 2409 a(X) p Fk 2136 2610 a(x) p Fg(2) p Fh([6]) p Fp 2313 2495 a(1) p Fm(=) p Fp(6) p Fm(x) p Fp 26 w(=) e(7) p Fm(=) p Fp(2) p Fm(:) p Fp 0 2763 a(F) -8 b(or) 31 b(the) g(v) -5 b(ariance) 30 b(w) m(e) h(ha) m(v) m(e) p Ff 1422 2876 a(E) p Fp([) p Fm(X) p Fh 1583 2838 a(2) p Fp 1624 2876 a(]) 25 b(=) p Fj 1785 2790 a(X) p Fk 1770 2991 a(x) p Fg(2) p Fh([6]) p Fp 1947 2876 a(1) p Fm(=) p Fp(6) p Fm(x) p Fh 2134 2838 a(2) p Fp 2200 2876 a(=) g(91) p Fm(=) p Fp(6) 0 3129 y(so) 31 b(that) p Ff 31 w(V) p Fp 1 w([) p Fm(X) p Fp 7 w(]) 26 b(=) f(35) p Fm(=) p Fp(12) 32 b(and) p Fm 30 w(\033) p Fl 28 w(\031) p Fp 25 w(1) p Fm(:) p Fp(71.) 0 3360 y(W) -8 b(e) 36 b(can) f(describ) s(e) f(the) h(lik) m(eliho) s(o) s(d) d(of) j(a) g(random) f(v) -5 b(ariable) 34 b(assuming) f(v) -5 b(alues) 35 b(far) f(a) m(w) m(a) m (y) j(from) e(the) g(mean) g(as) 0 3472 y(follo) m(ws.) p Fr 0 3667 a(Lemma) e(2.1) p Fc 46 w(Cheb) m(yshev's) c(Inequalit) m(y) p Ff 0 3819 a(Pr) p Fp 1 w([) p Fl(j) p Fm 1 w(X) p Fl 28 w(\000) p Fm 19 w(\026) p Fl(j) d(\025) p Fm 25 w(c) p Fp(]) p Fl 26 w(\024) p Fm 25 w(\033) p Fh 777 3786 a(2) p Fm 816 3819 a(=c) p Fh 900 3786 a(2) p Fc 940 3819 a(.) p Fp 0 4029 a(Another) k(useful) f(b) s(ound) f(\(in) i(particular) e (for) i(rep) s(eated) h(trials\)) e(is) h(the) g(follo) m(wing.) p Fr 0 4224 a(Lemma) j(2.2) p Fc 46 w(Mark) m(o) m(v's) f(Inequalit) m(y) 0 4376 y(Let) p Fm 31 w(X) p Fc 38 w(b) s(e) d(a) i(random) f(v) -5 b(ariable) 29 b(assuming) g(p) s(ositiv) m(e) g(in) m(teger) i(v) -5 b(alues.) 30 b(Then) p Ff 29 w(Pr) p Fp 2 w([) p Fm(X) p Fl 33 w(\025) p Fm 25 w(k) s(\026) p Fp(]) p Fl 25 w(\024) p Fp 25 w(1) p Fm(=k) p Fc 3 w(.) p Fn 0 4653 a(2.4) 112 b(Conditional) 36 b(Probabilit) m(y) f(and) j(Indep) s(endence) p Fp 0 4863 a(P) m(artial) h(kno) m(wledge) h(of) g(the) g(outcome) h(of) f(an) g(exp) s(erimen) m(t) f(ma) m(y) h(a\013ect) i(the) e(probabilit) m(y) d(of) j(an) g(ev) m(en) m(t.) h(F) -8 b(or) 0 4976 y(example,) 28 b(if) e(w) m(e) i(roll) e(a) i(die) f(and) g(the) h (result) f(is) f(ev) m(en,) j(the) f(probabilit) m(y) d(of) j(getting) g (a) g(4) g(is) f(1) p Fm(=) p Fp(3) i(rather) e(than) h(1) p Fm(=) p Fp(6) 0 5089 y(in) h(the) i(general) f(case.) i(This) c(leads) i (to) h(the) g(notion) f(of) p Fi 30 w(c) -5 b(onditional) 35 b(pr) -5 b(ob) g(ability) p Fp(:) p Ff 1481 5301 a(Pr) p Fp 1 w([) p Fm 15 w(A) p Fl 26 w(j) p Fm 25 w(B) p Fp 20 w(]) 26 b(=) p Ff 2001 5239 a(Pr) p Fp 1 w([) p Fm(A) p Fl 21 w(\\) p Fm 19 w(B) p Fp 5 w(]) p 2001 5280 384 4 v Ff 2085 5363 a(Pr) p Fp 2 w([) p Fm(B) p Fp 5 w(]) p Fm 2394 5301 a(:) p 90 rotate dyy eop %%Page: 5 5 5 4 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(5) p 0 -191 3900 4 v Fp 0 91 a(Tw) m(o) 29 b(ev) m(en) m(ts) p Fm 31 w(A) p Fp 29 w(and) p Fm 29 w(B) p Fp 33 w(are) p Fi 30 w(indep) -5 b(endent) p Fp 30 w(if) 28 b(no) h(additional) e (information) h(can) h(b) s(e) g(obtained) f(from) h(one) g(ab) s(out) 0 204 y(the) i(other:) p Ff 1440 317 a(Pr) p Fp 2 w([) p Fm(A) p Fl 20 w(\\) p Fm 20 w(B) p Fp 5 w(]) 25 b(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(A) p Fp(]) p Fl 20 w(\001) p Ff 21 w(Pr) p Fp 1 w([) p Fm(B) p Fp 5 w(]) p Fm(:) p Fp 0 476 a(Note) 32 b(that) f(in) e(this) g(case) p Ff 1578 588 a(Pr) p Fp 1 w([) p Fm 15 w(A) p Fl 26 w(j) p Fm 26 w(B) p Fp 19 w(]) d(=) p Ff 25 w(Pr) p Fp 1 w([) p Fm(A) p Fp(]) p Fm(:) p Fr 0 792 a(Lemma) 33 b(2.3) p Fc 46 w(Ba) m(y) m(es') f(Theorem) p Ff 0 945 a(Pr) p Fp 1 w([) p Fm(A) p Fp(]) p Ff 15 w(Pr) p Fp 3 w([) p Fm 15 w(B) p Fl 30 w(j) p Fm 25 w(A) p Fp 15 w(]) 26 b(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(B) p Fp 5 w(]) p Ff 15 w(Pr) p Fp 1 w([) p Fm 15 w(A) p Fl 26 w(j) p Fm 25 w(B) p Fp 20 w(]) p Fc(.) p Fp 0 1159 a(Lik) m(ewise,) k(t) m(w) m (o) h(random) f(v) -5 b(ariables) 29 b(are) p Fi 31 w(indep) -5 b(endent) p Fp 32 w(if) p Ff 29 w(Pr) p Fp 1 w([) p Fm(X) p Fp 33 w(=) p Fm 25 w(x;) 15 b(Y) p Fp 46 w(=) p Fm 25 w(y) p Fp 3 w(]) 25 b(=) p Ff 25 w(Pr) p Fp 2 w([) p Fm(X) p Fp 33 w(=) p Fm 24 w(x) p Fp(]) p Fl 21 w(\001) p Ff 20 w(Pr) p Fp 2 w([) p Fm(Y) p Fp 45 w(=) p Fm 25 w(y) p Fp 3 w(].) p Fr 0 1363 a(Lemma) 33 b(2.4) p Fc 46 w(F) -8 b(or) 31 b(indep) s(enden) m(t) d(random) i(v) -5 b(ariables) 29 b(w) m(e) h(ha) m(v) m(e) p Ff 32 w(E) p Fp([) p Fm(X) 7 b(Y) p Fp 21 w(]) 26 b(=) p Ff 25 w(E) p Fp([) p Fm(X) p Fp 7 w(]) p Fl 21 w(\001) p Ff 20 w(E) p Fp([) p Fm(Y) p Fp 21 w(]) p Fc(.) p Fn 0 1643 a(2.5) 112 b(Bernoulli) 35 b(T) -9 b(rials) p Fp 0 1853 a(One) 21 b(imp) s(ortan) m(t) f(t) m(yp) s(e) i(of) g(exp) s(erimen) m(t) e(is) h (a) g(rep) s(etition) f(of) i(some) g(basic) e(exp) s(erimen) m(t.) h (The) g(individual) c(outcomes) 0 1966 y(are) 26 b(assumed) g(to) g(b) s (e) f(indep) s(enden) m(t) f(of) i(eac) m(h) h(other.) g(W) -8 b(e) 27 b(can) f(then) g(ask) g(ho) m(w) g(man) m(y) g(times) f(an) h (ev) m(en) m(t) h(asso) s(ciated) 0 2079 y(with) g(the) i(F) -8 b(or) 29 b(example,) f(supp) s(ose) f(w) m(e) i(\015ip) e(a) i(coin) p Fm 28 w(n) p Fp 27 w(times) f(and) g(observ) m(e) p Fm 29 w(X) p Fp 7 w(,) h(the) g(n) m(um) m(b) s(er) e(of) i(heads.) f(W) -8 b(e) 30 b(can) 0 2192 y(de\014ne) c(an) p Fi 26 w(indic) -5 b(ator) 31 b(variable) p Fm 28 w(X) p Fk 1172 2206 a(i) p Fp 1227 2192 a(that) c(is) f(1) h(if) e(the) p Fm 27 w(i) p Fp(th) i(rep) s(etition) e(pro) s(duces) g(heads,) i(and) f(0) h (otherwise.) f(Then) p Fm 0 2305 a(X) p Fp 33 w(=) p Fm 25 w(X) p Fh 279 2319 a(1) p Fp 339 2305 a(+) p Fm 20 w(X) p Fh 505 2319 a(2) p Fp 564 2305 a(+) p Fm 20 w(:) 15 b(:) g(:) p Fp 22 w(+) p Fm 20 w(X) p Fk 948 2319 a(n) p Fp 995 2305 a(.) 30 b(If) g(the) h(coin) f(has) g(bias) p Fm 29 w(p) p Fp 30 w(then) p Ff 1347 2537 a(Pr) p Fp 1 w([) p Fm(X) p Fp 33 w(=) p Fm 25 w(k) p Fp 3 w(]) c(=) p Fj 1863 2409 a(\022) p Fm 1930 2476 a(n) 1932 2600 y(k) p Fj 1984 2409 a(\023) p Fm 2051 2537 a(p) p Fk 2097 2500 a(k) p Fp 2140 2537 a(\(1) p Fl 21 w(\000) p Fm 20 w(p) p Fp(\)) p Fk 2413 2500 a(n) p Fg(\000) p Fk(k) p Fp 0 2777 a(as) 31 b(a) f(simple) f(coun) m(ting) h(argumen) m(t) h(sho) m (ws.) f(One) g(can) h(easily) e(c) m(hec) m(k) j(that) p Fj 2586 2709 a(P) p Fk 2682 2735 a(n) 2682 2804 y(k) p Fh 2 w(=0) p Ff 2830 2777 a(Pr) p Fp 1 w([) p Fm(X) p Fp 33 w(=) p Fm 25 w(k) p Fp 4 w(]) 25 b(=) g(1.) p Fm 0 2929 a(X) p Fp 38 w(is) k(said) h(to) h(b) s(e) p Fi 29 w(binomial) 5 b(ly) p Fp 32 w(distributed.) 28 b(W) -8 b(e) 31 b(ha) m(v) m(e) p Ff 1412 3116 a(E) p Fp([) p Fm(X) p Fp 7 w(]) 26 b(=) p Fm 25 w(np) p Ff 182 w(V) p Fp 1 w([) p Fm(X) p Fp 7 w(]) g(=) p Fm 25 w(npq) s(:) p Fp 0 3342 a(If) d(w) m(e) h(coun) m(t) g(the) f(n) m(um) m(b) s(er) f (of) i(times) f(till) e(heads) i(app) s(ear) g(w) m(e) h(get) g(a) g (random) e(v) -5 b(ariable) p Fm 23 w(Y) p Fp 43 w(suc) m(h) 23 b(that) p Ff 24 w(Pr) p Fp 1 w([) p Fm(Y) p Fp 46 w(=) p Fm 25 w(k) p Fp 3 w(]) i(=) p Fm 0 3455 a(p) p Fp(\(1) p Fl 21 w(\000) p Fm 20 w(p) p Fp(\)) p Fk 319 3422 a(k) p Fg 2 w(\000) p Fh(1) p Fp 482 3455 a(for) p Fm 30 w(k) p Fl 28 w(\025) p Fp 25 w(1.) 31 b(In) f(this) f(case) j(w) m(e) f(sp) s (eak) f(of) g(a) p Fi 31 w(ge) -5 b(ometric) p Fp 31 w(distribution) 27 b(and) j(ha) m(v) m(e) p Ff 1388 3643 a(E) p Fp([) p Fm(Y) p Fp 21 w(]) 25 b(=) g(1) p Fm(=p) p Ff 183 w(V) p Fp 1 w([) p Fm(Y) p Fp 20 w(]) g(=) p Fm 25 w(q) s(=p) p Fh 2447 3605 a(2) p Fm 2487 3643 a(:) p Fo 0 3966 a(3) 135 b(Quic) l(ksort) p Fp 0 4208 a(Divide-and-conquer) 29 b(approac) m(h:) p Fl 136 4420 a(\017) p Fp 46 w(partition) g (\(costly\)) p Fl 136 4602 a(\017) p Fp 46 w(recursiv) m(ely) g(sort) p Fl 136 4784 a(\017) p Fp 46 w(join) h(\(trivial,) f(do) h(nothing\)) 0 4997 y(P) m(artion) h(is) e(linear) h(time,) g(but) g(the) h(length) f (of) h(the) g(resulting) e(subarra) m(ys) h(dep) s(ends) f(crucially) g (on) h(the) h(c) m(hoice) h(of) 0 5110 y(the) f(piv) m(ot) f(elemen) m (t.) 0 5340 y(Compare) g(this) f(to) j(Mergesort:) p 90 rotate dyy eop %%Page: 6 6 6 5 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(6) p 0 -191 3900 4 v Fl 136 91 a(\017) p Fp 46 w(split) 29 b(\(trivial\)) p Fl 136 279 a(\017) p Fp 46 w(recursiv) m(ely) g(sort) p Fl 136 467 a(\017) p Fp 46 w(merge) i(\(costly\)) 0 693 y(Length) 37 b(of) g(the) g(subarra) m(ys) g(is) f(alw) m(a) m(ys) p Fm 37 w(n=) p Fp(2,) i(and) f(the) g(merge) g(pro) s(cess) g(is) f (linear) g(time.) h(Hence) g(the) h(running) 0 806 y(time) 30 b(is) g(of) g(the) h(form) p Fm 30 w(T) p Fh 827 820 a(MS) p Fp 950 806 a(\() p Fm 1 w(n) p Fp(\)) 25 b(=) g(2) p Fm(T) p Fh 1295 820 a(MS) p Fp 1419 806 a(\() p Fm(n=) p Fp(2) q(\)) 20 b(+) p Fm 20 w(c) p Fl 21 w(\001) p Fm 20 w(n) p Fp(,) 31 b(and) e(it) h(is) g(not) h(hard) e(to) i(see) g (that) h(this) d(recurrence) h(has) 0 919 y(solution) p Fm 29 w(T) p Fh 397 933 a(MS) p Fp 520 919 a(\() p Fm 1 w(n) p Fp(\)) 25 b(=) g(\002\() p Fm(n) p Fp 15 w(log) p Fm 16 w(n) p Fp(\).) 0 1071 y(As) 45 b(w) m(e) g(will) d(see,) j(Quic) m (ksort) f(has) h(w) m(orst) g(case) g(b) s(eha) m(vior) f(\002\() p Fm(n) p Fh 2288 1038 a(2) p Fp 2327 1071 a(\),) h(but) f(on) h(a) m(v) m (erage) i(the) e(running) d(time) i(is) 0 1184 y(\002\() p Fm(n) p Fp 15 w(log) p Fm 16 w(n) p Fp(\).) 29 b(In) e(order) h(to) h (get) g(a) g(comp) s(etitiv) m(e) f(algorithm) g(w) m(e) g(need) g(to) h (b) s(eat) g(the) f(constan) m(ts) i(in) d(Mergesort.) i(T) -8 b(o) 0 1297 y(this) 33 b(end) g(w) m(e) h(will) d(insist) g(that) j (selection) g(of) g(the) g(piv) m(ot) f(is) p Fi 33 w(O) p Fp 9 w(\(1\);) h(needless) f(to) h(sa) m(y) g(there) g(is) f(nothing) g (w) m(e) h(can) 0 1410 y(do) i(ab) s(out) g(\002\() p Fm(n) p Fp(\)) g(for) g(partitioning.) e(The) h(reason) i(this) e(migh) m(t) g(w) m(ell) g(b) s(e) h(p) s(ossible) d(is) j(that) g(in) f (Mergesort,) j(the) 0 1523 y(t) m(ypical) 30 b(comparison) g(is) p Ff 121 1636 a(a[i]) p Fm 30 w(<) p Ff 30 w(a[j]) p Fp 0 1788 a(but) g(in) f(Quic) m(ksort) h(it) g(is) p Ff 121 1901 a(a[i]) p Fm 30 w(<) p Ff 30 w(p) p Fp 0 2053 a(so) h(the) f(piv) m(ot) p Fm 31 w(p) p Fp 30 w(can) g(b) s(e) g(k) m (ept) h(in) e(a) i(fast) g(register.) 0 2205 y(Also) 22 b(note) h(that) g(Mergesort) h(requires) d(more) i(memory:) f(2) p Fm(n) p Fp 4 w(+) t(\002\(lg) p Fm 17 w(n) p Fp(\)) g(in) g(the) g (usual) f(recursiv) m(e) h(implemen) m(tation.) p Fn 0 2487 a(3.1) 112 b(Piv) m(ot) 36 b(Selection) p Fp 0 2698 a(Crucial) 28 b(problem:) h(ho) m(w) i(to) g(c) m(ho) s(ose) g (the) g(piv) m(ot.) 0 2850 y(Problem:) d(if) f(the) i(piv) m(ot) f(is) g (alw) m(a) m(ys) h(the) g(largest) g(\(or) f(smallest\)) g(elemen) m(t) h(w) m(e) g(get) h(quadratic) e(running) e(time:) i(w) m(e) 0 2963 y(only) k(split) f(o\013) j(a) f(single) e(elemen) m(t) j(at) g (eac) m(h) g(step,) f(so) g(the) g(recursion) f(has) g(depth) p Fm 32 w(n) p Fp 33 w(and) g(the) h(amoun) m(t) h(of) f(w) m(ork) 0 3076 y(at) e(lev) m(el) p Fm 30 w(i) p Fp 31 w(is) e(\002\() p Fm(n) p Fl 20 w(\000) p Fm 20 w(i) p Fp(\).) 0 3267 y(Ideally) 23 b(w) m(e) i(w) m(ould) e(lik) m(e) h(to) h(c) m(ho) s(ose) h(the) e (median) g(as) h(the) f(piv) m(ot,) h(but) f(it) g(tak) m(es) i(w) m(a) m(y) f(to) s(o) g(m) m(uc) m(h) g(w) m(ork) f(to) i(compute) 0 3380 y(the) 31 b(median) e(\(though) h(it) g(can) h(b) s(e) e(done) i (in) e(linear) g(time\).) 0 3532 y(Giv) m(en) h(a) h(subarra) m(y) f (of) g(the) h(form) p Fb 30 w(a[l..r]) p Fp 28 w(the) g(piv) m(ot) f (is) f(t) m(ypically) h(c) m(hosen) h(as) p Fl 136 3759 a(\017) p Fp 46 w(sp) s(ecial) e(p) s(osition:) p Fm 29 w(a) p Fk 943 3774 a(l) p Fp 969 3759 a(,) p Fm 31 w(a) p Fk 1073 3773 a(r) p Fp 1111 3759 a(,) p Fm 30 w(a) p Fh 1214 3777 a(\() p Fk(l) p Fh 1 w(+) p Fk(r) p Fh 2 w(\)) p Fk(=) p Fh(2) p Fp 1454 3759 a(,) p Fl 136 3947 a(\017) p Fp 46 w(the) i(median) e(of) i(a) f(small) f(sample) h (of) g(elemen) m(ts,) h(sa) m(y) -8 b(,) p Fm 32 w(a) p Fk 2146 3962 a(l) p Fp 2172 3947 a(,) p Fm 31 w(a) p Fh 2276 3965 a(\() p Fk(l) p Fh 1 w(+) p Fk(r) p Fh 2 w(\)) p Fk(=) p Fh(2) p Fp 2546 3947 a(and) p Fm 30 w(a) p Fk 2771 3961 a(r) p Fp 2809 3947 a(,) p Fl 136 4134 a(\017) p Fp 46 w(at) 31 b(random,) f(median) f(of) i(a) g(small) e(random) g (sample.) 0 4361 y(Note) i(that) f(randomized) e(Quic) m(ksort) h (requires) f(a) i(random) f(n) m(um) m(b) s(er) f(generator,) j(w) m(e) f(will) d(simply) g(assume) i(that) 0 4474 y(a) i(c) m(heap) g(source) f (of) h(randomness) e(is) h(a) m(v) -5 b(ailable.) p Fo 0 4799 a(4) 135 b(Analysis) p Fp 0 5042 a(In) 39 b(most) h (probabilistic) c(argumen) m(ts) k(it) f(helps) g(greatly) h(to) g(mak) m(e) h(sev) m(eral) f(simplifying) 35 b(assumptions) j(ab) s(out) 0 5154 y(the) f(algorithm) f(in) g(question.) h(As) g(long) f(as) i(our) e (assumptions) g(do) h(not) g(decrease) h(the) f(running) d(time) j (that) h(is) 0 5267 y(p) s(erfectly) 30 b(acceptable.) p 90 rotate dyy eop %%Page: 7 7 7 6 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(7) p 0 -191 3900 4 v Fp 0 91 a(F) -8 b(or) 34 b(example,) g(w) m(e) g (ma) m(y) g(supp) s(ose) e(that) i(w) m(e) g(only) e(sort) i(p) s(erm) m (utations) f(of) g([) p Fm(n) p Fp(]:) h(the) g(absence) g(of) f (duplicates) f(in) 0 204 y(the) 37 b(input) e(arra) m(y) j(can) f(only) f(slo) m(w) h(do) m(wn) f(the) h(algorithm) f(\(w) m(e) i(could) e (eliminate) f(all) h(elemen) m(ts) i(equal) e(to) i(the) 0 317 y(piv) m(ot,) 31 b(not) f(just) g(the) h(piv) m(ot) f(itself) 7 b(\).) 30 b(W) -8 b(e) 31 b(assume) f(uniform) f(distribution) d(of) 31 b(the) f(input) f(p) s(erm) m(utations.) 0 469 y(F) -8 b(or) 31 b(de\014niteness,) d(w) m(e) j(assume) f(the) g(left) g (subarra) m(y) f(con) m(tains) h(all) f(elemen) m(ts) p Fm 30 w(<) c(p) p Fp(,) 30 b(the) g(righ) m(t) g(all) f(elemen) m(ts) p Fm 30 w(>) c(p) p Fp(.) 0 582 y(\(Sometimes) g(it) f(ma) m(y) h(also) g (b) s(e) f(useful) e(to) k(assume) e(that) h(the) g(piv) m(ot) g(is) e (still) g(con) m(tained) i(in) e(one) i(of) g(the) f(t) m(w) m(o) i (arra) m(ys;) 0 695 y(again,) 31 b(this) e(assumption) g(could) g(only) h(slo) m(w) g(do) m(wn) g(the) g(algorithm.\)) 0 886 y(Let) p Fm 31 w(X) p Fk 238 900 a(n) p Fp 315 886 a(b) s(e) g(the) h (random) e(v) -5 b(ariable:) 30 b(size) g(of) h(the) f(arra) m(y) h(in) e(the) i(\\left") g(subarra) m(y) -8 b(.) 30 b(Set) p Fm 1632 1090 a(p) p Fk 1678 1104 a(i) p Fp 1731 1090 a(=) p Ff 25 w(Pr) p Fp 1 w([) p Fm(X) p Fk 2017 1104 a(n) p Fp 2090 1090 a(=) p Fm 25 w(i) p Fp 1 w(]) p Fm(:) p Fp 0 1295 a(where) p Fm 30 w(i) p Fp 25 w(=) 25 b(0) p Fm(;) 15 b(:) g(:) g(:) i(;) e(n) p Fl 21 w(\000) p Fp 20 w(1) g(.) 30 b(Then) p Ff 1617 1416 a(E) p Fp([) p Fm(X) p Fk 1771 1430 a(n) p Fp 1819 1416 a(]) c(=) p Fj 1965 1330 a(X) p Fk 1970 1525 a(i<n) 0="" 4="" 7="" 8="" 10="" 15="" 18="" 19="" 20="" 21="" 25="" 26="" 28="" 29="" 30="" 31="" 32="" 33="" 34="" 35="" 36="" 37="" 40="" 41="" 42="" 46="" 90="" 91="" 106="" 112="" 113="" 114="" 136="" 157="" 204="" 212="" 336="" 363="" 424="" 449="" 472="" 558="" 559="" 576="" 618="" 643="" 666="" 691="" 705="" 714="" 739="" 828="" 853="" 855="" 973="" 1084="" 1087="" 1108="" 1123="" 1184="" 1210="" 1217="" 1243="" 1290="" 1303="" 1313="" 1316="" 1363="" 1364="" 1374="" 1416="" 1427="" 1430="" 1431="" 1454="" 1473="" 1482="" 1487="" 1500="" 1506="" 1509="" 1521="" 1527="" 1528="" 1529="" 1533="" 1550="" 1574="" 1583="" 1588="" 1611="" 1618="" 1629="" 1669="" 1683="" 1688="" 1730="" 1774="" 1782="" 1788="" 1793="" 1796="" 1797="" 1808="" 1815="" 1830="" 1831="" 1856="" 1893="" 1901="" 1912="" 1915="" 1935="" 1983="" 1986="" 1990="" 2012="" 2028="" 2034="" 2040="" 2043="" 2070="" 2089="" 2096="" 2099="" 2110="" 2111="" 2112="" 2123="" 2236="" 2241="" 2255="" 2264="" 2279="" 2296="" 2297="" 2302="" 2342="" 2350="" 2373="" 2377="" 2386="" 2392="" 2393="" 2402="" 2410="" 2488="" 2558="" 2559="" 2571="" 2584="" 2598="" 2608="" 2621="" 2697="" 2738="" 2774="" 2781="" 2807="" 2833="" 2849="" 2863="" 2876="" 2982="" 3001="" 3007="" 3031="" 3047="" 3068="" 3127="" 3131="" 3140="" 3174="" 3178="" 3214="" 3323="" 3378="" 3441="" 3465="" 3574="" 3636="" 3652="" 3659="" 3775="" 3804="" 3900="" 3917="" 3956="" 3966="" 4004="" 4113="" 4168="" 4178="" 4217="" 4255="" 4363="" 4364="" 4497="" 4549="" 4726="" 4932="" 4972="" 4993="" 5056="" p="" fm="" a(i)="" fl="" w(\001)="" w(p)="" fk="" fp="" a(whic)="" m(h)="" b(hop)="" s(efully)="" f(will)="" f(b)="" s(e)="" j(close)="" h="" (to)="" w(n=")" fp(2.)="" g(no)="" m(w)="" g(let)="" w(t)="" fp(\()="" fm(n)="" fp(\))="" g(b)="" e(the)="" i(a)="" m(v)="" m(erage)="" i="" (running)="" b(time)="" i(of)="" g(quic)="" m(ksort)="" g(on)="" h(a)="" y(p)="" s(erm)="" m(utation)="" b(of)="" i(length)="" f([)="" fp(].)="" g(then)="" a(t)="" c(=")" fj="" a(\032)="" a(c)="" w(if)="" w(n)="" w(\024)="" w(1,)="" a(p)="" a(i<n)="" a(\()="" fm(t)="" fm(i)="" c(+)="" w(\000)="" w(i)="" w(1\)\))="" f(+)="" w(cn)="" w(otherwise.)="" fn="" a(4.1)="" b(brute)="" b(f)="" -9="" b(orce)="" a(since)="" b(the)="" h(piv)="" m(ot)="" g(is)="" f(c)="" m="" (hosen)="" h(at)="" h(random,)="" a(=")" b(1)="" fm(="n)" w(where)="" w(=")" g(0)="" fm(;)="" b(:)="" g(:)="" i(;)="" e(n)="" w(1)="" b(\(the)="" b(left)="" g(\\buc)="" m(k)="" m(et")="" (consists)="" f(of)="" y(elemen)="" m(ts)="" h(strictly)="" e(less)="" h(than)="" g="" (the)="" g(piv)="" m(ot\).)="" y(hence)="" ff="" w(e)="" fp([)="" fm(x)="" a(n)="" a(])="" a(i="n)" f(\()="" w(1\))="" fp(2,)="" b(whic)="" d(lo)="" s(oks)="" h(promising.)="" y(t)="" -8="" b(o)="" b(determine)="" i(exp)="" s(ected)="" g(running)="" c="" (time)="" j(w)="" m(e)="" h(compute)="" b(=")" f(1)="" a(x)="" a(\000)="" a(\001)="" a(+)="" k(2)="" a(and)="" b(th)="" m(us)="" f(2)="" fh="" a(2)="" w(+)="" f(1\))="" g(1\))="" fg(\024)="" fk(n)="" w(c)="" b(2\))="" g(+)="" fp(\(2)="" y(whic)="" b(comes)="" i(do)="" m(wn)="" f(to)="" h(\(really)="" v="" h(+)="" w(d:)="" rotate="" dyy="" eop="" %%page:="" bop="" fr="" -228="" a(15-451)="" b(lec.)="" b(3)="" b(8)="" -191="" a(the)="" b(homogeneous)="" h(solution)="" e="" (for)="" h(the)="" h(last)="" f(equation)="" g(easy:)="" w(h)="" b(1.)="" b(but)="" f(the)="" g(solution)="" f(lo)="" y(lik)="" a(h)="" a(d="h)" e(=")" w(d)="" b(1\))="" fh(="1)" a(1)="" fm(h)="" a(4.2)="" b(digression:)="" b(solving)="" h(recurrence)="" a(it)="" b(is)="" g(helpful)="" d(to)="" b(generalize)="" e(a)="" h(bit)="" e(and)="" h(try)="" g(to)="" h(tac)="" m(kle)="" h(recurrences)="" e(of)="" g(the)="" h(form)="" a(a)="" w(f)="" w(\()="" b(otherwise.)="" y(this)="" b(w)="" m(ould)="" h(easy)="" h(except)="" h(for)="" w(a)="" h(term.)="" f(there)="" h(an)="" m(y)="" g(w)="" m(a)="" h(to)="" f(eliminate)="" e(this)="" h(term?)="" g(tric)="" (is)="" y(to)="" h(consider)="" i(corresp)="" s(onding)="" d="" (homogeneous)="" j(equation)="" b(if)="" y(supp)="" s(ose)="" j(someho)="" f(ha)="" (v)="" h(found)="" w(for)="" i(homogeneous)="" f(equation.)="" h(set)="" fg="" a(0)="" i(=")" b(and)="" fp(\).)="" b(then)="" d(b)="" h(dividing)="" k(original)="" d(equation)="" j(b)="" g(get)="" y(and)="" h(simply)="" d(unroll)="" f(this)="" j="" (in)="" m(to)="" g(a)="" h(sum)="" a(f)="" b(substituting)="" c(bac)="" h(=")" a(:)="" a(4.3)="" b(indicator)="" b(v)="" b(ariables)="" i(linearit)="" g(exp)="" s(ectation)="" b(\(b)="" s(oring\))="" g(game)="" y(pic)="" g(t)="" m(o)="" i(p)="" s(ositiv)="" d(in)="" m(tegers)="" w(b)="" fp(.)="" y(generate)="" j(a)="" f(random)="" e(in)="" m(teger)="" w(2)="" w([)="" fm(b)="" a(\017)="" w(y)="" m(ou)="" i(win.)="" b(<)="" b(lose.)="">) g(a) p Fp 30 w(pla) m(y) 30 b(again) h(with) e(\() p Fm(a;) 15 b(p) p Fl 21 w(\000) p Fp 20 w(1\).) 0 4771 y(What) 31 b(is) e(the) i(probabilit) m(y) p Fm 28 w(p) p Fp(\() p Fm(a;) 15 b(b) p Fp(\)) 31 b(of) g(winning?) 0 4923 y(Clearly) p Fm 29 w(p) p Fp(\(1) p Fm(;) 15 b(b) p Fp(\)) 26 b(=) f(1) 31 b(and) p Fm 30 w(p) p Fp(\() p Fm(a;) 15 b(a) p Fp(\)) 26 b(=) f(1) p Fm(=a) p Fp(.) p Fc 0 5075 a(Claim:) p Fp 120 w(Alw) m(a) m(ys) p Fm 30 w(p) p Fp(\() p Fm(a;) 15 b(b) p Fp(\)) 27 b(=) e(1) p Fm(=a) p Fp(.) p Fc 0 5227 a(Pro) s(of.) p Fp 91 w(Arguing) 36 b(inductiv) m(ely) -8 b(,) 35 b(the) j(probabilit) m(y) c(of) k (winning) c(is) i(1) p Fm(=b) p Fp 26 w(+) 24 b(\() p Fm(b) p Fl 25 w(\000) p Fm 25 w(a) p Fp(\)) p Fm(=b) p Fl 25 w(\001) p Fp 25 w(1) p Fm(=a) p Fp 38 w(=) 36 b(1) p Fm(=a) p Fp(.) i(The) f(\014rst) 0 5340 y(term) 30 b(comes) i(from) e (hitting) p Fm 28 w(a) p Fp(,) h(the) g(second) f(from) g(hitting) f (the) i(\\pla) m(y) f(again") h(region.) p Fa 3832 5344 a(2) p 90 rotate dyy eop %%Page: 9 9 9 8 bop Fr 0 -228 a(15-451) 106 b(Lec.) 35 b(3) 3174 b(9) p 0 -191 3900 4 v Fp 0 91 a(The) 28 b(k) m(ey) i(idea) e(for) g (the) h(analysis) e(is) h(to) h(asso) s(ciate) h(the) f(total) g(cost) h (of) f(Quic) m(ksort) f(with) f(the) i(n) m(um) m(b) s(er) e(of) i (compa-) 0 204 y(risons) g(made:) i(the) g(only) e(non-recursiv) m(e) h (w) m(ork) h(part) f(is) g(partition,) f(and) h(the) h(n) m(um) m(b) s (er) e(of) i(steps) f(in) g(partition) f(is) 0 317 y(prop) s(ortional) e (to) j(the) g(n) m(um) m(b) s(er) e(of) h(comparisons) g(made) g(\(no) g (elemen) m(t) h(is) f(mo) m(v) m(ed) h(without) e(comparison) h(to) h (the) 0 430 y(piv) m(ot\).) 0 582 y(Supp) s(ose) f(w) m(e) h(quic) m (ksort) h(a) f(p) s(erm) m(utation) g(of) g([) p Fm(n) p Fp(].) 0 734 y(Let) p Fm 31 w(X) p Fk 238 748 a(ij) p Fp 329 734 a(b) s(e) g(an) g(indicator) f(v) -5 b(ariable) p Fm 1219 1019 a(X) p Fk 1294 1033 a(ij) p Fp 1380 1019 a(=) p Fj 1476 864 a(\() p Fp 1549 956 a(1) 122 b(if) p Fm 29 w(i) p Fp 31 w(and) p Fm 29 w(j) p Fp 36 w(are) 31 b(compared,) 1549 1092 y(0) 122 b(otherwise.) 0 1296 y(Here) 31 b(1) p Fl 26 w(\024) p Fm 25 w(i) 25 b(<) g(j) p Fl 31 w(\024) p Fm 25 w(n) p Fp 30 w(so) 30 b(w) m(e) h(don't) g(coun) m (t) g(double.) 0 1448 y(Then) e(the) i(exp) s(ected) g(n) m(um) m(b) s (er) e(of) h(comparisons) g(is) p Fm 1707 1661 a(X) p Fp 33 w(=) p Fj 1911 1574 a(X) p Fk 1921 1770 a(i</n)>/tvz@princeton.edu