(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: hw6.dvi %%Pages: 1 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f hw6.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2006.04.09:1630 %%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 (hw6.dvi) @start %DVIPSBitmapFont: Fa cmsy7 7 1 /Fa 1 1 df0 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmmi7 7 2 /Fb 2 111 df<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230A212 605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA07F0 6C5A11287DA617>105 D<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00D860 FE133C5B5B00C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0A2ED C180913803C300D81F0013C7EC01FE000EEB00F8231B7D9929>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmr7 7 2 /Fc 2 51 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC15 005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA018039030003 0012065A001FB5FC5A485BB5FCA219267DA521>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmmi10 10 13 /Fd 13 122 df<121C127FEAFF80A5EA7F00121C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>I<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07 FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007F C0EE1FF0EE07FCEE01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC0 4B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0 EB7FC04848CAFCEA07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>62 D<1760177017F01601A21603A21607160FA24C7EA216331673166316C3A2ED0183A2ED03 03150683150C160115181530A21560A215C014011580DA03007FA202061300140E140C5C 021FB5FC5CA20260C7FC5C83495A8349C8FC1306A25BA25B13385B01F01680487E000716 FFB56C013F13FF5EA2383C7DBB3E>65 D<4BB4FC031F13F09238FE01FC913903F0007EDA 07C0EB1F80DA1F80EB0FC0023EC7EA07E002FCEC03F0495A4948EC01F8495A4948EC00FC 495A49C912FE49167E13FE49167F1201485AA2485AA2120F5B001F17FFA2485AA34848ED 01FEA400FFEE03FC90C9FCA2EF07F8A2EF0FF0A218E0171F18C0EF3F806C167F180017FE 4C5A6C6C5D1603001F4B5A6D4A5A000FED1F806C6C4AC7FC6D147E0003EC01F8D801FC49 5AD8007EEB0FC090263F807FC8FC903807FFF801001380383D7CBA3F>79 D<147E903803FF8090390FC1C38090391F00EFC0017E137F49133F485A4848EB1F801207 5B000F143F48481400A2485A5D007F147E90C7FCA215FE485C5AA214015D48150CA21403 EDF01C16181407007C1538007E010F1330003E131F027B13706C01E113E03A0F83C0F9C0 3A03FF007F80D800FCEB1F0026267DA42C>97 D<133FEA1FFFA3C67E137EA313FE5BA312 015BA312035BA31207EBE0FCEBE3FF9038E707C0390FFE03E09038F801F001F013F8EBE0 00485A15FC5BA2123F90C7FCA214015A127EA2140312FE4814F8A2140715F05AEC0FE0A2 15C0EC1F80143F00781400007C137E5C383C01F86C485A380F07C06CB4C7FCEA01FC1E3B 7CB924>II<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E1380 121C121812381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B12035B A20007131813E01438000F133013C01470EB806014E014C01381EB838038078700EA03FE EA00F815397EB71D>105 D110 D<90390F8003F090391FE00FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0 FF80030013E00001491303018015F05CEA038113015CA2D800031407A25CA20107140FA2 4A14E0A2010F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90 397F700F80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207 B512C0A32C3583A42A>112 D<903907E001F090391FF807FC9039783E0E0F9039E01F1C 1FD801C09038383F803A03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C 4AC7FC1218A2C7123FA292C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F 5BD87F81143801835C00FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC39 1FF00FFC3907C003F029267EA42F>120 D<13F8D803FE1470D8070F14F8000EEB800112 1C121800381403003015F0EA701F1260013F130700E0010013E012C05BD8007E130F16C0 13FE5B151F000115805BA2153F000315005BA25D157EA315FE5D1401000113033800F807 90387C1FF8EB3FF9EB0FE1EB00035DA2000E1307D83F805B007F495AA24A5A92C7FCEB00 3E007C5B00705B6C485A381E07C06CB4C8FCEA01FC25367EA429>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmbx12 14.4 32 /Fe 32 122 df45 D<157815FC14031407141F14FF130F0007B5 FCB6FCA2147F13F0EAF800C7FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI<91380FFFC091B512FC0107ECFF80011F15E09026 3FF8077F9026FF800113FC4848C76C7ED803F86E7E491680D807FC8048B416C080486D15 E0A4805CA36C17C06C5B6C90C75AD801FC1680C9FC4C13005FA24C5A4B5B4B5B4B13C04B 5BDBFFFEC7FC91B512F816E016FCEEFF80DA000713E0030113F89238007FFE707E701380 7013C018E07013F0A218F8A27013FCA218FEA2EA03E0EA0FF8487E487E487EB57EA318FC A25E18F891C7FC6C17F0495C6C4816E001F04A13C06C484A1380D80FF84A13006CB44A5A 6CD9F0075BC690B612F06D5D011F1580010302FCC7FCD9001F1380374F7ACD43>I<171F 4D7E4D7EA24D7EA34C7FA24C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C 7E03018116F8830303814C7E03078116E083030F814C7E031F81168083033F8293C77E4B 82157E8403FE824B800201835D840203834B800207835D844AB87EA24A83A3DA3F80C880 92C97E4A84A2027E8202FE844A82010185A24A820103854A82010785A24A82010F855C01 1F717FEBFFFCB600F8020FB712E0A55B547BD366>65 DI70 D72 D77 D80 D<91260FFF80130791B500F85B010702FF5B011FEDC03F49EDF07F9026FFFC006D5A4801 E0EB0FFD4801800101B5FC4848C87E48488149150F001F824981123F4981007F82A28412 FF84A27FA26D82A27F7F6D93C7FC14C06C13F014FF15F86CECFF8016FC6CEDFFC017F06C 16FC6C16FF6C17C06C836C836D826D82010F821303010082021F16801400030F15C0ED00 7F040714E01600173F050F13F08383A200788200F882A3187FA27EA219E07EA26CEFFFC0 A27F6D4B13806D17006D5D01FC4B5A01FF4B5A02C04A5A02F8EC7FF0903B1FFFC003FFE0 486C90B65AD8FC0393C7FC48C66C14FC48010F14F048D9007F90C8FC3C5479D24B>83 D<003FBC1280A59126C0003F9038C0007F49C71607D87FF8060113C001E08449197F4919 3F90C8171FA2007E1A0FA3007C1A07A500FC1BE0481A03A6C994C7FCB3B3AC91B912F0A5 53517BD05E>II87 D97 D<913801FFF8021FEBFF8091B612F0010315FC010F9038C00FFE903A1FFE0001FF D97FFC491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC486F1300705A4892 C8FC5BA312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F6CEE1F806C6DEC3F 006C6D147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A01001580023F49C7FC02 0113E033387CB63C>99 D<913803FFC0023F13FC49B6FC010715C04901817F903A3FFC00 7FF849486D7E49486D7E4849130F48496D7E48178048497F18C0488191C7FC4817E0A248 815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E14037E6C6D EC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0FFFC03FF8 010390B55A010015C0021F49C7FC020113F034387CB63D>101 DIII<137F497E000313E048 7FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0B5FCA512017EB3B3A6B612E0A5 1B547BD325>I108 DII<913801FFE0021F13FE91B6 12C0010315F0010F9038807FFC903A1FFC000FFED97FF86D6C7E49486D7F48496D7F4849 6D7F4A147F48834890C86C7EA24883A248486F7EA3007F1880A400FF18C0AC007F1880A3 003F18006D5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE 011F90C7FC903A0FFF807FFC6D90B55A010015C0023F91C8FC020113E03A387CB643>I< 912601FFE0EB0780021F01F8130F91B500FE131F0103ECFF80010F9039F03FC03F499039 800FE07F903A7FFE0003F04948903801F8FF4849EB00FD4849147F4A805A4849805A4A80 5AA291C87E5AA35B12FFAC6C7EA37EA2806C5EA26C6D5CA26C6D5C6C6D5C6C93B5FC6C6D 5B6D6C5B6DB4EB0FEF010F9038C07FCF6D90B5120F010114FED9003F13F80203138091C8 FCB1040FB61280A5414D7CB547>113 D<90397FE003FEB590380FFF80033F13E04B13F0 9238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02FEEB3FFC 5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537>I<903903FFF00F013FEBFE 1F90B7FC120348EB003FD80FF81307D81FE0130148487F4980127F90C87EA24881A27FA2 7F01F091C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C816C816C81C681013F1580 010F15C01300020714E0EC003F030713F015010078EC007F00F8153F161F7E160FA27E17 E07E6D141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FFC00FFC6DB55AD8FC1F14E0 D8F807148048C601F8C7FC2C387CB635>I<143EA6147EA414FEA21301A313031307A213 0F131F133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE07C0AB011FEC0F8080A26D EC1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C5B021F5B020313802A4D7ECB34>III121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmr10 10 60 /Ff 60 124 df12 D<001C131C007F137F39FF80FF80A26D13C0A300 7F137F001C131C00001300A40001130101801380A20003130301001300485B0006130600 0E130E485B485B485B006013601A197DB92A>34 D<121C127FEAFF80A213C0A3127F121C 1200A412011380A2120313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FC A25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E 1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F 6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0 B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7 FC120E5A5A5A5A5A13527CBD20>I<15301578B3A6007FB812F8B912FCA26C17F8C80078 C8FCB3A6153036367BAF41>43 D<121C127FEAFF80A213C0A3127F121C1200A412011380 A2120313005A1206120E5A5A5A12600A19798817>II<121C127F EAFF80A5EA7F00121C0909798817>I48 DII<1538A2157815F8A2140114031407A2140F141F141B14331473146314C313011483EB 030313071306130C131C131813301370136013C01201EA038013005A120E120C5A123812 305A12E0B712F8A3C73803F800AB4A7E0103B512F8A325397EB82A>52 D<121C127FEAFF80A5EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317> 58 D<007FB812F8B912FCA3CCFCAEB912FCA36C17F836167B9F41>61 D<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA2020E7FEC0C1FA2021C7FEC18 0FA202387FEC3007A202707FEC6003A202C07F1501A2D901807F81A249C77F167FA20106 810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E7EA213E0707E1201486C81D8 0FFC02071380B56C90B512FEA3373C7DBB3E>65 D<913A01FF800180020FEBE003027F13 F8903A01FF807E07903A03FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F 01FE153F12014848151F4848150FA248481507A2485A1703123F5B007F1601A35B00FF93 C7FCAD127F6DED0180A3123F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D000016 18017F15386D6C5CD91FE05C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFF FC020F13F002011380313D7BBA3C>67 DIIIIII<013FB512E0A39039001FFC00EC07F8B3B3A3123FEA7F 80EAFFC0A44A5A1380D87F005B0070131F6C5C6C495A6C49C7FC380781FC3801FFF03800 7F80233B7DB82B>I77 DI80 D83 D<003FB812E0A3D9C003 EB001F273E0001FE130348EE01F00078160000701770A300601730A400E01738481718A4 C71600B3B0913807FF80011FB612E0A335397DB83C>I87 D89 D91 D<3901800180000313033907 000700000E130E485B0018131800381338003013300070137000601360A200E013E0485B A400CE13CE39FF80FF806D13C0A3007F137FA2393F803F80390E000E001A1974B92A>I< EAFFF8A4EA0078B3B3B3B3A3EAFFF8A40D537FBD17>I97 DIIII<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213 FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I< ED03F090390FF00FF890393FFC3C3C9039F81F707C3901F00FE03903E007C03A07C003E0 10000FECF000A248486C7EA86C6C485AA200075C6C6C485A6D485A6D48C7FC38073FFC38 060FF0000EC9FCA4120FA213C06CB512C015F86C14FE6CECFF804815C03A0F80007FE048 C7EA0FF0003E140348140116F8481400A56C1401007C15F06CEC03E0003F1407D80F80EB 0F80D807E0EB3F003901FC01FC39007FFFF0010790C7FC26387EA52A>III107 DI<2703F00FF0EB1FE000FFD93FFCEB7FF8913AF03F01E07E903B F1C01F83803F3D0FF3800FC7001F802603F70013CE01FE14DC49D907F8EB0FC0A2495CA3 495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257EA445>I<3903F00FF000FFEB3F FCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A3486C497EB5 00C1B51280A329257EA42E>II<3903F01FE000FFEB7FF89038F1E07E 9039F3801F803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC150016FEA316 7FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F009038F1E0 7E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA42E>II<3807E01F00FFEB7F C09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038FC0080491300A45BB3 A2487EB512F0A31C257EA421>II<1318A51338A31378A313F8120112031207001FB5FCB6FCA2D801 F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038EB0FE012300070EB1FC0EC3F80 0060137F150014FE495AA2C6485A495AA2495A495A495AA290387F000613FEA2485A485A 0007140E5B4848130C4848131CA24848133C48C7127C48EB03FC90B5FCA21F247EA325> II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmsy10 10 11 /Fg 11 113 df<007FB81280B912C0A26C17803204799641>0 D15 D20 D<126012F0B3B3B3B3A5B512F014F8A26C13F0155272BD25>98 D<14301478B3B3B3B3A5 387FFFF8B5FCA26C13F015527FBD25>I<387FFFF0B512F8A214F000F0C7FCB3B3B3B3A5 1260155272BD25>I<387FFFF0B512F8A27EC71278B3B3B3B3A5143015527FBD25>II<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A7 801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A713 1F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D537ABD2A>I<126012F0B3B3B3B3 A91260045377BD17>106 D112 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmbx12 12 33 /Fh 33 122 df35 D44 D46 D48 DII<4AB47E021F13 F0027F13FC49B6FC01079038807F8090390FFC001FD93FF014C04948137F4948EBFFE048 495A5A1400485A120FA248486D13C0EE7F80EE1E00003F92C7FCA25B127FA2EC07FC9138 1FFF8000FF017F13E091B512F89039F9F01FFC9039FBC007FE9039FF8003FF17804A6C13 C05B6F13E0A24915F0A317F85BA4127FA5123FA217F07F121FA2000F4A13E0A26C6C15C0 6D4913806C018014006C6D485A6C9038E01FFC6DB55A011F5C010714C0010191C7FC9038 003FF02D427BC038>54 D56 D58 D65 D68 D71 DI75 D83 D<003FBA12E0A59026FE000F EB8003D87FE09338003FF049171F90C71607A2007E1803007C1801A300781800A400F819 F8481978A5C81700B3B3A20107B8FCA545437CC24E>I<903801FFE0011F13FE017F6D7E 48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7EA26F7FA36F7F6C5A6C5AEA00F090 C7FCA40203B5FC91B6FC1307013F13F19038FFFC01000313E0000F1380381FFE00485A5B 127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013EEBFFC03A1FFF80FC7F0007EBFFF8 6CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 D100 DI<137C48B4FC4813804813C0A24813E0A56C13C0A26C13806C 1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520>105 D107 DI<90277F8007FEEC0FFCB590 263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC0 0FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A 5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F8007FEB590383FFF 8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D 7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF14F89139DFC03FFC91 39FF001FFE000301FCEB07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF3FFC ACEF7FF8A318F017FFA24C13E06E15C06E5B6E4913806E4913006E495A9139DFC07FFC02 CFB512F002C314C002C091C7FCED1FF092C9FCADB67EA536407DAC3E>I<90387F807FB5 3881FFE0028313F0028F13F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC91 38E007F8ED01E092C7FCA35CB3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B512 87000314FF120F381FF003383FC00049133F48C7121F127E00FE140FA215077EA27F01E0 90C7FC13FE387FFFF014FF6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F 020313E0140000F0143FA26C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F0090 38F803FE90B55A00FC5CD8F03F13E026E007FEC7FC232F7CAD2C>IIIII121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmbx12 17.28 21 /Fi 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: Fj cmbx10 10 23 /Fj 23 118 df45 D<141E143E14FE1307133FB5FCA313CFEA00 0FB3B3A6007FB61280A4213779B630>49 D52 D<001C15C0D81F80130701F8137F90B61280A216005D5D15F05D15804AC7FC14F090C9FC A8EB07FE90383FFFE090B512F89038FC07FC9038E003FFD98001138090C713C0120EC813 E0157F16F0A216F8A21206EA3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15 C06C5B6C491380D9C0071300390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC2538 7BB630>II58 D65 D71 DI80 D87 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF00013 804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217F06E 133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0D9C0 0390C7FC2F3A7EB935>98 D100 D<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F80484813 3F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FCA412 7FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06DB5120001 0F13FC010113E025257DA42C>I105 D<13FFB5FCA412077EB3B3ACB5 12FCA4163A7DB91B>108 D<01FED97FE0EB0FFC00FF902601FFFC90383FFF80020701FF 90B512E0DA1F81903983F03FF0DA3C00903887801F000749DACF007F00034914DE6D48D9 7FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0A44C257DA451>I<01FEEB 7FC000FF903803FFF8020F13FE91381F03FFDA3C011380000713780003497E6D4814C05C A25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801FFC0010F13F8017F13FFD9 FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81491303007F81A300FF1680 A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C6CB5 C7FC011F13FC010113C029257DA430>I<9039FF01FF80B5000F13F0023F13FC9138FE07 FFDAF00113800003496C13C00280EB7FE091C713F0EE3FF8A2EE1FFCA3EE0FFEAA17FC16 1FA217F8163F17F06E137F6E14E06EEBFFC0DAF00313809139FC07FE0091383FFFF8020F 13E0020390C7FC91C9FCACB512FCA42F357EA435>I<9038FE03F000FFEB0FFEEC3FFF91 387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92C7FC91C8FCB3A2B5 12FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F0003007E 1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F812 03C614FC131F9038007FFE140700F0130114007E157E7E157C6C14FC6C14F8EB80019038 F007F090B512C000F8140038E01FF81F257DA426>I<01FFEC3FC0B5EB3FFFA400071401 6C80B3A35DA25DA26C5C6E4813E06CD9C03E13FF90387FFFFC011F13F00103138030257D A435>117 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 0 -237 a Fj(15-451)94 b(HW)31 b(6)3233 b(1)p 0 -204 3900 4 v 0 58 4012 4 v 0 728 4 670 v 482 218 a Fi(15-451)52 b(|)i(Algorithms)g(|)g(Spring)f(2006)1392 335 y Fh(Sleator,)36 b(Golo)m(vin,)h(Kissner)1649 539 y(Homew)m(ork)f(#6)1284 683 y(Due:)50 b(T)-9 b(uesda)m(y)38 b(April)d(18,)j(2006.)p 4008 728 V 0 731 4012 4 v 0 1011 a Fj(Ground)32 b(rules:)125 1213 y Fg(\017)41 b Ff(This)32 b(is)g(an)g(oral)g(presen)n(tation)f(assignmen)n(t.)50 b(Y)-7 b(ou)33 b(should)f(w)n(ork)f(in)i(groups)e(of)h(three.)51 b(A)n(t)33 b(some)f(p)r(oin)n(t)g(b)r(efore)208 1313 y Fj(April)d(14)p Ff(,)d(y)n(our)f(group)g(m)n(ust)h(sign)f(up)h(for)g (a)f(1-hour)g(time)h(slot)g(on)g(the)g(sign)n(up)f(sheet)h(on)g(the)g (course)f(w)n(eb)h(page.)125 1479 y Fg(\017)41 b Ff(Please)30 b(write)i(up)h(\(and)f(turn)g(in)h(during)e(y)n(our)g(presen)n (tation\))g(Solutions)h(to)g(the)h(problems.)49 b(Y)-7 b(ou)32 b(need)h(not)f(b)r(e)208 1578 y(o)n(v)n(erly)25 b(formal)i(or)g(v)n(erb)r(ose.)35 b(Just)28 b(summarize)f(the)h(imp)r (ortan)n(t)f(ideas)g(of)g(y)n(our)g(solution.)125 1744 y Fg(\017)41 b Ff(During)27 b(the)h(presen)n(tations,)e(y)n(ou)h(ma)n (y)g(b)r(e)h(ask)n(ed)e(to)i(explain)f(wh)n(y)g(y)n(our)g(algorithm)f (is)i(correct.)0 1946 y Fj(Problems:)0 2257 y Fe(1)135 b(T)-11 b(ra)l(v)l(eling)46 b(Salesman)g(T)-11 b(ours)44 b(in)h(the)g(Unit)g(Square)0 2391 y Ff(There)27 b(are)g Fd(n)g Ff(p)r(oin)n(ts)h Fd(p)748 2403 y Fc(1)785 2391 y Fd(;)14 b(p)864 2403 y Fc(2)901 2391 y Fd(;)g(:)g(:)g(:)27 b(;)14 b(p)1141 2403 y Fb(n)1214 2391 y Ff(inside)27 b(the)h(unit)h(square)d Fg(f)p Ff(\()p Fd(x;)14 b(y)s Ff(\))23 b Fg(j)g Ff(0)g Fg(\024)f Fd(x)i Fg(\024)e Ff(1)h Fd(;)37 b Ff(0)23 b Fg(\024)f Fd(y)k Fg(\024)d Ff(1)f Fg(g)p Ff(.)37 b(Giv)n(e)27 b(an)g(algorithm)0 2491 y(that)k (constructs)e(a)h(T)-7 b(ra)n(v)n(eling)28 b(Salesman)i(T)-7 b(our)30 b(among)f(these)h(p)r(oin)n(ts)g(whose)g(length)h(is)f(at)g (most)g Fd(a)20 b Ff(+)g Fd(b)3417 2431 y Fg(p)p 3486 2431 50 4 v 60 x Fd(n)p Ff(,)31 b(for)f(some)0 2590 y(constan)n(ts)c Fd(a)h Ff(and)g Fd(b)p Ff(.)36 b(Y)-7 b(our)27 b(algorithm)f(should)g (try)h(to)g(minimize)h Fd(b)p Ff(.)36 b(The)27 b(running)g(time)g(of)g (y)n(our)f(algorithm)g(should)h(b)r(e)0 2690 y Fd(O)r Ff(\()p Fd(n)14 b Ff(log)h Fd(n)p Ff(\).)36 b(\(A)26 b(T)-7 b(ra)n(v)n(eling)24 b(Salesman)h(T)-7 b(our)25 b(is)h(simply)g(a)f(p)r(erm)n(utation)g(of)h(the)g(p)r(oin)n(ts.)36 b(The)26 b(length)g(of)g(the)g(tour)f(is)h(the)0 2790 y(sum)31 b(of)f(the)h(Euclidean)e(distance)i(b)r(et)n(w)n(een)f (successiv)n(e)f(p)r(oin)n(ts,)i(plus)g(the)f(distance)h(b)r(et)n(w)n (een)f(the)h(last)f(p)r(oin)n(t)g(and)h(the)0 2889 y(\014rst)c(one.\))0 3025 y(HINTS:)j(There's)e(a)h(v)n(ery)f(simple)h(algorithm)f(to)h(do)g (this.)42 b(T)-7 b(o)29 b(get)f(started,)h(\014nd)h(a)f(TST)g(for)g (the)3201 2965 y Fg(p)p 3270 2965 V 60 x Fd(n)g Ff(b)n(y)3466 2965 y Fg(p)p 3535 2965 V 60 x Fd(n)g Ff(arra)n(y)e(of)0 3124 y(p)r(oin)n(ts)h(in)f(the)h(unit)h(square.)0 3435 y Fe(2)135 b(Arithmetic)45 b(Progression)h(of)f(Bits)0 3569 y Ff(Giv)n(en)32 b(an)g(arra)n(y)e(of)i Fd(n)g Ff(bits)g Fd(A)p Ff([0])p Fd(;)14 b(A)p Ff([1])p Fd(;)g(:)g(:)g(:)f(A)p Ff([)p Fd(n)22 b Fg(\000)f Ff(1],)33 b(giv)n(e)e(an)h Fd(O)r Ff(\()p Fd(n)14 b Ff(log)h Fd(n)p Ff(\))32 b(algorithm)f(that)i (\014nds)f(an)g(an)g(\\arithmetic)0 3669 y(progression")23 b(of)j(1)g(bits)h(in)f(the)h(arra)n(y)d(\(if)j(there)f(is)g(one\).)37 b(That)26 b(is,)h(if)f(\014nds)h(constan)n(ts)e Fd(a)h Ff(and)g Fd(b)g Ff(\(with)i Fd(b)22 b(>)h Ff(0)j(and)g(0)c Fg(\024)h Fd(a)0 3768 y Ff(and)h Fd(a)12 b Ff(+)g(2)p Fd(b)22 b Fg(\024)h Fd(n)12 b Fg(\000)g Ff(1\))23 b(suc)n(h)h(that)h Fd(A)p Ff([)p Fd(a)p Ff(])e(=)g(1)h(and)g Fd(A)p Ff([)p Fd(a)12 b Ff(+)g Fd(b)p Ff(])23 b(=)f(1)i(and)h Fd(A)p Ff([)p Fd(a)12 b Ff(+)g(2)p Fd(b)p Ff(])22 b(=)g(1)i({)g(or)g(pro)n(v)n (es)e(that)j(no)f(suc)n(h)g(constan)n(ts)0 3868 y(exist.)37 b(HINT:)28 b(Think)g(FFT.)0 4178 y Fe(3)135 b(Mo)l(v)l(e-Half-W)-11 b(a)l(y-T)g(o-F)g(ron)l(t)0 4313 y Ff(In)38 b(class)f(w)n(e)g(analyzed) g(the)i(Mo)n(v)n(e-T)-7 b(o-F)g(ron)n(t)35 b(algorithm)h(for)i(the)g (list)g(up)r(date)g(problem.)68 b(W)-7 b(e)38 b(sho)n(w)n(ed)f(that)h (it's)g(4-)0 4412 y(comp)r(etitiv)n(e.)e(In)25 b(this)h(problem)e(w)n (e'll)h(consider)f(the)i(MHF)g(algorithm)d(that)j(mo)n(v)n(es)e(the)h (accessed)f(elemen)n(t)h(half)g(w)n(a)n(y)f(to)0 4512 y(the)k(fron)n(t.)36 b(More)27 b(sp)r(eci\014cally)-7 b(,)27 b(if)h(an)g(elemen)n(t)f Fd(x)h Ff(in)g(p)r(osition)g Fd(i)f Ff(is)g(accessed)g(\(the)h(p)r(ositions)f(are)g(n)n(um)n(b)r (ered)g(1)p Fd(;)14 b Ff(2)p Fd(;)g(:)g(:)g(:)26 b(;)14 b(n)0 4612 y Ff(from)28 b(fron)n(t)f(to)h(bac)n(k\),)g(then)g Fd(x)h Ff(is)f(sw)n(app)r(ed)g Fg(d)1486 4579 y Fb(i)p Fa(\000)p Fc(1)p 1485 4593 109 4 v 1523 4640 a(2)1604 4612 y Fg(e)g Ff(times)g(with)h(its)f(neigh)n(b)r(or)f(to)h(the)g(fron) n(t.)38 b(In)29 b(other)e(w)n(ords,)g Fd(x)h Ff(mo)n(v)n(es)0 4720 y(past)f Fg(d)227 4687 y Fb(i)p Fa(\000)p Fc(1)p 227 4701 V 265 4748 a(2)346 4720 y Fg(e)g Ff(elemen)n(ts,)h(but)g (still)g(has)f Fg(b)1282 4687 y Fb(i)p Fa(\000)p Fc(1)p 1282 4701 V 1319 4748 a(2)1400 4720 y Fg(c)h Ff(elemen)n(ts)f(in)h (fron)n(t)f(of)h(it.)0 4855 y(Chose)d(a)g(p)r(oten)n(tial)g(function,)h (and)g(c)n(ho)r(ose)e(a)h(constan)n(t)f Fd(c)i Ff(\(as)f(small)g(as)g (p)r(ossible\),)g(and)h(use)f(them)h(to)f(pro)n(v)n(e)f(that)h(MHF)0 4955 y(is)i Fd(c)p Ff(-comp)r(etitiv)n(e.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF