(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: hw5.dvi %%Pages: 2 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f hw5.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2006.04.03:1659 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (hw5.dvi) @start %DVIPSBitmapFont: Fa cmmi10 10 9 /Fa 9 117 df11 D71 D<0103B5D8F803B512F8495D A290260007F8C73807F8004B5DA2020F150F615DA2021F151F615DA2023F153F615DA202 7F157F96C7FC92C8FCA24A5D605CA249B7FC60A202FCC7120101031503605CA201071507 605CA2010F150F605CA2011F151F605CA2013F153F605CA2017F157F95C8FC91C8FC496C 4A7EB690B6FCA345397DB845>I<0103B6FC5B5E90260007FCC8FC5D5D140FA25DA2141F A25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA2130718404A15C0 A2010F150118804A1403A2011F16005F4A1406170E013F151E171C4A143C177C017F5D16 0391C7120F49EC7FF0B8FCA25F32397DB839>76 D<0103B612F849EDFF8018E0903B0007 F8001FF84BEB03FCEF00FE020F157FA24BEC3F80A2021F16C0A25DA2143FF07F805DA202 7FEDFF006092C7485A4D5A4A4A5A4D5A4AEC1F80057FC7FC0101EC07F891B612E094C8FC 9139FC000FC00103EC03F0707E4A6D7E831307177E5C177F010F5D5F5CA2011F1401A25C A2133F16034A4A1360A2017F17E019C091C71401496C01011480B61503933900FE0700EF 7E0ECAEA1FFCEF07F03B3B7DB83F>82 D109 DI<14 FF010313C090380F80F090383E00380178131C153C4913FC0001130113E0A33903F000F0 6D13007F3801FFE014FC14FF6C14806D13C0011F13E013039038003FF014071403001E13 01127FA24814E0A348EB03C012F800E0EB07800070EB0F006C133E001E13F83807FFE000 0190C7FC1E267CA427>115 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmbx12 14.4 17 /Fb 17 117 df<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7 FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI<171F 4D7E4D7EA24D7EA34C7FA24C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C 7E03018116F8830303814C7E03078116E083030F814C7E031F81168083033F8293C77E4B 82157E8403FE824B800201835D840203834B800207835D844AB87EA24A83A3DA3F80C880 92C97E4A84A2027E8202FE844A82010185A24A820103854A82010785A24A82010F855C01 1F717FEBFFFCB600F8020FB712E0A55B547BD366>65 DI<932601FFFCEC01C0047FD9FFC013030307B600F81307033F 03FE131F92B8EA803F0203DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A0180 0203B5FC494848C9FC4901F8824949824949824949824949824990CA7E494883A2484983 485B1B7F485B481A3FA24849181FA3485B1B0FA25AA298C7FC5CA2B5FCAE7EA280A2F307 C07EA36C7FA21B0F6C6D1980A26C1A1F6C7F1C006C6D606C6D187EA26D6C606D6D4C5A6D 6D16036D6D4C5A6D6D4C5A6D01FC4C5A6D6DEE7F806D6C6C6C4BC7FC6E01E0EC07FE020F 01FEEC1FF80203903AFFE001FFF0020091B612C0033F93C8FC030715FCDB007F14E00401 01FCC9FC525479D261>I<932601FFFCEC01C0047FD9FFC013030307B600F81307033F03 FE131F92B8EA803F0203DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A018002 03B5FC494848C9FC4901F8824949824949824949824949824990CA7E494883A248498348 5B1B7F485B481A3FA24849181FA3485B1B0FA25AA298C8FC5CA2B5FCAE6C057FB712E0A2 80A36C94C7003FEBC000A36C7FA36C7FA27E6C7FA26C7F6C7FA26D7E6D7F6D7F6D6D5E6D 7F6D01FC93B5FC6D13FF6D6C6D5C6E01F0EC07FB020F01FEEC1FF10203903AFFF001FFE0 020091B6EAC07F033FEE001F030703FC1307DB007F02E01301040149CAFC5B5479D26A> 71 D97 D<913803FFC0023F13FC49B6FC010715C04901817F903A3FFC007FF849486D7E49486D7E 4849130F48496D7E48178048497F18C0488191C7FC4817E0A248815B18F0A212FFA490B8 FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E14037E6C6DEC07E0A26C6DEC0FC06C 6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0FFFC03FF8010390B55A010015C002 1F49C7FC020113F034387CB63D>101 D104 D<137F497E000313E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0B5FCA5 12017EB3B3A6B612E0A51B547BD325>I109 DI<913801FFE0021F13FE91B612C0010315F0010F9038807FFC903A1FFC 000FFED97FF86D6C7E49486D7F48496D7F48496D7F4A147F48834890C86C7EA24883A248 486F7EA3007F1880A400FF18C0AC007F1880A3003F18006D5DA26C5FA26C5F6E147F6C5F 6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE011F90C7FC903A0FFF807FFC6D90B55A01 0015C0023F91C8FC020113E03A387CB643>I<903A3FF001FFE0B5010F13FE033FEBFFC0 92B612F002F301017F913AF7F8007FFE0003D9FFE0EB1FFFC602806D7F92C76C7F4A824A 6E7F4A6E7FA2717FA285187F85A4721380AC1A0060A36118FFA2615F616E4A5BA26E4A5B 6E4A5B6F495B6F4990C7FC03F0EBFFFC9126FBFE075B02F8B612E06F1480031F01FCC8FC 030313C092CBFCB1B612F8A5414D7BB54B>I<90397FE003FEB590380FFF80033F13E04B 13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02FEEB 3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537>114 D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307D81FE0130148487F4980 127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C 816C816C81C681013F1580010F15C01300020714E0EC003F030713F015010078EC007F00 F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FF C00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB635>I<143EA6147EA414 FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE 07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C5B021F5B0203 13802A4D7ECB34>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmr10 10 54 /Fc 54 123 df12 D14 D<121C127FEAFF80A213C0A3 127F121C1200A412011380A2120313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FC A25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E 1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F 6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0 B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7 FC120E5A5A5A5A5A13527CBD20>I<121C127FEAFF80A213C0A3127F121C1200A4120113 80A2120313005A1206120E5A5A5A12600A19798817>44 DI<12 1C127FEAFF80A5EA7F00121C0909798817>I49 DII<1538A2157815F8A2140114031407A2140F141F141B143314 73146314C313011483EB030313071306130C131C131813301370136013C01201EA038013 005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B512F8A325397EB8 2A>I54 D<121C127FEAFF80A5EA7F00121CC7FCB212 1C127FEAFF80A5EA7F00121C092479A317>58 D<1538A3157CA315FEA34A7EA34A6C7EA2 02077FEC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202 C07F1501A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7E A3496E7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB 3E>65 D<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03FC000F0FD90F F0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F4848150FA24848 1507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A3123F7F001F1603 18006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE05C6D6CEB03C0 D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D7BBA3C>67 DI< B812FCA30001903880000F6C90C71201EE007E173E171E170EA31706A317078316C0A394 C7FCA31501A21503150F91B5FCA3EC000F15031501A21500A21860A318E093C712C0A417 01A3EF0380A21707A2170F173F177F486D903807FF00B9FCA333397DB839>I71 DI< B612C0A3C6EBC0006D5AB3B3AD497EB612C0A31A397EB81E>I76 D78 D80 D82 D<003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770 A300601730A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C> 84 D87 D89 D97 DIIII<147E903803FF 8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801F8 C7FCB3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE000FFD93F FCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01FE 14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257E A445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE49 6D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<3903 F01FE000FFEB7FF89038F1E07E9039F3801F803A07F7000FC0D803FEEB07E049EB03F049 14F849130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001 F614C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA4 2E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC 03E09038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F81201 12031207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB 0FFEEB01F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038 EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A495A495A A290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7127C48 EB03FC90B5FCA21F247EA325>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmsy10 10 1 /Fd 1 16 df15 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmbx12 12 31 /Fe 31 120 df35 D44 D46 D48 D50 D<0007150301E0143F01FFEB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9 FCAAEC3FF001C1B5FC01C714C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D13 804915C0497F6C4815E0C8FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C 4815E05B007EC74813C0123E003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB6 12F0C65D013F1480010F01FCC7FC010113C02D427BC038>53 D<4AB47E021F13F0027F13 FC49B6FC01079038807F8090390FFC001FD93FF014C04948137F4948EBFFE048495A5A14 00485A120FA248486D13C0EE7F80EE1E00003F92C7FCA25B127FA2EC07FC91381FFF8000 FF017F13E091B512F89039F9F01FFC9039FBC007FE9039FF8003FF17804A6C13C05B6F13 E0A24915F0A317F85BA4127FA5123FA217F07F121FA2000F4A13E0A26C6C15C06D491380 6C018014006C6D485A6C9038E01FFC6DB55A011F5C010714C0010191C7FC9038003FF02D 427BC038>I58 D65 D68 D71 DI75 D83 D<903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C 6D7EA26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC 01000313E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE 013EEBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36> 97 D99 D101 DI<137C48B4FC4813804813 C0A24813E0A56C13C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6 FCA518467CC520>105 D107 DI<9027 7F8007FEEC0FFCB590263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01F FC0FE03FF8913D8FC00FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC 5D02F86D496D7EA24A5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<9039 7F8007FEB590383FFF8092B512E0028114F8913987F03FFC91388F801F000390399F000F FE6C139E14BC02F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF 14F89139DFC03FFC9139FF001FFE000301FCEB07FF6C496D13804A15C04A6D13E05C7013 F0A2EF7FF8A4EF3FFCACEF7FF8A318F017FFA24C13E06E15C06E5B6E4913806E4913006E 495A9139DFC07FFC02CFB512F002C314C002C091C7FCED1FF092C9FCADB67EA536407DAC 3E>I<90387F807FB53881FFE0028313F0028F13F8ED8FFC91389F1FFE000313BE6C13BC 14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35CB3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B51287000314FF120F381FF003383FC00049133F48C7121F127E00FE 140FA215077EA27F01E090C7FC13FE387FFFF014FF6C14C015F06C14FC6C800003806C15 806C7E010F14C0EB003F020313E0140000F0143FA26C141F150FA27EA26C15C06C141FA2 6DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F03F13E026E007FEC7FC232F7CAD2C >IIIII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmbx12 17.28 21 /Ff 21 125 df45 D48 D<16F04B7E1507151F153FEC 01FF1407147F010FB5FCB7FCA41487EBF007C7FCB3B3B3B3007FB91280A6395E74DD51> I<913801FFF8021FEBFFC091B612F8010315FF010F16C0013F8290267FFC0114F89027FF E0003F7F4890C7000F7F48486E7FD807F86E148048486E14C048486E14E048486F13F001 FC17F8486C816D17FC6E80B56C16FE8380A219FFA283A36C5BA26C5B6C90C8FCD807FC5D EA01F0CA14FEA34D13FCA219F85F19F04D13E0A294B512C019804C14004C5B604C5B4C5B 604C13804C90C7FC4C5A4C5A4B13F05F4B13804B90C8FC4B5AED1FF84B5A4B5A4B48143F 4A5B4A48C8FC4A5A4A48157E4A5A4A5AEC7F8092C9FC02FE16FE495A495A4948ED01FCD9 0FC0150749B8FC5B5B90B9FC5A4818F85A5A5A5A5ABAFCA219F0A4405E78DD51>I52 D<01C0EE01C0D801F8160F01FF167F02F0EC07FFDAFF8090B5FC92B71280190060606060 60606095C7FC17FC5F17E0178004FCC8FC16E09026FC3FFCC9FC91CBFCADED3FFE0203B5 12F0020F14FE023F6E7E91B712E001FDD9E00F7F9027FFFE00037F02F801007F02E06EB4 FC02806E138091C8FC496F13C04917E07113F0EA00F090C914F8A219FC83A219FEA419FF A3EA03F0EA0FFC487E487E487FA2B57EA319FEA35C4D13FC6C90C8FC5B4917F8EA3FF001 804B13F06D17E0001F5E6C6C17C06D4B1380D807FC92B512006C6C4A5B6C6C6C01075B6C 01E0011F5BD97FFE90B55A6DB712C0010F93C7FC6D15FC010115F0D9003F1480020301F0 C8FC406078DD51>II65 D83 D103 D<903807FF80B6FCA6C6FC7F7FB3A8EF1FFF94B512F0040714FC041F14FF4C819326 7FE07F7F922781FE001F7FDB83F86D7FDB87F07FDB8FC0814C7F039FC78015BE03BC8003 FC825DA25DA25DA45DB3B2B7D8F007B71280A651647BE35A>II<903807FF80B6FCA6C6FC7F7FB3B3B3 B3ADB712E0A623647BE32C>108 D<902607FF80D91FFFEEFFF8B691B500F00207EBFF80 040702FC023F14E0041F02FF91B612F84C6F488193267FE07F6D4801037F922781FE001F 9027E00FF0007FC6DA83F86D9026F01FC06D7F6DD987F06D4A487F6DD98FC0DBF87EC780 4C6D027C80039FC76E488203BEEEFDF003BC6E4A8003FC04FF834B5FA24B5FA24B94C8FC A44B5EB3B2B7D8F007B7D8803FB612FCA67E417BC087>I<902607FF80EB1FFFB691B512 F0040714FC041F14FF4C8193267FE07F7F922781FE001F7FC6DA83F86D7F6DD987F07F6D D98FC0814C7F039FC78015BE03BC8003FC825DA25DA25DA45DB3B2B7D8F007B71280A651 417BC05A>I<923807FFE092B6FC020715E0021F15F8027F15FE494848C66C6C7E010701 F0010F13E04901C001037F49496D7F4990C87F49486F7E49486F7E48496F13804819C04A 814819E048496F13F0A24819F8A348496F13FCA34819FEA4B518FFAD6C19FEA46C6D4B13 FCA36C19F8A26C6D4B13F0A26C19E06C6D4B13C0A26C6D4B13806C6D4B13006D6C4B5A6D 6D495B6D6D495B010701F0010F13E06D01FE017F5B010090B7C7FC023F15FC020715E002 0092C8FC030713E048437CC151>I<902607FF80EBFFF8B6010FEBFF80047F14F00381B6 12FC038715FF038F010114C09227BFF0003F7FC6DAFFC0010F7F6D91C76C7F6D496E7F03 F86E7F4B6E7F4B17804B6F13C0A27313E0A27313F0A21BF885A21BFCA3851BFEAE4F13FC A41BF861A21BF0611BE0611BC06F92B512801B006F5C6F4A5B6F4A5B03FF4A5B70495B04 E0017F13C09226CFFC03B55A03C7B648C7FC03C115F803C015E0041F91C8FC040313E093 CBFCB3A3B712F0A64F5D7BC05A>I114 D<913A3FFF8007800107B5EAF81F011FECFE7F017F91B5FC48B8FC48EBE0014890C7121F D80FFC1407D81FF0801600485A007F167F49153FA212FF171FA27F7F7F6D92C7FC13FF14 E014FF6C14F8EDFFC06C15FC16FF6C16C06C16F06C826C826C826C82013F1680010F16C0 1303D9007F15E0020315F0EC001F1500041F13F81607007C150100FC81177F6C163FA217 1F7EA26D16F0A27F173F6D16E06D157F6D16C001FEEDFF806D0203130002C0EB0FFE02FC EB7FFC01DFB65A010F5DD8FE0315C026F8007F49C7FC48010F13E035437BC140>II124 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmbx10 10 21 /Fg 21 116 df45 D<141E143E14FE1307133FB5FCA313CFEA00 0FB3B3A6007FB61280A4213779B630>49 DI52 D<001C15C0D81F80130701F8 137F90B61280A216005D5D15F05D15804AC7FC14F090C9FCA8EB07FE90383FFFE090B512 F89038FC07FC9038E003FFD98001138090C713C0120EC813E0157F16F0A216F8A21206EA 3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15C06C5B6C491380D9C0071300 390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC25387BB630>I58 D72 D80 D82 DI87 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FF DAF00013804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8 A217F06E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F 13E0D9C00390C7FC2F3A7EB935>98 D100 D<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F 804848133F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0 C8FCA4127FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06D B51200010F13FC010113E025257DA42C>I105 D<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>108 D<01FED97FE0EB0FFC00FF90 2601FFFC90383FFF80020701FF90B512E0DA1F81903983F03FF0DA3C00903887801F0007 49DACF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B5 12F0A44C257DA451>I<01FEEB7FC000FF903803FFF8020F13FE91381F03FFDA3C011380 000713780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<90 3801FFC0010F13F8017F13FFD9FF807F3A03FE003FE048486D7E48486D7E48486D7EA200 3F81491303007F81A300FF1680A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C49 5A6C6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029257DA430>I<9038FE03F000 FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92 C7FC91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381F C00F383F0003007E1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14 C06C14F06C14F81203C614FC131F9038007FFE140700F0130114007E157E7E157C6C14FC 6C14F8EB80019038F007F090B512C000F8140038E01FF81F257DA426>I E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 0 -237 a Fg(15-451)94 b(HW)31 b(5)3233 b(1)p 0 -204 3900 4 v 0 58 4012 4 v 0 728 4 670 v 482 218 a Ff(15-451)52 b(|)i(Algorithms)g(|)g(Spring)f(2006)1392 335 y Fe(Sleator,)36 b(Golo)m(vin,)h(Kissner)1649 539 y(Homew)m(ork)f(#5)1185 683 y(Due:)50 b(April)36 b(6,)h(2006,)h(start)f (of)h(class.)p 4008 728 V 0 731 4012 4 v 0 1011 a Fg(Some)30 b(Reminders:)125 1213 y Fd(\017)41 b Fc(Y)-7 b(ou)30 b(ma)n(y)g(discuss)g(these)g(problems)g(with)h(others,)f(in)h(small)f (groups.)43 b(Ho)n(w)n(ev)n(er)29 b(w)n(e)h(strongly)f(recommend)h (that)208 1313 y(y)n(ou)c(think)i(for)g(a)f(while)g(ab)r(out)h(them)g (y)n(ourself)f(b)r(efore)g(starting)g(suc)n(h)g(discussions.)125 1479 y Fd(\017)41 b Fc(The)33 b(w)n(ork)f(that)i(y)n(ou)f(turn)g(in)h (m)n(ust)f(b)r(e)h(y)n(our)e(o)n(wn,)j(written)e(b)n(y)h(y)n(ou)e(in)i (y)n(our)e(o)n(wn)h(w)n(ords.)53 b(W)-7 b(e)34 b(are)f(allo)n(wing)208 1578 y(handwritten)28 b(solutions,)f(although)h(t)n(yp)r(eset)g(ones)g (are)f(preferred.)38 b(If)28 b(y)n(ou)g(handwrite,)g(WRITE)g(CLEARL)-7 b(Y,)28 b(or)208 1678 y(w)n(e)f(will)h(rev)n(ert)e(to)h(the)h(old)g (system)f(of)h(requiring)e(y)n(ou)h(to)g(t)n(yp)r(eset)h(solutions.)125 1844 y Fd(\017)41 b Fc(The)e(co)n(v)n(er)e(page)h(of)g(y)n(our)g (submission)g(m)n(ust)i(clearly)d(displa)n(y)h(the)i(assignmen)n(t)e(n) n(um)n(b)r(er,)j(y)n(our)d(name,)j(y)n(our)208 1944 y(recitation)26 b(section)i(and)f(y)n(our)f(Andrew)i(ID.)0 2146 y Fg(Problems:)0 2456 y Fb(1)135 b(A)44 b(Bipartite)i(Game)0 2590 y Fc(Consider)29 b(the)h(follo)n(wing)f(2-pla)n(y)n(er)f(p)r(erfect)i(information)g (game.)43 b(The)30 b(t)n(w)n(o)g(pla)n(y)n(ers)e(are)h(called)h(Left)g (and)g(Righ)n(t.)44 b(The)0 2690 y(game)31 b(is)g(pla)n(y)n(ed)f(on)i (an)f(undirected)g(bipartite)h(graph)e Fa(G)p Fc(,)j(in)e(whic)n(h)h (the)g(t)n(w)n(o)e(parts)h(are)g(called)g Fa(L)g Fc(and)g Fa(R)q Fc(.)48 b(Left)32 b(go)r(es)0 2790 y(\014rst)k(b)n(y)g(pic)n (king)g(an)n(y)f(v)n(ertex)h(of)g Fa(L)p Fc(.)62 b(Then)37 b(Righ)n(t)f(pic)n(ks)g(a)g(neigh)n(b)r(or)f(of)h(this)h(v)n(ertex)e (\(whic)n(h)i(is)f(in)g Fa(R)q Fc(,)j(of)d(course\).)0 2889 y(Pla)n(y)28 b(con)n(tin)n(ues)h(in)i(this)f(w)n(a)n(y)-7 b(,)29 b(with)h(eac)n(h)f(pla)n(y)n(er)f(pic)n(king)i(a)f(v)n(ertex)g (of)g(the)i(appropriate)d(set)h(neigh)n(b)r(oring)g(the)h(v)n(ertex)0 2989 y(just)g(pic)n(k)n(ed,)f(with)h(the)f(additional)g(pro)n(viso)f (that)h(a)g(v)n(ertex)f(ma)n(y)h(b)r(e)g(used)h(only)f(once.)41 b(The)29 b(pla)n(y)n(er)f(who)h(\014nds)g(herself)0 3089 y(without)f(a)f(legal)g(mo)n(v)n(e)f(loses)h(the)h(game.)60 3307 y(\(a\))42 b(Assume)29 b(that)h(the)g(graph)e Fa(G)i Fc(has)f(a)g(matc)n(hing)g(in)h(whic)n(h)f(ev)n(ery)g(v)n(ertex)f(of)i Fa(L)f Fc(is)g(in)h(the)g(matc)n(hing.)42 b(Pro)n(v)n(e)208 3407 y(that)27 b(in)h(this)g(case)f(Righ)n(t)g(has)g(a)h(winning)f (strategy)-7 b(.)55 3539 y(\(b\))43 b(Assume)34 b(that)g(the)h(graph)e Fa(G)i Fc(has)f(a)g(matc)n(hing)f(in)i(whic)n(h)f(ev)n(ery)f(v)n(ertex) h(of)g Fa(R)h Fc(is)f(in)h(the)f(matc)n(hing,)i(but)208 3639 y(some)27 b(v)n(ertex)f(of)i Fa(L)f Fc(is)g(not)h(in)g(the)g(matc) n(hing.)36 b(Pro)n(v)n(e)25 b(that)j(in)g(this)g(case)f(Left)h(has)f(a) g(winning)h(strategy)-7 b(.)65 3772 y(\(c\))42 b(Extend)24 b(parts)h(\(a\))g(and)g(\(b\))g(to)g(giv)n(e)f(a)h(complete)g(c)n (haracterization)d(of)j(the)h(class)e(of)h(graphs)e(on)i(whic)n(h)g (Left)208 3871 y(has)i(a)g(winning)g(strategy)-7 b(.)36 b(Explain)27 b(wh)n(y)g(y)n(our)g(c)n(haracterization)e(is)i(correct.) 55 4004 y(\(d\))43 b(No)n(w)21 b(giv)n(e)f(a)i(p)r(olynomial)f(time)h (algorithm)e(whic)n(h)i(tak)n(es)e(an)i(arbitrary)d(bipartite)j(graph)e Fa(G)i Fc(and)g(determines)208 4104 y(whic)n(h)27 b(pla)n(y)n(er)f(has) h(a)g(winning)h(strategy)-7 b(.)p eop %%Page: 2 2 2 1 bop 0 -237 a Fg(15-451)94 b(HW)31 b(5)3233 b(2)p 0 -204 3900 4 v 0 83 a Fb(2)135 b(Cohesion)0 218 y Fc(Consider)28 b(problem)h(46)g(on)g(page)f(444)g(of)i(the)g(b)r(o)r(ok.)41 b(The)30 b(solution)f(to)g(the)h(problem)f(is)g(to)g(build)h(a)f(graph) f Fa(H)37 b Fc(from)29 b Fa(G)p Fc(,)0 317 y(and)c(to)g(\014nd)h(a)f (min)g(cut)h(in)f Fa(H)7 b Fc(.)36 b(This)25 b(graph)f(has)h(the)h (prop)r(ert)n(y)e(that)h(if)h(the)g(minim)n(um)g(cut)f(\(in)h(a)f (certain)f(class)g(of)i(cuts\))0 417 y(is)h(su\016cien)n(tly)h(small,)f (then)h(the)g(cohesion)f(is)g(at)h(least)f Fa(\013)p Fc(.)0 552 y(Here's)e(ho)n(w)f(w)n(e)h(build)g Fa(H)7 b Fc(.)36 b(The)25 b(graph)f(has)h(four)g(columns)f(of)h(v)n(ertices.) 35 b(The)26 b(left)f(column)g(\(column)h(1\))f(is)g(the)g(source)f Fa(s)p Fc(.)0 652 y(The)k(next)h(column)f(has)f(a)h(v)n(ertex)f(for)h (eac)n(h)f(v)n(ertex)g(of)h Fa(G)p Fc(.)39 b(The)28 b(third)g(column)h (has)e(a)h(v)n(ertex)f(for)h(eac)n(h)f(edge)g(of)i Fa(G)p Fc(,)f(and)0 751 y(the)i(fourth)g(column)f(is)h Fa(t)p Fc(.)43 b(The)30 b(edges)f(go)f(from)i(a)f(column)h(to)f(the)h(next)g (column)g(to)f(the)h(righ)n(t.)43 b(The)29 b(edges)g(from)h Fa(s)f Fc(to)0 851 y(column)g(2)f(all)g(ha)n(v)n(e)f(capacit)n(y)h Fa(\013)p Fc(.)40 b(The)29 b(edges)f(from)g(column)g(2)g(to)h(column)f (3)h(all)f(ha)n(v)n(e)f(in\014nite)j(capacit)n(y)-7 b(,)27 b(and)i(there)f(is)0 951 y(suc)n(h)f(an)g(edge)g(if)g(the)h(corresp)r (onding)d(v)n(ertex)h(and)h(edge)g(of)g Fa(G)h Fc(are)e(inciden)n(t.)37 b(The)28 b(edges)e(from)h(column)g(3)g(to)g Fa(t)g Fc(all)g(ha)n(v)n(e) 0 1050 y(capacit)n(y)f(1.)0 1186 y(Let)i Fa(n)f Fc(b)r(e)h(the)g(n)n (um)n(b)r(er)g(of)f(v)n(ertices)g(of)g Fa(G)p Fc(,)h(and)g(let)g Fa(m)f Fc(b)r(e)h(the)g(n)n(um)n(b)r(er)f(of)h(edges)f(of)g Fa(G)p Fc(.)60 1404 y(\(a\))42 b(No)n(w)27 b(pro)n(v)n(e)f(the)i (theorem:)390 1570 y(Theorem:)43 b(The)30 b(graph)g Fa(G)h Fc(has)f(cohesion)g(at)h(least)f Fa(\013)h Fc(if)g(and)g(only)f(if)i (the)f(minim)n(um)g(cut)g(of)g Fa(H)390 1670 y Fc(\(among)c(all)f(the)i (cuts)f(whic)n(h)h(cut)f(at)g(least)g(one)g(of)g(the)g(edges)g(from)g (column)g(1)g(to)g(column)g(2\))g(is)390 1769 y(at)h(most)f Fa(m)p Fc(.)55 1935 y(\(b\))43 b(Giv)n(e)30 b(a)h(p)r(olynomial-time)f (algorithm)g(that)i(can)e(compute)i(the)f(appropriate)e(minim)n(um)j (cut)g(of)f Fa(H)37 b Fc(that's)208 2035 y(needed)27 b(in)h(the)g(theorem.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF