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:
k / Subset21 / {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.
Term / Calculation / Valuex1 / (37*75+4) mod 100 / 79
x2 / (37*79+4) mod 100 / 27
x3 / (37*27+4) mod 100 / 3
x4 / (37*3+4) mod 100 / 15
x5 / (37*15+4) mod 100 / 59
x6 / (37*59+4) mod 100 / 87
x7 / (37*87+4) mod 100 / 23
x8 / (37*23+4) mod 100 / 55
x9 / (37*55+4) mod 100 / 39
x10 / (37*39+4) mod 100 / 47
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 State / Input Character / Output State / Output Character / Directionstart / blank / A / 1 / Right
start / 1 / A / 1 / Left
A / blank / start / 1 / Left
A / 1 / halt / halt / halt
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.)