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
  "<constraint>"
      "<weight>" Weight "</weight>"
          "<relation>" Relation "</relation>"
	      "<variables>" VariableList "</variables>"
	        "</constraint>".


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 = <height> int <diameter> 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()) .<Pack>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)