(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: hw7.dvi %%Pages: 2 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f hw7.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2006.04.25:1441 %%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 (hw7.dvi) @start %DVIPSBitmapFont: Fa cmex10 10 1 /Fa 1 85 df<913801FFE0020F13FC027FEBFF8049B612E04981010F15FC499038003FFE D93FF8EB07FFD97FC001007F49486E7E4848C8EA1FE048486F7E48486F7E48486F7E4915 0148486F7E49167E003F177F90CA7EA2481880007E171FA200FE18C048170FB3B3B3A400 78EF07803A537B7F45>84 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmti10 10 15 /Fb 15 122 df<14F8EB07FE90381F871C90383E03FE137CEBF801120148486C5A485A12 0FEBC001001F5CA2EA3F801403007F5C1300A21407485C5AA2140F5D48ECC1C0A2141F15 831680143F1587007C017F1300ECFF076C485B9038038F8E391F0F079E3907FE03FC3901 F000F0222677A42A>97 D<147F903803FFC090380FC1E090381F0070017E137849133839 01F801F83803F003120713E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3 153015381578007C14F0007EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C6 90C7FC1D2677A426>99 D<147F903803FFC090380FC1E090383F00F0017E13785B485A48 5A485A120F4913F8001F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC 5A5AA55AA21530007C14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781 F83803FFE0C690C7FC1D2677A426>101 DII105 D108 DII<147F903803FFC090380FC1F090381F00F8 017E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A 4814FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E 6C13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF09039 3CF0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15C A2D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A 6E485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA212 03A25B1207B512C0A3293580A42A>I<3903C003F0390FF01FFC391E783C0F381C7C703A 3C3EE03F8038383FC0EB7F800078150000701300151CD8F07E90C7FCEAE0FE5BA2120012 015BA312035BA312075BA3120F5BA3121F5BA3123F90C9FC120E212679A423>114 D116 D<13F8D803FEEB01C0D8078FEB03E0390E0F8007121E121C0038140F131F007815C01270 013F131F00F0130000E015805BD8007E133FA201FE14005B5D120149137EA215FE120349 EBFC0EA20201131E161C15F813E0163CD9F003133814070001ECF07091381EF8F03A00F8 3C78E090393FF03FC090390FC00F00272679A42D>I<13F0D803FCEB01C0D8071EEB03E0 D80E1F1307121C123C0038140F4914C01270A249131FD8F07E148012E013FEC648133F16 0012015B5D0003147E5BA215FE00075C5BA214015DA314035D14070003130FEBF01F3901 F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48133F92C7FC147E147C007E13FC3870 01F8EB03E06C485A383C1F80D80FFEC8FCEA03F0233679A428>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmmi7 7 2 /Fc 2 110 df<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230A212 605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA07F0 6C5A11287DA617>105 D<3B07801FC007E03B0FE07FF01FF83B18F0E0F8783C3B30F180 7CE03E903AFB007D801ED860FEEB3F005B49133E00C14A133E5B1201A24848495BA35F48 48485A1830EE01F0A23C0F8003E003E060A218C0933801E180271F0007C013E3933800FF 00000E6D48137C341B7D993B>109 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmr7 7 2 /Fd 2 51 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC15 005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA018039030003 0012065A001FB5FC5A485BB5FCA219267DA521>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmmi10 10 25 /Fe 25 121 df<121C127FEAFF80A5EA7F00121C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>II<1760177017F01601A21603A21607160FA24C7EA216331673166316C3A2ED0183A2ED03 03150683150C160115181530A21560A215C014011580DA03007FA202061300140E140C5C 021FB5FC5CA20260C7FC5C83495A8349C8FC1306A25BA25B13385B01F01680487E000716 FFB56C013F13FF5EA2383C7DBB3E>65 D<0103B77E4916F018FC903B0007F80003FE4BEB 00FFF07F80020FED3FC0181F4B15E0A2141FA25DA2143F19C04B143F1980027F157F1900 92C812FE4D5A4A4A5AEF0FF04AEC1FC005FFC7FC49B612FC5F02FCC7B4FCEF3FC00103ED 0FE0717E5C717E1307844A1401A2130F17035CA2131F4D5A5C4D5A133F4D5A4A4A5A4D5A 017F4BC7FC4C5A91C7EA07FC49EC3FF0B812C094C8FC16F83B397DB83F>I<9339FF8001 C0030F13E0037F9038F80380913A01FF807E07913A07F8000F0FDA1FE0EB079FDA3F8090 3803BF0002FFC76CB4FCD901FC80495A4948157E495A495A4948153E017F163C49C9FC5B 1201484816385B1207485A1830121F4993C7FCA2485AA3127F5BA312FF90CCFCA41703A2 5F1706A26C160E170C171C5F6C7E5F001F5E6D4A5A6C6C4A5A16076C6C020EC8FC6C6C14 3C6C6C5C6CB4495A90393FE00FC0010FB5C9FC010313FC9038007FC03A3D7CBA3B>I<01 03B7FC4916E018F8903B0007F80007FE4BEB00FFF03F80020FED1FC0180F4B15E0F007F0 021F1503A24B15F81801143F19FC5DA2147FA292C8FCA25C18035CA2130119F84A1507A2 130319F04A150FA2010717E0181F4A16C0A2010FEE3F80A24AED7F00187E011F16FE4D5A 4A5D4D5A013F4B5A4D5A4A4A5A057FC7FC017F15FEEE03FC91C7EA0FF049EC7FC0B8C8FC 16FC16C03E397DB845>I<0103B812F05BA290260007F8C7123F4B1407F003E0020F1501 18005DA2141FA25D19C0143FA24B1330A2027F1470190092C7126017E05C16014A495A16 0F49B6FCA25F9138FC000F01031407A24A6DC8FCA201075C18034A130660010F160693C7 FC4A150E180C011F161C18184A1538A2013F5E18F04A4A5AA2017F15074D5A91C8123F49 913803FF80B9FCA295C7FC3C397DB83D>I<0103B812E05BA290260007F8C7123F4B140F F003C0140F18015DA2141FA25D1980143FA25D1760027F14E095C7FC92C75AA24A1301A2 4A495A16070101141F91B6FC94C8FCA2903903FC001F824A130EA21307A24A130CA2010F 141CA24A90C9FCA2131FA25CA2133FA25CA2137FA291CBFC497EB612C0A33B397DB835> II<0103B6FC5B5E90260007FCC8FC5D5D140FA25D A2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA213071840 4A15C0A2010F150118804A1403A2011F16005F4A1406170E013F151E171C4A143C177C01 7F5D160391C7120F49EC7FF0B8FCA25F32397DB839>76 D<92391FE00380DBFFFC130002 036D5A91390FE01F8F91393F0007DF027EEB01FE02F81300495A4948147E177C4948143C 495AA2011F153891C8FCA3491530A28094C7FC80806D7E14FEECFFE06D13FE6DEBFFC06D 14F06D806D80021F7F02037FEC003F03037F1500167F163F161FA3120C160FA2001C151F 94C7FCA3003C153EA25E003E5D127E007F4A5A6D495A6DEB0FC0D8F9F0495AD8F0FE01FE C8FC39E03FFFF8010F13E0D8C00190C9FC313D7CBA33>83 D<267FFFFC91383FFFC0B55D A2000390C83807FC006C48ED03E06060000094C7FC5F17065FA25F6D5DA26D5D17E05F4C 5AA24CC8FC6E1306A2013F5C161C16185EA25E6E5BA2011F495A150393C9FC1506A25D6E 5AA2010F5B157015605DA2ECE18002E3CAFC14F3EB07F614FE5C5CA25C5CA26D5AA25C91 CBFC3A3B7CB830>86 D<49B500F890387FFFF095B5FC1AE0D90003018090380FFC004BC7 13E00201ED07804EC7FC6E6C140E606F5C705B606F6C485A4D5A031F91C8FCEEE0065F6F 6C5A5F03075B705A16F96FB45A94C9FC6F5AA36F7EA34B7FED037F9238063FC0150E4B6C 7E1538ED700F03E07F15C04A486C7EEC0300020613034A805C4A6D7E14704A1300494880 495A49C86C7E130E011E153F017E4B7ED803FF4B7E007F01E0011FEBFFC0B5FC6144397E B845>88 DI<163FED1FFFA3ED007F167EA216FE A216FCA21501A216F8A21503A216F0A21507A2027E13E0903803FF8790380FC1CF90381F 00EF017EEB7FC049133F485A4848131F000715805B000F143F485A1600485A5D127F90C7 127EA215FE5A485CA21401A248ECF80CA21403161CEDF0181407007C1538007E010F1330 003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F00283B7DB92B >100 DI107 D109 DI<3903E001F83907F807FE390E3C1E07 391C3E381F3A183F703F800038EBE07F0030EBC0FF00705B00601500EC007E153CD8E07F 90C7FCEAC07EA2120013FE5BA312015BA312035BA312075BA3120F5BA3121F5B0007C9FC 21267EA425>114 D<13F8D803FE1438D8070F147C000E6D13FC121C1218003814011230 D8701F5C12601503EAE03F00C001005B5BD8007E1307A201FE5C5B150F1201495CA2151F 120349EC80C0A2153F1681EE0180A2ED7F0303FF130012014A5B3A00F8079F0E90397C0E 0F1C90393FFC07F8903907F001F02A267EA430>117 D<01F8EB03C0D803FEEB07E0D807 0F130F000E018013F0121C12180038140700301403D8701F130112601500D8E03F14E000 C090C7FC5BEA007E16C013FE5B1501000115805B150316001203495B1506150E150C151C 151815385D00015C6D485A6C6C485AD97E0FC7FCEB1FFEEB07F024267EA428>I<01F816 F0D803FE9138E001F8D8070F903801F003000ED9800314FC121C12180038020713010030 EDE000D8701F167C1260030F143CD8E03F163800C001005B5BD8007E131F183001FE5C5B 033F1470000117604991C7FCA218E000034A14C049137E17011880170318005F03FE1306 170E000101015C01F801BF5B3B00FC039F8070903A7E0F0FC0E0903A1FFC03FFC0902703 F0007FC7FC36267EA43B>I<903907E001F090391FF807FC9039783E0E0F9039E01F1C1F D801C09038383F803A03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4A C7FC1218A2C7123FA292C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5B D87F81143801835C00FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391F F00FFC3907C003F029267EA42F>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmbx12 14.4 21 /Ff 21 118 df44 D<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF8 00C7FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI< 91380FFFC091B512FC0107ECFF80011F15E090263FF8077F9026FF800113FC4848C76C7E D803F86E7E491680D807FC8048B416C080486D15E0A4805CA36C17C06C5B6C90C75AD801 FC1680C9FC4C13005FA24C5A4B5B4B5B4B13C04B5BDBFFFEC7FC91B512F816E016FCEEFF 80DA000713E0030113F89238007FFE707E7013807013C018E07013F0A218F8A27013FCA2 18FEA2EA03E0EA0FF8487E487E487EB57EA318FCA25E18F891C7FC6C17F0495C6C4816E0 01F04A13C06C484A1380D80FF84A13006CB44A5A6CD9F0075BC690B612F06D5D011F1580 010302FCC7FCD9001F1380374F7ACD43>I66 D<932601FFFCEC01C0047FD9FFC013030307B600F81307033F03FE131F 92B8EA803F0203DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A01800203B5FC 494848C9FC4901F8824949824949824949824949824990CA7E494883A2484983485B1B7F 485B481A3FA24849181FA3485B1B0FA25AA298C8FC5CA2B5FCAE6C057FB712E0A280A36C 94C7003FEBC000A36C7FA36C7FA27E6C7FA26C7F6C7FA26D7E6D7F6D7F6D6D5E6D7F6D01 FC93B5FC6D13FF6D6C6D5C6E01F0EC07FB020F01FEEC1FF10203903AFFF001FFE0020091 B6EAC07F033FEE001F030703FC1307DB007F02E01301040149CAFC5B5479D26A>71 D80 D97 DI<4DB47E0407B5FCA5EE001F1707B3A4913801FFE0021F13FC91B6FC010315C7 010F9038E03FE74990380007F7D97FFC0101B5FC49487F4849143F484980485B83485B5A 91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F6C6D5C7E6C6D5C6C6D49B5FC6D6C 4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B5128F0101ECFE0FD9003F13F80203 01C049C7FC41547CD24B>100 D<913803FFC0023F13FC49B6FC010715C04901817F903A 3FFC007FF849486D7E49486D7E4849130F48496D7E48178048497F18C0488191C7FC4817 E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E1403 7E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0FFF C03FF8010390B55A010015C0021F49C7FC020113F034387CB63D>I103 DI<137F497E000313E0487FA2487FA76C5BA26C5BC6 13806DC7FC90C8FCADEB3FF0B5FCA512017EB3B3A6B612E0A51B547BD325>I108 DII<913801FFE0021F13FE91B612C0010315F0010F9038807FFC903A 1FFC000FFED97FF86D6C7E49486D7F48496D7F48496D7F4A147F48834890C86C7EA24883 A248486F7EA3007F1880A400FF18C0AC007F1880A3003F18006D5DA26C5FA26C5F6E147F 6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE011F90C7FC903A0FFF807FFC6D90B5 5A010015C0023F91C8FC020113E03A387CB643>I<90397FE003FEB590380FFF80033F13 E04B13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02 FEEB3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537>114 D<143EA6147EA414FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426 003FFEC8FCB3A9EE07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEBFFF8 6D6C5B021F5B020313802A4D7ECB34>116 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmr10 10 62 /Fg 62 123 df12 D14 D<001C131C007F137F39FF80 FF80A26D13C0A3007F137F001C131C00001300A40001130101801380A200031303010013 00485B00061306000E130E485B485B485B006013601A197DB92A>34 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485A A212075B120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F1207 7F1203A26C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12 C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA214 80A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2 485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<121C127FEAFF80A213C0A312 7F121C1200A412011380A2120313005A1206120E5A5A5A12600A19798817>44 DI<121C127FEAFF80A5EA7F00121C0909798817>I48 DII<1538A2157815F8A2140114031407A2 140F141F141B14331473146314C313011483EB030313071306130C131C13181330137013 6013C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E01 03B512F8A325397EB82A>52 D57 D<121C127FEAFF80A5EA7F 00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317>I<007FB812F8B912FCA3CC FCAEB912FCA36C17F836167B9F41>61 D<1538A3157CA315FEA34A7EA34A6C7EA202077F EC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F15 01A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E 7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>65 DI<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03 FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F48 48150FA248481507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A312 3F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE0 5C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D 7BBA3C>III< B812F8A30001903880001F6C90C71201EE00FC177C173C171CA2170CA4170E1706A2ED01 80A21700A41503A21507151F91B5FCA3EC001F15071503A21501A692C8FCAD4813C0B612 C0A32F397DB836>IIII76 DII80 D82 DI<003FB812E0A3D9C003EB001F273E0001FE 130348EE01F00078160000701770A300601730A400E01738481718A4C71600B3B0913807 FF80011FB612E0A335397DB83C>II< B5D8FC07B5D8F001B5FCA30007902780001FFEC7EA1FF86C48C7D80FF8EC07E000010307 ED03C01B807F6C6F6C1500A26E5F017F6E6C1406A280013F4A6C5CA280011F4A6D5BEE06 7FA26D6C010E6D5BEE0C3FA26D6C011C6D5BEE181FA26D6C6F5BEE300FA26D6C6F485AEE 6007A26D6C4CC7FC9338C003FCA203805D913B7F818001FE06A203C1150EDA3FC3C7EAFF 0CA203E3151CDA1FE6EC7F98A215F6DA0FFCEC3FF0A302075E4B141FA202035E4B140FA2 02015E4B1407A2020093C8FC4B80503B7EB855>87 D89 D<3901800180000313033907000700000E130E485B0018131800381338 003013300070137000601360A200E013E0485BA400CE13CE39FF80FF806D13C0A3007F13 7FA2393F803F80390E000E001A1974B92A>92 D97 DIIII<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213 FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I< ED03F090390FF00FF890393FFC3C3C9039F81F707C3901F00FE03903E007C03A07C003E0 10000FECF000A248486C7EA86C6C485AA200075C6C6C485A6D485A6D48C7FC38073FFC38 060FF0000EC9FCA4120FA213C06CB512C015F86C14FE6CECFF804815C03A0F80007FE048 C7EA0FF0003E140348140116F8481400A56C1401007C15F06CEC03E0003F1407D80F80EB 0F80D807E0EB3F003901FC01FC39007FFFF0010790C7FC26387EA52A>IIIIII<2703F00FF0EB1FE000FFD93FFCEB7FF8913AF03F01E07E903BF1C01F8380 3F3D0FF3800FC7001F802603F70013CE01FE14DC49D907F8EB0FC0A2495CA3495CB3A348 6C496CEB1FE0B500C1B50083B5FCA340257EA445>I<3903F00FF000FFEB3FFCECF03F90 39F1C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A3486C497EB500C1B51280 A329257EA42E>II<3903F01FE000FFEB7FF89038F1E07E9039F3801F 803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC150016FEA3167FAA16FEA3 ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F009038F1E07E9038F0FF F8EC1FC091C8FCAB487EB512C0A328357EA42E>II<3807E01F00FFEB7FC09038E1E3 E09038E387F0380FE707EA03E613EE9038EC03E09038FC0080491300A45BB3A2487EB512 F0A31C257EA421>II<1318A51338A31378A313F8120112031207001FB5FCB6FCA2D801F8C7FCB215 C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB220>IIIIII<003FB5 12FCA2EB8003D83E0013F8003CEB07F00038EB0FE012300070EB1FC0EC3F800060137F15 0014FE495AA2C6485A495AA2495A495A495AA290387F000613FEA2485A485A0007140E5B 4848130C4848131CA24848133C48C7127C48EB03FC90B5FCA21F247EA325>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmsy10 10 7 /Fh 7 107 df15 D<020FB6128091B712C01303010F1680D91FF8C9FCEB7F8001FECAFCEA01F8 485A485A485A5B48CBFC5A123E123C127CA2127812F8A25AA77EA21278127CA2123C123E 123F7E6C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF86DB71280010316C01300020F158091 CAFCAD001FB812804817C0A26C1780324279B441>18 D<127012FCB4FCEA7FC0EA1FF0EA 07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007F C0ED1FF0ED07FCED01FF9238007FC0EE1FF0EE07FCEE01FF9338007FC0171F177F933801 FF80933807FC00EE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0 EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270 CCFCAD007FB81280B912C0A26C1780324279B441>21 D<91381FFFFE91B6FC1303010F14 FED91FF0C7FCEB7F8001FEC8FCEA01F8485A485A485A5B48C9FCA2123EA25AA2127812F8 A25AA2B712FE16FFA216FE00F0C9FCA27EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7E EA00FEEB7F80EB1FF06DB512FE010314FF1300021F13FE283279AD37>50 D102 D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F 80130FB3A7801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00495A495A495A5C13 0F5CB3A7131F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D537ABD2A>I<126012 F0B3B3B3B3A91260045377BD17>106 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmbx12 12 32 /Fi 32 122 df35 D44 D46 D48 D50 D<163FA25E5E5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E 147E147C14F8EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B 48C7FC123E5A12FCB91280A5C8000F90C7FCAC027FB61280A531417DC038>52 D<4AB47E021F13F0027F13FC49B6FC01079038807F8090390FFC001FD93FF014C0494813 7F4948EBFFE048495A5A1400485A120FA248486D13C0EE7F80EE1E00003F92C7FCA25B12 7FA2EC07FC91381FFF8000FF017F13E091B512F89039F9F01FFC9039FBC007FE9039FF80 03FF17804A6C13C05B6F13E0A24915F0A317F85BA4127FA5123FA217F07F121FA2000F4A 13E0A26C6C15C06D4913806C018014006C6D485A6C9038E01FFC6DB55A011F5C010714C0 010191C7FC9038003FF02D427BC038>54 D<121E121F13FC90B712FEA45A17FC17F817F0 17E017C0A2481680007EC8EA3F00007C157E5E00785D15014B5A00F84A5A484A5A5E151F C848C7FC157E5DA24A5A14035D14074A5AA2141F5D143FA2147F5D14FFA25BA35B92C8FC A35BA55BAA6D5A6D5A6D5A2F447AC238>I58 D68 D71 DI75 D77 D83 D<903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7E A26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC0100 0313E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013E EBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 D99 D101 DI<137C48B4FC4813804813C0A2 4813E0A56C13C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA5 18467CC520>105 D107 DI<90277F80 07FEEC0FFCB590263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC0F E03FF8913D8FC00FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02 F86D496D7EA24A5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F80 07FEB590383FFF8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE6C 139E14BC02F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90387F807FB53881FFE0028313F0028F13F8 ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35C B3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B51287000314FF120F381FF00338 3FC00049133F48C7121F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014FF6C 14C015F06C14FC6C800003806C15806C7E010F14C0EB003F020313E0140000F0143FA26C 141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F0 3F13E026E007FEC7FC232F7CAD2C>IIIII121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmbx12 17.28 21 /Fj 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: Fk cmbx10 10 22 /Fk 22 116 df45 D<141E143E14FE1307133FB5FCA313CFEA00 0FB3B3A6007FB61280A4213779B630>49 DI52 D<001C15C0D81F80130701F8 137F90B61280A216005D5D15F05D15804AC7FC14F090C9FCA8EB07FE90383FFFE090B512 F89038FC07FC9038E003FFD98001138090C713C0120EC813E0157F16F0A216F8A21206EA 3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15C06C5B6C491380D9C0071300 390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC25387BB630>I<123C123EEA3FE0 90B71280A41700485D5E5E5EA25E007CC7EA0FC000784A5A4BC7FC00F8147E48147C15FC 4A5A4A5AC7485A5D140F4A5A143F92C8FC5C147E14FE1301A2495AA31307A2130F5CA213 1FA5133FA96D5A6D5A6D5A293A7BB830>55 D58 D72 D80 D82 DI87 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF0 0013804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217 F06E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0 D9C00390C7FC2F3A7EB935>98 D100 D<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F8048 48133F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FC A4127FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06DB512 00010F13FC010113E025257DA42C>I105 D<13FFB5FCA412077EB3B3 ACB512FCA4163A7DB91B>108 D<01FED97FE0EB0FFC00FF902601FFFC90383FFF800207 01FF90B512E0DA1F81903983F03FF0DA3C00903887801F000749DACF007F00034914DE6D 48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0A44C257DA451>I<01 FEEB7FC000FF903803FFF8020F13FE91381F03FFDA3C011380000713780003497E6D4814 C05CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801FFC0010F13F8017F13 FFD9FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81491303007F81A300FF 1680A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C 6CB5C7FC011F13FC010113C029257DA430>I<9038FE03F000FFEB0FFEEC3FFF91387C7F 809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92C7FC91C8FCB3A2B512FEA4 22257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F0003007E130100 7C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F81203C614 FC131F9038007FFE140700F0130114007E157E7E157C6C14FC6C14F8EB80019038F007F0 90B512C000F8140038E01FF81F257DA426>I E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 0 -237 a Fk(15-451)94 b(HW)31 b(7)3233 b(1)p 0 -204 3900 4 v 0 58 4012 4 v 0 728 4 670 v 482 218 a Fj(15-451)52 b(|)i(Algorithms)g(|)g(Spring)f(2006)1392 335 y Fi(Sleator,)36 b(Golo)m(vin,)h(Kissner)1649 539 y(Homew)m(ork)f(#7)1204 683 y(Due:)51 b(Ma)m(y)38 b(4,)f(2006,)h(start) f(of)h(class.)p 4008 728 V 0 731 4012 4 v 0 1011 a Fk(Some)30 b(Reminders:)125 1189 y Fh(\017)41 b Fg(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 1289 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 1443 y Fh(\017)41 b Fg(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 1542 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 1642 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 1796 y Fh(\017)41 b Fg(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 1895 y(recitation)26 b(section)i(and)f(y)n(our)f(Andrew)i(ID.)0 2073 y Fk(Problems:)0 2208 y Fg(Note:)42 b(When)30 b(attempting)g(to)g(sho)n(w)f(a)h(problem) f(is)h(NP-complete)g(b)n(y)f(reducing)h(a)f(kno)n(wn)g(NP-complete)h (problem)f(to)0 2308 y(y)n(our)d(problem,)h(y)n(ou)g(ma)n(y)g(use)h (only)f(those)g(NP-complete)g(problems)g(co)n(v)n(ered)f(in)h(lecture)h (or)f(in)g(the)h(textb)r(o)r(ok.)0 2613 y Ff(1)135 b(Graduation)0 2748 y Fg(Cran)n(b)r(erry-Melon)19 b(Univ)n(ersit)n(y)h(has)h Fe(n)g Fg(courses.)34 b(In)21 b(order)f(to)h(graduate,)h(a)e(studen)n (t)i(m)n(ust)g(satisfy)f(sev)n(eral)e(requiremen)n(ts.)0 2847 y(Eac)n(h)37 b(requiremen)n(t)g(is)g(of)h(the)g(form)g(\\y)n(ou)e (m)n(ust)i(tak)n(e)g(at)f(least)h Fe(k)j Fg(courses)36 b(from)h(subset)h Fe(S)5 b Fg(".)67 b(The)38 b(problem)f(is)h(to)0 2947 y(determine)27 b(whether)g(or)g(not)g(a)g(giv)n(en)f(studen)n(t)h (can)g(graduate.)35 b(The)28 b(tric)n(ky)e(part)h(is)g(that)g(an)n(y)g (giv)n(en)f(course)g(cannot)h(b)r(e)0 3047 y(used)f(to)n(w)n(ards)f (satisfying)h(m)n(ultiple)g(requiremen)n(ts.)36 b(F)-7 b(or)26 b(example)g(if)g(one)g(requiremen)n(t)g(states)g(that)g(y)n(ou) g(m)n(ust)h(tak)n(e)e(at)0 3146 y(least)k(t)n(w)n(o)g(courses)f(from)h Fh(f)p Fe(A;)14 b(B)t(;)g(C)6 b Fh(g)p Fg(,)30 b(and)f(a)g(second)g (requiremen)n(t)f(states)i(that)f(y)n(ou)g(m)n(ust)h(tak)n(e)e(at)i (least)f(t)n(w)n(o)g(courses)0 3246 y(from)e Fh(f)p Fe(C)q(;)14 b(D)r(;)g(E)5 b Fh(g)p Fg(,)28 b(then)g(a)f(studen)n(t)h(who)f(had)h (tak)n(en)f(just)h Fh(f)p Fe(B)t(;)14 b(C)q(;)g(D)r Fh(g)27 b Fg(w)n(ould)g(not)h(y)n(et)f(b)r(e)h(able)f(to)h(graduate.)0 3381 y(Y)-7 b(our)35 b(job)h(is)g(to)g(giv)n(e)f(a)g(p)r (olynomial-time)h(algorithm)e(for)i(the)g(follo)n(wing)f(problem.)61 b(Giv)n(en)36 b(a)f(list)h(of)g(requiremen)n(ts)0 3481 y Fe(r)37 3493 y Fd(1)75 3481 y Fe(;)14 b(r)149 3493 y Fd(2)186 3481 y Fe(;)g(:)g(:)g(:)28 b(;)14 b(r)422 3493 y Fc(m)516 3481 y Fg(\(where)30 b(eac)n(h)g(requiremen)n(t)g Fe(r)1483 3493 y Fc(i)1542 3481 y Fg(is)g(of)h(the)g(form:)42 b(\\y)n(ou)30 b(m)n(ust)g(tak)n(e)g(at)h(least)f Fe(k)3044 3493 y Fc(i)3103 3481 y Fg(courses)f(from)h(set)h Fe(S)3776 3493 y Fc(i)3803 3481 y Fg("\),)0 3580 y(and)c(giv)n(en)g(a)g(list)h Fe(L)f Fg(of)h(courses)e(tak)n(en)h(b)n(y)g(some)g(studen)n(t,)h (determine)g(if)g(that)g(studen)n(t)g(can)f(graduate.)0 3886 y Ff(2)135 b(Graduation,)45 b(P)l(art)h(2)0 4020 y Fg(Cran)n(b)r(erry-Melon)27 b(Univ)n(ersit)n(y)h(has)h(switc)n(hed)g (to)h(a)f(less)f(draconian)g(p)r(olicy)i(for)e(graduation)g(requiremen) n(ts)g(than)i(that)0 4120 y(used)21 b(in)g(the)g(previous)f(problem.)34 b(As)21 b(b)r(efore,)h(there)f(is)g(a)f(list)h(of)g(requiremen)n(ts)f Fe(r)2559 4132 y Fd(1)2597 4120 y Fe(;)14 b(r)2671 4132 y Fd(2)2708 4120 y Fe(;)g(:)g(:)g(:)28 b(;)14 b(r)2944 4132 y Fc(m)3007 4120 y Fg(,)22 b(where)f(eac)n(h)f(requiremen)n(t)0 4219 y Fe(r)37 4231 y Fc(i)90 4219 y Fg(is)26 b(of)f(the)g(form:)36 b(\\y)n(ou)24 b(m)n(ust)h(tak)n(e)f(at)i(least)e Fe(k)1542 4231 y Fc(i)1596 4219 y Fg(courses)f(from)i(set)g Fe(S)2252 4231 y Fc(i)2280 4219 y Fg(".)36 b(Ho)n(w)n(ev)n(er,)23 b(unlik)n(e)i(the)h(case)e(b)r(efore,)i(a)f(studen)n(t)0 4319 y Fb(may)39 b Fg(use)g(the)f(same)g(course)g(to)g(ful\014ll)h(sev) n(eral)e(requiremen)n(ts.)69 b(F)-7 b(or)38 b(example,)i(if)g(one)e (requiremen)n(t)f(stated)i(that)f(a)0 4419 y(studen)n(t)29 b(m)n(ust)f(tak)n(e)f(at)h(least)g(one)g(course)f(from)h Fh(f)p Fe(A;)14 b(B)t(;)g(C)6 b Fh(g)p Fg(,)28 b(another)f(required)g (at)h(least)g(one)g(course)f(from)g Fh(f)p Fe(C)q(;)14 b(D)r(;)g(E)5 b Fh(g)p Fg(,)0 4518 y(and)26 b(a)g(third)h(required)e (at)i(least)f(one)g(course)f(from)h Fh(f)p Fe(A;)14 b(F)r(;)g(G)p Fh(g)p Fg(,)27 b(then)g(a)f(studen)n(t)g(w)n(ould)g(only)g(ha)n(v)n(e)f (to)i(tak)n(e)e Fe(A)i Fg(and)f Fe(C)33 b Fg(to)0 4618 y(graduate.)0 4753 y(No)n(w,)28 b(consider)f(an)h(incoming)f(freshman)h (in)n(terested)g(in)g(\014nding)g(the)h Fb(minimum)f Fg(n)n(um)n(b)r(er)f(of)h(courses)f(that)h(he)g(\(or)g(she\))0 4853 y(needs)f(to)h(tak)n(e)f(in)h(order)e(to)h(graduate.)60 5041 y(\(a\))42 b(Pro)n(v)n(e)27 b(that)i(the)h(problem)f(faced)h(b)n (y)f(this)g(freshman)g(is)h(NP-hard,)e(ev)n(en)h(if)h(eac)n(h)f Fe(k)2904 5053 y Fc(i)2961 5041 y Fg(is)h(equal)f(to)g(1.)42 b(Sp)r(eci\014cally)-7 b(,)208 5141 y(consider)33 b(the)i(follo)n(wing) e(decision)h(problem:)50 b(giv)n(en)33 b Fe(n)h Fg(items)h(lab)r(eled)f (1)p Fe(;)14 b Fg(2)p Fe(;)g(:)g(:)g(:)27 b(;)14 b(n)p Fg(,)36 b(giv)n(en)d Fe(m)i Fg(subsets)f(of)g(these)208 5240 y(items)f Fe(S)486 5252 y Fd(1)524 5240 y Fe(;)14 b(S)612 5252 y Fd(2)649 5240 y Fe(;)g(:)g(:)g(:)27 b(;)14 b(S)898 5252 y Fc(m)961 5240 y Fg(,)35 b(and)f(giv)n(en)e(an)i(in)n (teger)e Fe(k)s Fg(,)j(do)r(es)f(there)f(exist)h(a)f(set)g Fe(S)39 b Fg(of)33 b(at)h(most)f Fe(k)k Fg(items)d(suc)n(h)f(that)208 5340 y Fh(j)p Fe(S)300 5278 y Fa(T)383 5340 y Fe(S)434 5352 y Fc(i)462 5340 y Fh(j)23 b(\025)f Fg(1)28 b(for)f(all)g Fe(S)958 5352 y Fc(i)986 5340 y Fg(.)37 b(Pro)n(v)n(e)25 b(that)j(this)g(problem)f(is)g(NP-complete)g(\(don't)h(forget)f(to)g (pro)n(v)n(e)f(it)i(is)g(in)g(NP\).)p eop %%Page: 2 2 2 1 bop 0 -237 a Fk(15-451)94 b(HW)31 b(7)3233 b(2)p 0 -204 3900 4 v 55 83 a Fg(\(b\))43 b(Sho)n(w)26 b(ho)n(w)g(y)n(ou)f (could)i(use)f(a)g(p)r(olynomial-time)g(algorithm)g(for)g(the)h(ab)r(o) n(v)n(e)e(decision)h(problem)g(to)h(also)e(solv)n(e)h(the)208 183 y(searc)n(h-v)n(ersion)e(of)j(the)h(problem)f(\(i.e.,)h(actually)f (\014nd)h(a)g(minim)n(um-sized)f(set)h(of)f(courses)g(to)g(tak)n(e\).) 65 349 y(\(c\))42 b(W)-7 b(e)24 b(could)h(de\014ne)f(a)g Fb(fr)l(actional)i Fg(v)n(ersion)d(of)h(the)h(graduation)e(problem)h(b) n(y)g(imagining)g(that)g(in)h(eac)n(h)e(course)h(tak)n(en,)208 448 y(a)31 b(studen)n(t)i(gets)e(a)h(grade)f(b)r(et)n(w)n(een)h(0.00)e (and)i(1.00,)g(and)g(that)h(requiremen)n(t)e Fe(r)2792 460 y Fc(i)2852 448 y Fg(no)n(w)g(states)h(\\the)g(sum)g(of)g(y)n(our) 208 548 y(grades)27 b(in)j(courses)e(tak)n(en)h(from)g(set)h Fe(S)1465 560 y Fc(i)1522 548 y Fg(m)n(ust)f(b)r(e)h(at)f(least)g Fe(k)2186 560 y Fc(i)2214 548 y Fg(")g(\(courses)g(not)g(tak)n(en)g (coun)n(t)g(as)g(0\).)42 b(The)30 b(studen)n(t)208 648 y(no)n(w)h(w)n(an)n(ts)g(to)g(kno)n(w)g(the)h(least)g(total)f(w)n(ork)g (needed)h(to)f(graduate,)h(de\014ned)g(as)f(the)h(the)g(minim)n(um)h (sum)f(of)f(all)208 747 y(grades)26 b(needed)h(to)h(satisfy)f(all)g (the)h(requiremen)n(ts.)208 880 y(Sho)n(w)d(ho)n(w)h(this)g(problem)g (can)f(b)r(e)i(solv)n(ed)e(using)h Fb(line)l(ar)j(pr)l(o)l(gr)l(amming) p Fg(.)37 b(Be)26 b(sure)f(to)h(sp)r(ecify)h(what)f(the)g(v)-5 b(ariables)208 980 y(are,)26 b(what)i(the)g(constrain)n(ts)e(are,)h (and)g(what)h(y)n(ou)e(are)h(trying)g(to)g(minimize)i(or)d(maximize.)0 1290 y Ff(3)135 b(Building)45 b(the)g(Bom)l(b)0 1425 y Fg(It)27 b(is)f(1944,)e(and)i(y)n(ou)g(are)f(a)h(ph)n(ysicist)f(w)n (orking)g(on)h(the)g(Manhattan)g(pro)5 b(ject,)26 b(attempting)h(to)f (build)g(an)g(atomic)g(b)r(om)n(b.)0 1524 y(In)e(the)h(pro)r(cess,)e(y) n(ou)h(will)g(b)r(e)g(enric)n(hing)f(a)h(lot)g(of)g(uranium.)35 b(The)25 b(thing)f(ab)r(out)g(this)g(enric)n(hed)g(uranium)f(is,)i(if)g (to)r(o)e(m)n(uc)n(h)0 1624 y(of)29 b(it)h(gets)f(close)g(together,)g (it)g(will)h(explo)r(de,)g(making)e(y)n(ou)h(v)n(ery)f(unhapp)n(y)-7 b(.)42 b(Naturally)-7 b(,)29 b(y)n(ou)g(will)g(tak)n(e)g(precautions)f (to)0 1723 y(mak)n(e)f(sure)g(y)n(ou)g(don't)g(get)h(blo)n(wn)f(up,)h (though)f(ideally)g(y)n(ou'd)g(lik)n(e)h(to)f(do)g(it)h(as)f(inexp)r (ensiv)n(ely)g(as)g(p)r(ossible...)60 1942 y(\(a\))42 b(The)30 b(\014rst)h(approac)n(h)e(is)h(to)h(tak)n(e)f(y)n(our)f (storage)g(facilities)i(as)f(\014xed,)i(and)e(place)g(the)i(uranium)e (in)h(lo)r(cations)f(that)208 2041 y(are)d(su\016cien)n(tly)h(spaced)f (out.)38 b(T)-7 b(o)28 b(mak)n(e)f(this)i(concrete,)e(w)n(e)h(will)g (mo)r(del)g(the)h(storage)d(facilit)n(y)i(as)f(an)h(undirected)208 2141 y(graph)k Fe(G)i Fg(=)e(\()p Fe(V)5 b(;)14 b(E)5 b Fg(\),)36 b(where)e Fe(V)52 b Fg(is)34 b(the)g(set)g(of)f(lo)r (cations)g(at)h(whic)n(h)f(w)n(e)h(can)f(store)g(uranium.)55 b(The)33 b(edges)g(ha)n(v)n(e)208 2241 y(w)n(eigh)n(ts)23 b Fe(w)r Fg(\()p Fe(e)p Fg(\),)i(whic)n(h)f(induce)h(a)e(distance)h (metric)g(on)g(the)g(graph,)g(in)g(whic)n(h)g Fe(d)p Fg(\()p Fe(u;)14 b(v)s Fg(\))24 b(is)g(the)h(cost)e(of)h(the)g(minim)n (um)208 2340 y(w)n(eigh)n(t)j(path)i(from)f Fe(u)f Fg(to)i Fe(v)s Fg(.)39 b(Y)-7 b(ou)28 b(are)g(also)f(giv)n(en)g(a)h(parameter)f Fe(D)r Fg(.)39 b(Putting)28 b(uranium)g(at)g(t)n(w)n(o)g(lo)r(cations)f Fe(u)h Fg(and)208 2440 y Fe(v)g Fg(suc)n(h)d(that)g Fe(d)p Fg(\()p Fe(u;)14 b(v)s Fg(\))24 b Fe(<)e(D)27 b Fg(will)f(cause)e(an)h (explosion.)35 b(Ho)n(w)n(ev)n(er)23 b(y)n(ou'd)i(lik)n(e)f(to)h(place) g(as)f(man)n(y)h(units)g(of)g(uranium)208 2540 y(as)e(p)r(ossible)h(do) n(wn,)h(sub)5 b(ject)25 b(to)f(the)h(constrain)n(t)e(of)h(not)h(b)r (eing)f(blo)n(wn)g(up.)37 b(Deriv)n(e)23 b(a)h(p)r(olynomial)g(time)h (algorithm)208 2639 y(to)31 b(maximize)f(the)i(n)n(um)n(b)r(er)f(of)g (units)h(of)f(uranium)g(y)n(ou)f(can)h(place)g(\(the)h(output)f(is)g (the)h(set)f(of)g(lo)r(cations)g(where)208 2739 y(y)n(ou'd)c(put)h (it\),)g(or)f(sho)n(w)g(that)g(this)h(problem)f(is)h(NP-hard.)55 2905 y(\(b\))43 b(Another)21 b(w)n(a)n(y)f(to)h(con)n(trol)f(the)i(n)n (uclear)e(c)n(hain)h(reaction)f(is)h(with)h(con)n(trol)e(ro)r(ds)g (that)i(stop)f(the)h(cascading)e(neutrons.)208 3004 y(So)30 b(y)n(ou)h(can)f(imagine)h(another)f(undirected)h(graph)f Fe(G)f Fg(=)g(\()p Fe(V)5 b(;)14 b(E)5 b Fg(\))31 b(where)g(y)n(ou)f (plan)h(to)g(place)g(uranium)f(at)h(ev)n(ery)208 3104 y(lo)r(cation)i(in)i Fe(V)19 b Fg(.)57 b(This)35 b(is)f(safe)g(if)h (and)f(only)g(if)h(y)n(ou)f(place)g(con)n(trol)f(ro)r(ds)h(do)n(wn)g (at)g(a)g(set)g(of)h(lo)r(cations)e Fe(X)41 b Fh(\022)34 b Fe(V)208 3204 y Fg(suc)n(h)27 b(that)i(eac)n(h)e Fe(v)h Fh(2)c Fe(V)47 b Fg(is)28 b(either)h(in)f Fe(X)35 b Fg(or)27 b(has)h(a)f(neigh)n(b)r(or)h(in)g Fe(X)7 b Fg(.)38 b(Y)-7 b(our)28 b(goal)f(is)h(the)h(mak)n(e)e(the)i(site)f(safe)g(while)208 3303 y(minimizing)36 b(the)h(size)e(of)h Fe(X)7 b Fg(.)62 b(Deriv)n(e)36 b(a)f(p)r(olynomial)h(time)h(algorithm)d(to)i(minimize)h Fh(j)p Fe(X)7 b Fh(j)p Fg(,)38 b(or)d(sho)n(w)g(that)i(this)208 3403 y(problem)27 b(is)g(NP-hard.)65 3569 y(\(c\))42 b(A)e(third)g(w)n(a)n(y)e(to)i(deal)f(with)h(the)h(uranium)e(problem)g (is)h(to)g(reinforce)e(the)i(w)n(alls)f(with)i(material)e(that)h(stops) 208 3669 y(neutrons.)35 b(Here)23 b(y)n(ou)g(ha)n(v)n(e)f(an)i (undirected)g(graph)e Fe(G)i Fg(=)e(\()p Fe(V)5 b(;)14 b(E)5 b Fg(\))25 b(with)f(edge)f(w)n(eigh)n(ts)g Fe(w)j Fg(and)e(with)g(a)f(set)h Fe(Y)42 b Fh(\022)22 b Fe(V)43 b Fg(of)208 3768 y(lo)r(cations)23 b(where)h(y)n(ou)g(plan)g(to)g(put)h (the)g(uranium.)36 b(Eac)n(h)23 b(edge)h Fe(e)g Fg(represen)n(ts)f(a)h (barrier)f(to)h(neutrons)g(that)h(can)f(b)r(e)208 3868 y(reinforced)g(an)n(y)g(fractional)g(amoun)n(t)h Fe(x)p Fg(\()p Fe(e)p Fg(\))h(at)f(a)g(cost)f(of)h Fe(w)r Fg(\()p Fe(e)p Fg(\))p Fe(x)p Fg(\()p Fe(e)p Fg(\).)38 b(Y)-7 b(ou)25 b(m)n(ust)h(reinforce)e(the)h(edges)g(of)g(the)g(graph)208 3968 y(suc)n(h)j(that)i(for)f(an)n(y)f(t)n(w)n(o)g(v)n(ertices)g Fe(u;)14 b(v)29 b Fh(2)d Fe(Y)18 b Fg(,)30 b(the)g(shortest)e(path)h (from)g Fe(u)g Fg(to)g Fe(v)k Fg(under)c(lengths)g Fe(x)p Fg(\()p Fe(e)p Fg(\))h(\(i.e.)42 b(edge)28 b Fe(e)208 4067 y Fg(has)e(length)g Fe(x)p Fg(\()p Fe(e)p Fg(\)\).)38 b(is)26 b(at)h(least)f(one.)36 b(Y)-7 b(our)26 b(goal)f(is)h(to)h (minimize)g(the)g(total)f(cost)g(y)n(ou)g(pa)n(y)-7 b(.)36 b(Deriv)n(e)26 b(a)g(p)r(olynomial)208 4167 y(time)i(algorithm)e(to)i (minimize)g(the)g(cost,)f(or)g(sho)n(w)f(that)i(this)g(problem)f(is)h (NP-hard.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF