CSG 110
Spring 2008                                          Karl Lieberherr

Midterm March 24
----------------
Open book and open notes

Question 1: 30 points
Question 2: 42 points
Question 3: 20 points
Question 4: 20 points
Question 5: 20 points
Question 6: 30 points
162 points total

THE GAME OF REDUNDANCY AND UNKNOWNS
-----------------------------------

Some of the questions in this exam ask you to determine unknowns
of the form UNKNOWN1, UNKNOWN2, ... This makes it easier for you
to answer the questions, since you get extra context information.
Yet you need to master the behavioral objectives of the course to answer
the questions. Guessing an answer is not a successful strategy and
therefore a "game of redundancy" test is more interesting than
a multiple choice test.

The questions have the following pattern: I show you several artifacts
which are related by the material covered in the course.
Because of the dependencies between the artifacts,
some of the information is redundant and can be recovered from the
context by applying the objectives covered in the course.
The information which you should discover is marked UNKNOWNx.

If an UNKNOWN is empty, use  UNKNOWN = NOTHING.

Question 1: 30 points : structure evolution
==================================================

Consider the following two class dictionaries
that are also used in later questions:
The first one, called cd-with-noise,
defines trees with some noise added:

cd-with-noise:
BSTInt : EmptyInt | NodeInt.
NodeInt = "(" <data> int <a> N1 <b> N2 ")".
N1 = <t> BSTInt .
N2 = <t> BSTInt .
EmptyInt = "empty".

The second defines "pure" trees:

cd-pure:
BSTInt : NodeInt | EmptyInt.
NodeInt = "(" <data> Integer <left> BSTInt <right> BSTInt ")".
EmptyInt = "()".

We are charged to develop a library of tree processing
routines that work with these two data structures as well as
with several other "tree-like" data structures.

The functions we want to implement are: height, incr, sum.
For each of those functions you get the solution for cd-pure
and you are asked to generalize it so that it works for both
cd-pure and cd-with-noise.
To achieve this impressive flexibility we use DemeterF.

PART 1a: 5 points
=======
Here is a solution for height which works for class dictionary
cd-pure:

class Height2 extends IDb{
    int combine(NodeInt t, int d, int l, int r){ int n= Math.max(l,r) + 1; 
      System.out.println(" height increased " + n); return n;}
    int combine(BSTInt l){ return 0; }

    static int height (Object o)
    {
	return new Traversal(new Height2()). <Integer> traverse(o);
    }
}

Add one or more combine methods to make your program
work for both class dictionary cd-pure and
class dictionary cd-with-noise
as well as for many other class dictionaries.
Put combine method(s) in UNKNOWN1.

PART 1b: 5 points
=======
Give an English description of the kind of class dictionaries for which
your program will work.
Use blue book.


PART 2: 5+5 points
=======
Do the same for: incr.


Here is a solution for incr which works for class dictionary
cd-pure:

class Incr extends IDf{ 
  int apply(int i){ return i+1; } 
    static BSTInt incr (Object o)
    {
	return new Traversal(new Incr()). <BSTInt> traverse(o);
    }

}

Answer parts 1a, 1b.
Put combine method(s) in UNKNOWN2.

Part 3: 5+5 points
=======
Do the same for: sum


class Sum extends IDb{
    int combine(NodeInt t, int d, int l, int r){ return d+r+l; }
    int combine(BSTInt l){ return 0; }
  static int sum (Object o)
    {
	return new Traversal(new Sum()). <Integer> traverse(o);
    }
}

Answer parts 1a, 1b.
Put combine method(s) in UNKNOWN3.


Question 2: 42 points : Adding a feature
==========================================================

You are asked to develop software for
the following new version of the SDG game.
The raw material is a collection of
weighted constraints as in SDG(CSP)
and all constraints are expressed
as linear inequalities of the form:

sum x_i = j
sum x_i >= j
sum x_i <= j

Example of a raw material in this new form:

10  x1 x6 x8 = 1
3   x1 x5 x7 = 2
4   x1 x2 >= 1
200 x1 x2 <= 1
2   x2 = 1

The meaning of the first constraint 
10  x1 x6 x8 = 1
is
x1 + x6 + x8 = 1 with weight 10.
The addition is integer addition but as usual,
the variables only assume values 0 or 1.

How would you manage this software development project?
Develop a brief plan and write it down succinctly like:

1. Class dictionary for new notation.
2. Extend class dictionary to cover new and old notation.
3. Write DemeterF function object ...

Design a class dictionary for inputting the
new kind of raw material.

Find the UNKNOWNs in the following class dictionary:
(3 points each)

