аЯрЁБс>ўџ <>ўџџџ;џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅС7 №ПИbjbjUU "67|7|ИџџџџџџlЈЈЈЈЈЈЈМииииьlМЩъddddddddHJJJJJJ$Г гІnЈdddddndЈЈddƒddddЈdЈdHddHdАdЈЈdX  Ž‰ј№ЇУМиd4™0ЩydydММЈЈЈЈйCOT 4810 Homework #6 (10/14-10/16), due 10/30/03 (Please answer all 6.) Game Trees (Cht. 6) 1) Give an example of a game tree (that is two levels deep) where pruning could be employed. (Note: No need to write an evaluation function or anything. Just show the values calculated at each "position" and how that could lead to pruning.) board / | \ a2 b1 c1 / | \ / | \ / | \ d2 e4 f3 g1 prune j1 prune In the tree above, the letters a through l represent moves. Moves h, i, k and l are all pruned away since moves g and j knock moves b and c out of contention so to speak. (Note: Moves h and i are below b, and moves k and l are below c.) Detecting Primes (Cht. 50) 2) Use Miller's test to determine if 47 is prime or not, with a probability of 75%. (Hint: run the test twice with two different bases.) Try base 2: 246 = 4(211)4 mod 47 = 4(2048)4 mod 47 = 4(27)4 mod 47, using a calculator = 4(12) mod 47 = 1 mod 47 as desired. Try base 3: 346 = 9(311)4 mod 47 = 9(177147)4 mod 47 = 9(4)4 mod 47, using a calculator = 9(21) mod 47 = 1 mod 47 as desired. Public Key Cryptography (Cht. 37) 3) Given the set S = {2, 5, 8, 19, 35, 80} list out all values of k for which there is a subset that sums to it for 20 < k < 35. The subset must contain 19 and can not contain 35 or 80. This set is contructed as the sets used for the Hellman-Merkle-Diffie cryptosystem. Thus, any subset that sums to greater than 19 and less than 35 must contain 19, since the rest of the elements less than 19 in S don't even sum to 19. Thus, we can list all subsets of S that contain 19 as their largest element that have more than one element to reproduce the set of k: kSubset21{19, 2}24{19, 5}26{19, 5, 2}27{19, 8}29{19, 8, 2}32{19, 8, 5}34{19, 8, 5, 2} Random Numbers (Cht. 8) 4) Using the linear congruence method given that k=37, c=4, m=100 and x0=75, produce the first ten "random" numbers x1, x2, x3, ... x10. TermCalculationValuex1(37*75+4) mod 10079x2(37*79+4) mod 10027x3(37*27+4) mod 1003x4(37*3+4) mod 10015x5(37*15+4) mod 10059x6(37*59+4) mod 10087x7(37*87+4) mod 10023x8(37*23+4) mod 10055x9(37*55+4) mod 10039x10(37*39+4) mod 10047 Linear Programming (Cht. 57) 5) Given that x + y ( 8 and 3x + 2y ( 15, with x ( 0 and y ( 0, find the maximum value of 6x+5y. Oops! Sorry about this problem, the two lines involved don't even intersect, so you only have to use the second constraint for the problem. By graphing, we only have to test the endpoints of the line 3x+2y = 15 in the first quadrant. These are (5, 0) and (0, 7.5). Using the second, we find the maximum value of 6x+5y to be 37.5. Noncomputable Functions (Cht. 39) 6) Find the busy beaver for two states. (Using the busy beaver 5 definition.) Input StateInput CharacterOutput StateOutput CharacterDirectionstartblankA1Rightstart1A1LeftAblankstart1LeftA1halthalthalt Let t be the tape head. In the trace below, t will be directly to the left of the character the machine will process next. Also, blanks will be represented by 0. Here is a trace of the machine: Tape: t0 (start, 0) ( (A, 1, Right) Tape: 1t0 (A, 0) ( (start, 1, Left) Tape: t11 (start, 1) ( (A, 1, Left) Tape: t011 (A, 0) ( (start, 1, Left) Tape: t0111 (start, 0) ( (A, 1, Right) Tape: 1t111 (A, 1) ( Halt This may not be the only machine for 2 states. (I haven't done an exhaustive search to prove that other machines don't exist.) $0H]_O$&ЎЛНУХЦЧёђˆ‰‹‘“”•СТщъK L p r ђ % ' l m š › ž Ÿ Ђ Ѓ Њ Ќ Џ Ч Ш Щ р с т љ њ ћ    ) * + B C D [ \ ] t u v  Ž  І Ї Љ С Т с ќѕќ№ќќ№ќќчпчпчпчпчпќчпчпчпчпчпќ№ќќ№ќйдйдйдйдйдпдйпдйпдйпдйпдйпдйпдйпдйпдйпдйпќ№OJQJ H*OJQJ5OJQJ\5H*OJQJ\ 5>*\ 56\]5\T1H\]NOYn‘к#$­ЎЯњ7_z{Ъ / њњјјѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓѓ$a$$a$И§/ J K L o p ё ђ  ž   Ї Ј Ћ Г Д њњњњњњњњњёё†0ёё†0k$$If–lжж0”џр,"LLж0џџџџџџі6жџџжџџжџџжџџ4ж laі $$Ifa$$a$Д З П Р У Ю Я в к л о щ ъ э ј љ ќ іі‹<іі‹0іі‹<іі‹<іі‹Hіk$$If–lжж0”џр,"LLж0џџџџџџі6жџџжџџжџџжџџ4ж laі $$Ifa$ќ $ % Ў Џ Д Р Ц і‹†††††ііі$a$k$$If–lжж0”џр,"LLж0џџџџџџі6жџџжџџжџџжџџ4ж laі $$Ifa$ Ц Ч Ъ м п р у ѕ ј љ ќ    dxxxdxxx`xxx` $$Ifa$~$$If–lжжF”џ„Є,"№ ˆ ж0џџџџџџі6ж џџџж џџџж џџџж џџџ4ж laі   % ( ) , > A B E W Z [ ^ іііxdіііxdіііxdі~$$If–lжжF”џ„Є,"№ ˆ ж0џџџџџџі6ж џџџж џџџж џџџж џџџ4ж laі $$Ifa$ ^ p s t w ‰ Œ   Ђ Ѕ І Њ М ііxdіііxdіііxhіі~$$If–lжжF”џ„Є,"№ ˆ ж0џџџџџџі6ж џџџж џџџж џџџж џџџ4ж laі $$Ifa$ М П Р С Т р с BCŽАБџіxsssssssssss$a$~$$If–lжжF”џ„Є,"№ ˆ ж0џџџџџџі6ж џџџж џџџж џџџж џџџ4ж laі $$Ifa$ с у ѕ і CŽБДDE[\mnƒ„—™uv—˜РСту 12Иќјјєєќяќќќќќќќшќшќшќшќшќшќ jЎ№5\ 5>*\ jГ№ jЃ№5\%џ ):DEKњёёёёёM\ёЄ$$If–lжжr”џdд,"ы‘TpXж0џџџџџџі6жџџџџџжџџџџџжџџџџџжџџџџџ4ж laі $$Ifa$$a$KQSU[\bdfhііііRHііііЄ$$If–lжжr”џdд,"ы‘TpXж0џџџџџџі6жџџџџџжџџџџџжџџџџџжџџџџџ4ж laі $$Ifa$ hmnpv|~ƒ„†іRXіііііRPіЄ$$If–lжжr”џdд,"ы‘TpXж0џџџџџџі6жџџџџџжџџџџџжџџџџџжџџџџџ4ж laі $$Ifa$ †ˆ’—˜™[\ііііRMKK$a$Є$$If–lжжr”џdд,"ы‘TpXж0џџџџџџі6жџџџџџжџџџџџжџџџџџжџџџџџ4ж laі $$Ifa$\jЕл*89И§§§§§§§§§ 1hАа/ Ар=!А"А# $ %А i8@ёџ8 NormalCJ_HaJmH sH tH <A@ђџЁ< Default Paragraph FontИ 6 џџџџ1H\]NOYn‘к#$­ЎЯњ7_z{Ъ/JKLopёђž ЇЈЋГДЗПРУЮЯвклощъэјљќ   $%ЎЏДРЦЧЪмпруѕјљќ    % ( ) , > A B E W Z [ ^ p s t w ‰ Œ   Ђ Ѕ І Њ М П Р С Т р с B C  Ž А Б џ  ) : D E K Q S U [ \ b d f h m n p v | ~ ƒ „ † ˆ  ’ — ˜ ™ [ \ j  Е л *89К˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜@0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€™0€€˜0€€˜0€€˜0€€˜0€€˜0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€Љ0€€Љ0€€Љ0€€™0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€Љ0€€Ћ0€€Ћ0€€Ћ0€€Ћ0€€™0€€Љ0€€Ћ0€€Ћ0€€Ћ0€€Ћ0€€™0€€Љ0€€Ћ0€€Ћ0€€Ћ0€€Ћ0€€™0€€Љ0€€Ћ0€€Ћ0€€Ћ0€€Ћ0€€™0€€Љ0€€Ћ0€€Ћ0€€Ћ0€€Ћ0€€™0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€с И / Д ќ Ц  ^ М џKh†\И И џџdmarinodC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of Document1.asddmarino)C:\arup\COT4810\Homework\COT4810Hmk06.docdmarinojC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of COT4810Hmk06Sol.asddmarinojC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of COT4810Hmk06Sol.asddmarino,C:\arup\COT4810\Homework\COT4810Hmk06Sol.docdmarinojC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of COT4810Hmk06Sol.asddmarinojC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of COT4810Hmk06Sol.asddmarino,C:\arup\COT4810\Homework\COT4810Hmk06Sol.docž ЇЈЋГДЗПРУЮЯвклощъэјљќ  ЏДРЦЧЪмпруѕјљќ    % ( ) , > A B E W Z [ ^ p s t w ‰ Œ   Ђ Ѕ І Њ М П Р  ) : D E K Q S U [ \ b d f h m n p v | ~ ƒ „ † ˆ  ’ — ˜ Кžžžžžžž–žžžžžžžžžž–žžžž–џ@€ЗЗфЉсЗ7d@ИА@џџUnknownџџџџџџџџџџџџG‡z €џTimes New Roman5€Symbol3& ‡z €џArial3Times"1ˆ№аhЕzf U{&I!# $№ЅРДД0ч2ƒ№џџ0COT 4810 Homework #6 (10/14-10/16), due 10/30/03dmarinodmarinoўџр…ŸђљOhЋ‘+'Гй0”˜др№ќ (4 P \ ht|„Œф1COT 4810 Homework #6 (10/14-10/16), due 10/30/030OT dmarinomarmarNormaldmarino3arMicrosoft Word 9.06@іЎ2 @=™У@Жђ№ЇУ!# ўџеЭеœ.“—+,љЎ04 hp˜ ЈА ИРШа и фUniversity of Central Florida6ч  1COT 4810 Homework #6 (10/14-10/16), due 10/30/03 Title ўџџџ !"#$%&'()*ўџџџ,-./012ўџџџ456789:ўџџџ§џџџ=ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF`ыžј№ЇУ?€1TableџџџџџџџџџџџџyWordDocumentџџџџџџџџ"6SummaryInformation(џџџџ+DocumentSummaryInformation8џџџџџџџџџџџџ3CompObjџџџџjObjectPoolџџџџџџџџџџџџ`ыžј№ЇУ`ыžј№ЇУџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РFMicrosoft Word Document MSWordDocWord.Document.8є9Вq