top

COMP 202: Principles of Object-Oriented Programming II

← Exam1 Review Lab →

Home — Fall 2008

Here are some practice exercises to help you prepare for Exam 1:

Write a lazy evaluator for a lazy LRStruct called LazyNInvEval that will create the following list:
{1.0, 1.0/2.0, 1.0/3.0, 1.0/4.0, 1.0/5.0, ....}
That is, the list of all the inverses of the integers (expressed as Doubles).

Use the following code base (lazyEvalCode.zip) which has been modified from the lecture code to include the above evaluator, plus adds a new algorithm that can sum the first N elements and has had its code cleaned up and reorganized somewhat. The LazyNInvEval class is included but the method bodies have been deleted -- just for you!
Write an ILambda, called AlgebraicRep, for an InOrder1 visitor for a BiTree that behaves as follows: Suppose the tree was representative of "abstract syntax" where the interior nodes of the tree (i.e. nodes that have at least one non-empty child) were filled with strings that represent functions of one or two variables, and the leaves of the tree (i.e. nodes that have 2 empty children) were strings representing variable names. For instance, given the following tree:
```
f1
|_ a
|  |_[]
|  |_[]
|_f2
  |
  |_f3
  | |_b
  | | |_[]
  | | |_[]
  | |_c
  |   |_[]
  |   |_[]
  |_f4
     |_[]
     |_d
       |_[]
       |_[]
```
The result of running the InOrder1 visitor with your lambda on the above BiTree should be a single string with the familiar algebraic notation:

f1(a, f2(f3(b, c), f4(d)))

An empty tree would return an empty string and a single element tree would return a string with just that element in it.

Do not assume that the tree holds Strings. Use the data's toString() method to get a string representation of that data.

Is this actually an in-order tree traversal?

Here is a zip file with a pre-built project including test cases where the body of AlgebraicRep has been deleted for your convenience: biTreeCode.zip :-) (also contains code for Prob. 6)
Write an IAlgo visitor to an LRStruct, called MapLRS, that "maps" an ILambda onto every element of the list as such:
    Map(f, inp, {x1, x2, x3, ....}) = {f(x1, inp), f(x2, inp), f(x3, inp), ...}

MapLRS mutates the host LRStruct. The constructor of MapLRS should take the ILambda that it is going to use.   The input parameter(s) to the lambda are the input parameters to the Map visitor.

The return value of the ILambda can be used to control the mapping process.   Let the ILambda be defined as returning a Boolean object.   If the return value is Boolean.TRUE, continue mapping. Otherwise stop mapping.

MapLRS should return a reference to the host LRStruct.

Write some test lambdas to check if you mapping is working properly:
1. Square every integer in a list of integers (Square).
2. Append a string onto every string in a list of strings (AppendStr)
3. Replace every negative value in a list of integers with its positive counterpart (AbsVal)
4. Replace every string in a list of strings with another string unless a particular stop string is encountered, at which point, stop mapping. The element containing the stop string is not replaced. The stop string is given to the constructor of the lambda. (ReplaceStr)
Here is a zip file with all the necessary classes with a pre-built project with test code and all student code graciously stubbed out: mapFoldCode.zip (contains code for Probs. 4 & 5 too).
Write an ILambda, called AddingMachine, that when used with FoldlLRS on a list of integers, will return a list of integers that holds the running total of the elements of the original list up to that point. For instance:
{} ==> {0}
{a, b, c, d, ...} ==> {..., a+b+c+d, a+b, a, 0}

NOTE: The definitions of FoldlLRS and FoldrLRS used here are slightly different than that used in class: Foldl/r passes host not host.getFirst() to the lambda.
What do you expect to happen if you run this lambda using FoldrLRS?

The download for Prob. 3 contains the test code and stubs for this problem.
Given an LRStruct containing distinct Integers, find the minimum element and return the LRStruct containing this minimum (as its first). Write the algorithm in two ways:
1. as a standard visitor using forward accumulation. (MinLRS)
2. as a higher-order visitor using the FoldrLRS visitor and an appropriate ILambda. (Min2LRS)
The download for Prob. 3 contains the test code and stubs for this problem.
Given an BiTree containing distinct Integers, find the minimum element and return the BiTree containing this minimum element (as its root data). An empty tree should return the empty host tree as its result. Note that the BiTree is not ordered in any way. Write the algorithm in two ways:
1. as a standard visitor using in-order traversal (MinTree)
2. as a higher-order lambdausing the InOrder1 visitor and an appropriate ILambda (Min3Tree)
The download for Prob. 2 contains the test code and stubs for this problem.

Solutions for the above problems -- no peeking!!

← Exam1 Review Lab →