CSP = ConstraintList.
Constraint = *l UNKNOWN1 UNKNOWN2 UNKNOWN3 UNKNOWN4.
Kind : Exact | GreaterThanEqual | LessThanEqual.
Exact = "=".
GreaterThanEqual = ">=".
LessThanEqual = "<=".
Variable = <v> Ident.
Relation = <v> int.
Weight = <v> int.
Constant = <v> int.

ConstraintList : NECL | ECL.
NECL = <first> Constraint <rest> ConstraintList.
ECL = .

VariableList : NEVL | EVL.
NEVL = <first> Variable <rest> VariableList.
EVL = .

How would you leverage the current SDG(CSP) implementation?
You must translate the new input format into
an XML style input format and figure out
a function relNumber(int numberOfvariables, Kind kind, Constant constant)
that determines the relation number.
For example, relNumber("3","=","1") = 22.

Assume that this function is given to you and it currently
is the constant 3000.

Write a program to translate constraints of the new form:

10 x1 x6 x8=1
3 x1 x5 x7=2
4 x1 x2>=1
200 x1 x2<=1
2 x2=1 

to constraints of the old XML style form:

<constraint><weight>10</weight><relation>3000</relation>
  <variables>x1 x6 x8</variables></constraint>
<constraint><weight>3</weight><relation>3000</relation>
  <variables>x1 x5 x7</variables></constraint>
<constraint><weight>4</weight><relation>3000</relation>
  <variables>x1 x2</variables></constraint>
<constraint><weight>200</weight><relation>3000</relation>
  <variables>x1 x2</variables></constraint>
<constraint><weight>2</weight><relation>3000</relation>
  <variables>x2</variables></constraint> done 

Find the UNKNOWN in the enclosed program: 30 points


import edu.neu.ccs.demeterf.*;

class Trans extends IDf{ 
  UNKNOWN5
  static CSP trans (Object o)
    {
	return new Traversal(new Trans()). <CSP> traverse(o);
    }

}

Question 3: 20 points : System analysis / application knowledge
==========================================================
Use blue book.

Application software development requires knowledge 
about the application domain.

PART 1: 5 points
What is the relation number for Boolean relation R2(x1,x2,x3)
defined by x1 + x2 + x3 = 2? Addition is integer addition.

PART 2: 15 points
If the type of a derivative contains only relation R2,
what is the lowest price p so that you are guaranteed 
not to lose money if you offer the derivative at price p?

Question 4: 20 points : Reverse engineering
==========================================================
Use blue book.

Reading undocumented code is challenging.
What is the meaning of XYZ.xyz(Object o)?
Explain in English what the method computes.
Give a precondition and a post-condition
that captures the meaning of the method.

class XYZ extends IDba{
    int update(NodeInt n, int i){ return i+1; }
    int combine(NodeInt t, int d, int l, int r){ return Math.max(l,r); }
    int combine(Object n, int i){ return i; }
    int combine(BSTInt n, int i){ return i; }

    static int xyz (Object o)
    {
	return new Traversal(new XYZ()). <Integer> traverse(o,0);
    }
}

Question 5: 20 points : structure-shy programming
==============================================================

The diameter of a tree T is the largest of the following quantities:

* the diameter of T's left subtree
* the diameter of T's right subtree
* the longest path between leaves that goes 
  through the root of T (this can be computed 
  from the heights of the subtrees of T) 


Implement the Diameter computation in a structure-shy way
using DemeterF. Do one traversal of the tree to compute
both height and diameter.

Your function object must correctly compute the diameter for both
cd-pure and cd-with-noise from question 1.

Find the UNKNOWN below:

From the class dictionary:

DiameterPair = "height" <height> int "diameter" <diameter> int.


From the function object:

class Diameter extends IDba{ // type unifying 
    DiameterPair combine(BSTInt l) {return new DiameterPair(0,0);}
    UNKNOWN1
}

Question 6: 30 points : Design by contract / structure-shy
=================================================================

Consider the design by contract approach
in the context of binary search trees.
You write the contract for a method which
has as precondition the property that the
tree must be a binary search tree.
You use a check predicate that is implemented
using the following Check function object.

The check predicate expresses
that the integers in the left subtree
must all be smaller than the integer at the root
and the integers in the right subtree must all be
greater than or equal to the integer at the root.

PART 1: 15 points
======

Your check method must work for cd-pure.

Find the UNKNOWN below.

class Check extends IDb {
    boolean combine(BSTInt l){ return true; }
    UNKNOWN1
}

PART 2: 10 points
======

Do this part only if you are done with all other questions.

Can you make your check predicate work for both
cd-pure and cd-with-noise by changing your code?
Put code in UNKNOWN2.


PART 3: 5 points
======
Use blue book.

Discuss whether you have any Law of Demeter violations
in your program. Justify your answer.