CSG 110 Spring 2008 Karl Lieberherr Midterm March 24 ---------------- Question 1: ================================================== UNKNOWN1 = int combine(Object n, int i){ return i; } // i+1 if want to count noise UNKNOWN2 = NOTHING UNKNOWN3 = int combine(Object n, int i){ return i; } Question 2: ================================================== UNKNOWN1 = Weight UNKNOWN2 = VariableList UNKNOWN3 = Kind UNKNOWN4 = Constant UNKNOWN5 = OldC apply(NewC i){ return new OldC( i.get_weight(), new Relation(new Integer(3000)), i.get_variablelist()); } assumes cd: CSP = ConstraintList. Constraint : OldC | NewC. NewC = *l Weight VariableList Kind Constant. OldC = *l "" "" Weight "" "" Relation "" "" VariableList "" "". Question 5: ================================================== UNKNOWN1 = DiameterPair combine(NodeInt t, Integer d, DiameterPair l, DiameterPair r) { return new DiameterPair(Math.max(l.get_height(), r.get_height())+1, Math.max(l.get_height() + r.get_height() +1, Math.max(l.get_diameter(), r.get_diameter()))); } DiameterPair combine(Object n, DiameterPair i){ return i; } // DiameterPair = int int. Question 6: ================================================== UNKNOWN1 = class Check extends IDb{ Pack combine(BSTInt l){ return new Pack(true); } Pack combine(NodeInt t, int d, Pack lt, Pack rt){ return new Pack((lt.good && rt.good && (lt.max < d) && (d < rt.min)), Math.min(lt.min,d), Math.max(rt.max,d)); } static boolean check(BSTInt tree){ return new Traversal(new Check()) .traverse(tree).good; }} UNKNOWN2 = See above with Pack combine(Object o, Pack p) {return p;} Other questions: =========================================================== Question 1.1b Program works with any cd for a hierarchical structure (does not have to be recursive) with properties: (^ is used for "result comes up the object) Use classes BSTInt and NodeInt. NodeInt Integer ^ ^ Object ^ BSTInt : EmptyInt. // but EmptyInt not hardwired. Question 1.2b Must use a class BSTInt. Question 3: ======================================================================= 011 8 101 32 110 64 104 System analysis for 104: threshold = min [all formulas F] max [all assignment J] sat(F,J) apply to formulas only using 104. symmetric formulas are the worst-case. Take a symmetric formula with binomial(n 3) constraints where binomial(n k) is the binomial coefficient. If we set k variables to true (does not matter which subset), we get the fraction binomial(k,2) * (n-k) --------------------- binomial(n,3) satisfied. binomial(k,2) * (n-k) k^2 * (n-k) * 6 --------------------- =~ ------------- binomial(n,3) 2 * n^3 = 3 * x^2 * (1-x) = f(x) if we set x=k/n. f(x) has a maximum at 2/3 which is 4/9 = threshold. Question 4: ======================================================================= Returns the height of the tree. input: tree t precondition: t not null (assuming class graph is ok) postcondition: return = height(t) >=0 (ignoring noise)