1. Number Line (55 answered for credit) score range: 11-25 (mode 21) EC score range: 0-25 (A) best: 256, worst: 511 (B) best: 9, worst: 109 (C) best: 11, worst: 12 Extra Extra Credit (27 successful) answers: wet-wed-wad-dad-day-dry wet-pet-pee-pre-pry-dry wet-bet-bat-bay-day-dry (8 people) wet-wed-wad-way-wry-dry (5 people) wet-wed-wad-way-day-dry (3 people) wet-met-mat-may-day-dry (9 people) wet-pet-pat-pay-pry-dry (2 people) wet-pet-pat-pay-day-dry wet-set-sat-say-day-dry (3 people) 2. Word Ladder: CSP Modeling (38 answered for credit) score range: 12-24 (mode 20) EC score range: 0-24 (A) There are two ways to do this. One is to base things on letters, another on words. I thought words were more natural, but letters also work. Words ----- Variables: X1...X4 Domain: L Constraints: (X1) : {w | w is one away from "wet"} (X4) : {w | w is one away from "dry"} (X1,X2) : {w1, w2 | w1 is one away from w2 } (X2,X3) : {w1, w2 | w1 is one away from w2 } (X3,X4) : {w1, w2 | w1 is one away from w2 } Note that the legal assignment lists will be no larger than |L|26x3. Letters ------- Variables: a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3 Domain: A={a, ..., z} (a is first word, d is last final) Constraints: (a1,a2,a3) : { all three letter combinations that give a word one away from "wet" } (d1,d2,d3) : { all three letter combinations that give a word one away from "dry" } (a1,a2,a3,b1,b2,b3) : { all six letter combinations that give two words, w1 and w2, such that w1 is one away from w2 } (b1,b2,b3,c1,c2,c3) : { all six letter combinations that give two words, w1 and w2, such that w1 is one away from w2 } (c1,c2,c3,d1,d2,d3) : { all six letter combinations that give two words, w1 and w2, such that w1 is one away from w2 } (B) Words ----- After things settle down, each word in X1 must be one step away from "wet" and one step away from some word in X2. Similarly, each word remaining in X2 is one step away from some word in X1 and some word in X3. Since this holds for each set, any word in Xi sits on some ladder of 4 words between "wet" and "dry". This means that now we can choose any word in X1, any word in X2 that works with X1, any word in X3 that works with X2, and any word in X4 that works with X3, and we have a valid ladder. No search is needed! Letters ------- This doesn't work out as well as it does in the word case. For example, since "wed", "bet", and "wit" are all one away from "wet", we could form the word "bid" in the first slot out of the remaining letters. So the second slot will have to include words that fit with "bid", which won't end up limiting it to only words on a valid ladder. 3. Word Ladder: SAT Modeling (15 answered for credit) score range: 5-24 EC score range: 0-24 (mode 0) (A) One solution is to convert that CSP encoding into a SAT encoding using the method described in class. Here is a more direct solution. v(i,j,alpha) is an indicator variable for word i (1 to 4), letter position j (1 to 3), letter alpha (a...z). Wi(w) is an indicator variable for word i (1 to 4) having identity w (in L). Clauses: for each i, Wi(w1) + Wi(w2) + Wi(w3) ... (At least one word must be chosen.) for each i, w, j, (~Wi(w) + v(i,j,alpha)) (where alpha is the jth letter of i) (Picking a word forces the corresponding letters to be picked.) for each i, alpha != beta, gamma != delta, and j1 != j2, ~v(i,j1,alpha) + ~v(i+1,j2,beta) + ~v(i,j1,gamma) + ~v(i+1,j2,delta) (Can't have two consecutive words differ by more than one letter.) (v(1,1,w) + v(1,2,e))(v(1,1,w) + v(1,3,t))(v(1,2,e) + v(1,3,t)) (First word must match two or more letters of "wet".) (v(4,1,d) + v(4,2,r))(v(4,1,d) + v(4,3,y))(v(4,2,r) + v(4,3,y)) (Fourth word must match two or more letters of "dry".) 4. Word Ladder: Heuristic (52 answered for credit) score range: 9-25 (mode 25) EC score range: 0-24 (A) h(s) = number of characters mismatching target state ("dry"). (B) Constraints: next state is illegal if (1) more than one letter changed from previous word (2) next state is not a word The heuristic in part (A) gives the optimal solution length to the problem which relaxes (removes) the second constraint. 5. Maximially Unassigned Satisfying Assignment (30 answered for credit) score range: 11-24 EC score range: 0-22 (mode 0) (A) Starting state: all 1s. Scoring function: number of zeros (plus negative infinity if resulting partial assignment is not satisfying). (B) Hillclimbing is not guaranteed to find the global optimum. In the example problem, 011 is a local optimum, but it is not globally optimal (since 100 has fewer variables assigned and is still satisfying). (C) The statement is true for the example but is not true in general. Consider the formula (a+b)(c+d) with satisfying assignment T T T T. The partial assignment 1010 is satisfying as is 0101. However, crossover can yield the children 1100 and 0011, neither of which are satisfying. 6. Win, Lose or Draw (54 answered for credit) score range: 6-25 (mode 21) EC score range: 0-23 (A) Value is 1. (B) [0] 2 [0] 1 1 2 1 0 [1] [1] [0] 1 [1] [2] 2 2 I took off two points for extra circles and three points for missing circles. I think the most common mistake was to circle the final two, which can be pruned. (To see this, ask yourself what value of the leaf would change the value of the root.)