Solutions Midterm Spring 2012 1. The same as the HSR(x,y) problem. HSR(x,y)=q implies TCP(x,y)=q. HSR produces a special binary search tree. same leaves. Internal nodes are 1..n. For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1. n = n-1 + 1 TCP(x,y)=q implies HSR(x,y)=q same leaves. There must be 1..n-1 internal nodes labeled as in HSR. Because in both cases a special binary search tree. Internal nodes cannot be larger than n-1. Otherwise would not be a special binary search tree. n2 = n0-1 = n - 1 The algorithm is based on the modified Pascal's triangle. First we compute the minimum number of questions needed followed by constructing the tree. Pruning of the tree might be needed. 2. Connection to Graph-DIS: Graph-DIS(c) implies optimum claim is C-Graph(n,c,c-1) Part 2.1: a) C-Graph(9,3,3) true, strengthen to C-Graph(9,3,2) 4 points b) C-Graph(160,4,1) true, strengthen to C(160,4,3) 4 points c) C-Graph(10,2,1) true and optimal 4 points Part 2.2: C1(11,3,2) is false. 8 points Stephanie Lund: The distance between s and t must be at least 4. By the BFS algorithm, we can divide all nodes from s to t into 3 layers, based on their distance from s. Other than s and t, we have 9 nodes so we can divide those into 3 layers of 3 nodes. The only way to remove all paths from s to t would be to delete all nodes in a layer, but the layers can all have 3 nodes; so k needs to be at least 3. *--*---* 3 nodes /\ /\ /\ / \/ \/ \ / /\ /\ \ / / \/ \ \ s---*---*----*---t 5 nodes, dist(s,t)=4 \ \ /\ / / \ \/ \/ / \ /\ /\ / \/ \/ \/ *--*---* 3 nodes 11 nodes total dist(s,t) = 4 > n/3 n < 12, choose n = 11 because no multiple of c=3 restriction. There are no two nodes whose deletion disconnects s from t. alternative: Michael Amirault, Eduardo Fungairino *-----*-----* / \ / \ s-*-----*-----*--t 5 nodes, dist(s,t)=4 \ / \ / *-----*-----* 3. ForAll Q, R Exists S !Q or ((R and S) or (!R and !S)) true: response: if Q and R then S (S true) else if Q and !R then !S (S false) else S is don't care alternative: if Q is false, pick any S, if Q is true, pick S = R. other alternative: Jason Shrand if R then S (S true) if !R then !S (S false) other alternative: Christopher Souvey, Sarah Laplante S = R other: S = Q and R negation must be false: Exists Q,R ForAll S: !(!Q or ((R and S) or (!R and !S))) 4. C = 20 n0 = 100 or C = 1000 n0 = 10 5. 5 points for each of the 6 subquestions 5.1.1: false, add acyclic: DAG 5.1.2: false, add no odd cycle 5.1.3 false, 3/4 is optimal or change length 2 to length 3. 5.1.4 true, strengthen to g=(sqrt(5)-1)/2. 5.2.1 assuming s and t are connected. true, using BFS or DFS. O(n+m) 5.2.2 true, use Gale-Shapley O(n^2) 6. Stephanie Lund: Defending a claim is different from proving it true. If a refuter provides an x, and the defender provides a suitable y, the claim has been defended only for that x. It is still possible that there exists an x for which there is no satisfying y. Refuting a claim only shows that the defender cannot provide a suitable y, not that such a y does not exist. It is possible that the defender is not using an optimal algorithm. Mike Allen Refuting and defending are merely providing instances and their solutions that contradict or support a claim. They are not a mathematical proof either way. Jason Shrand: Refuting a claim is different from proving it false, as a refutation in itself may be refutable. Refutations based on an error of the Proposer can be invalidated and will fail to disprove a claim. Christopher Souvey: A successful refutation only proves that the proposer can't defend the claim, not that the claim cannot be defended.