Midterm CSU 670 Spring 2009 Question 1: ================================================== UNKNOWN1 = Money combine(Money a, int v){ int r; // return money left if (toPay > v) { toPay = toPay-v; r = 0; } else {r = v - toPay; toPay = 0;} Main.p(" still to pay " + toPay + "\n"); return new Money(r);} UNKNOWN2 = a+b UNKNOWN3 = w+a UNKNOWN4 = k+b UNKNOWN5 = w+a UNKNOWN6 = p+c UNKNOWN7 = k+b UNKNOWN8 = w+a UNKNOWN9 = p+c UNKNOWN10 = k+b UNKNOWN11 = w+a UNKNOWN12 = bedrooms UNKNOWN13 = mattress UNKNOWN14 = mattress UNKNOWN15 = 19 UNKNOWN16 = 15 UNKNOWN17 = 18 UNKNOWN18 = 18 UNKNOWN19 = Counts only the money in one bedroom. There is no dedicated method for Bedrooms. Calls instead combine(Object, int) throwing away the money in the second bedroom. UNKNOWN20 = (continue on back) PaperBoy.moneyAvailableLoDV grossly violates the Law of Demeter. While it only has a customer, it reaches all the way down to access the values in the mattresses and kitchen cabinet. Question 2 To simplify, use: 1 = b^3 + 3*b^2*(1-b) + 3*b*(1-b)^2 + (1-b)^3 (1 = sum[q=0..3] binomial(3,q)*b^q*(1-b)^(3-q)) One of all possible events will happen with probability 1. An application of the Binomial Theorem: (x+y)^n = sum[k=0..n] binomial(n,k)*y^k*x^(n-k) set x = b, y = 1-b, n =3 Apply to: 63 = 1 + 2 + 4 + 8 + 16 + 32 = 255 - 64 - 128 Therefore the polynomial for 63 is: 1-b^2(1-b)-b^3=1-b^2 (63, 238) break-even(63,238) = 3/4 worst t1, t2: t1=t2=0.5 lookahead(63) (b) = 1-b^2 lookahead(238) (b) = 2*b - b^2 lookahead(63,238) (b,t1,t2) = t1*(1-b^2)+t2*(2*b-b^2) try: 1-b^2 = 2*b-b^2 b_max = 1/2 lookahead(63,238) (1/2,t1,t2) = t1*(1-b^2)+t2*(2*b-b^2) = 3/4 A fair coin guarantees a satisfaction ratio of 3/4. Best possible. ====== break-even (119, 238) = break-even (63, 238) 63 = 1 + 2 + 4 + 8 + 16 + 32 119 = 1 + 2 + 4 + 16 +32 + 64 238 = 2 + 4 + 8 + 32 + 64 + 128 Easiest solution: look-ahead(relation(2,0)) = 1-b^2 = not all true of 2 look-ahead(relation(2,2)) = 1 -(1-b)^2 = not all false of 2 1-b^2 = 1 - (1-b)^2 <=> b=1/2 substitute: 3/4 = break-even(119, 238) 321 63 119 1 000 2 001 4 010 8 011 0 16 100 32 101 64 110 0 128 111 0 0 For 63: ^ is don't care column. For 119:^ is don't care column. Or observe: look-ahead(119)=look-ahead(63) and therefore break-even(119,238)=break-even(63,238) ====== (104, 105) 104 = 64 + 32 + 8 105 = 64 + 32 + 8 + 1 104 implies 105 break-even(104,105) = break-even(104) 104 = 2 in 3. look-ahead(104)(b) = 3*b^2(1-b) b_max = 2/3 look-ahead(104)(2/3) = break-even(104) = 4/9 (104 106) 106 = 64 + 32 + 8 + 2 104 implies 106 same result (104 110) 110 = 64 + 32 + 8 + 4 + 2 104 implies 110 same result (104 111) 111 = 64 + 32 + 8 + 4 + 2 + 1 104 implies 111 same result ============= other example (127,254) 127: at least one false = not (all true) = !A or !B or !C 254: at least one true = not (all false)= A or B or C 1-b^3 = 1 - (1-b)^3 b=1/2 break-even = 7/8 worst t1, t2: t1=t2=0.5 for symmetry reasons other example: some conjectured that break-even (104 110) = break-even(2 8) This is not true: While 104 => 110 it is not the case that 2 => 8. And (1-b)^2*b = (1-b)*b implies b=2/3 and break-even(2,8)=4/27 ====== Some conjectured that break-even(63,238) = break-even(1,2). This is not true: Computing break-even(1,2): (1-b)^3 = (1-b)^2*b 1-b = b b=1/2 break-even(1,2)=1/8 break-even(63,238) = 3/4 =============================================================== Question 3 sdg class dictionary // Knapsack // Part a type KnapsackInstance product (items: ItemList cap: Weight) type KnapsackSolution product (selected: ItemNameList) type ItemList sum (NEItemList | EItemList) type NEItemList product (first: Item rest: ItemList) type Item product (itemName: ItemName value: Value weight: Weight) type EItemList product () type Value product (v: int) type Weight product (v: int) type ItemName product (v: ident) // type ItemList ... //Part b // CSP raw materials for your robots type RawMaterial product ( constraints: ConstraintList) type ConstraintList sum ( NECL | ECL ) type NECL product ( first: Constraint rest: ConstraintList ) type ECL product () type Constraint product (w: Weight ":" rn: RelationNr vars: VarList ) type Weight product (v: int) type RelationNr product (v: int) type VarList sum (NVL | EVL) type NVL product () type EVL product () // ... // Part c // self description type Cd_graph product ("sdg" "class" "dictionary" cd: NAdj_list) type NAdj_list product (first: Adj rest: Adj_list) type Adj product ("type" vertex: Vertex ns: Neighbors) type Neighbors sum (Product | Sum) =========== truth table: 1 000 2 001 4 010 8 011 16 100 32 101 64 110 128 111