Comp201: Principles of Object-Oriented Programming I
Spring 2006 -- Extra Credit Assignments   

The following assignments will add the indicated number of percentage points to a student's total grade.

5 pts:   Complete the extra-credit HW12

Submit this part of the extra-credit work as instructed in HW 12.

5 pts:   Complete the following problems:

For this part of the extra-credit assignment, create a subdirectory called extra2 and save all work in this subdirectory.  After you are done, clean the build directory of your project files to remove all class files.  Zip the whole extra2 subdirectory and submit it to your Comp 201 WEBCT Extra assignment page.

Suggestion:   Add the following method to LRStruct to make checking equality of lists easier:

    public boolean equals(Object other) {
      return (Boolean) this.execute(lrs.visitor.LRSEqual.Singleton, other);
    }
    

Now, in your JUnit tests, simply define a "result" list that is an LRStruct that has the elements that you expect to see in the resultant list after running an algorithm on the test list.  Your codes should look something akin the the following

assertEquals("Descr. of this test", resultList, testList.execute(algo, params));

1. (0.25 pts) Using a Comparator, write a visitor called RemAllComp to an LRStruct that will remove all elements in the LRStruct that are "less than" (as defined by the Comparator) a given value.   Thus the visitor will take two input parameters, a Comparator and an Object with which to compare the elements.  The host list should be returned.
   
    
2. (0.25 pts) Write a visitor called RemMinComp that removes the minimum element from an LRStruct, as defined by a given Comparator.  Hint:  Do you want to accumulate the actual minimum value or the list whose first is the current minimum value?   The minimum value should be returned.
   
    
3. (0.25 pts) Selection Sort on an LRStruct:   Selection sorting is done by removing the minimum value from a list and re-inserting it at the front of the list.   Then, simply recursively sort the rest of the list.   By the time you reach the end of the list, it will be totally sorted.     Write a visitor called SelectionSortComp that uses the previously defined RemMinComp visitor to perform a selection sort on an LRStruct.   The visitor should mutate the list so that, in the end, the same list becomes sorted.    It doesn't matter what value is returned.
   
    
4. (0.50 pts) Write a visitor called SplitHalf to divide an LRStruct into two LRStructs, not by unzipping, but by dividing the list in the middle.   That is the list  (a, b, c, d) would mutate into (a, b) and return the list (c, d).     If there is an odd number of elements, the returned list should be the shorter of the two.    You do not need to calculate the length of the list!  The algorithm can be performed in a single pass through the list with no if-statements.
   
   Hints:
   • Think about accumulating the split point as the list is traversed.
   • Is the first recursive call really the same as the second recursive call? 
   • To truncate a non-empty LRStruct, simply set it's rest to be a new empty LRStruct.
   • The key to this algorithm is setting up the accumulator to keep track of where to split the list as you recurse into the list.   The accumulator lags behind the recursion point, and doesn't always advance each time the recursion advances farther into the list.
   • Consider the following scenario of advancing the accumulator as the recursion progresses through the list.  Notice how the accumulator is always at a point just before where the list will be split, that is the front of the list is truncated and the returned list begins:

   () -- empty list case, splitting would result in () and ().

   (a, ...)   -- non-empty list case, recursion is at a.   Need to recurse at least once to see if there are any more elements in the list.  Initialize accumulator to a.

   (a, b,...)  -- recursion is at b, but accumulator is at a.  If b was the empty list at the end, splitting now would mutate the host to (a) and return ().

   (a, b, c,...)  -- recursion is at c,  accumulator is still at a.    If c was the empty list at the end, splitting now mutate the host to (a) and return (b).

   (a, b, c, d,...) -- recursion is at d, accumulator is at b.   If d was the empty list at the end, splitting now would mutate the host to (a, b) and return  (c).

   (a, b,  c, d, e, ...) -- recursion is at e, accumulator is still at b.  If e was the empty list at the end, splitting now would mutate the host to (a, b) and return (c, d).

   (a, b,  c, d, e,  f, ...) -- recursion is at f, accumulator is at c.  If f was the empty list at the end, splitting now would mutate the host to (a, b, c) and return (d, e).

   (a, b, c, d, e, f,  g, ...) -- recursion is at g, accumulator is still at c.  If g was the empty list at the end, splitting now would mutate the host to (a, b, c) and return (d, e, f).

   (a, b, c, d, e, f, g, h, ...) -- recursion is at h, accumulator is at d.  If h was the empty list at the end, splitting now would mutate the host to (a, b, c, d) and return (e, f, g).

   In the above, how many different helper algorithms are needed to advance the accumulator only every other time the recursion advances?

   Is the accumulator the particular value or is it the list that starts with that value?

   What is the relationship between the list that starts with the accumulator and returned list?

   
    

5.  (0.25 pts) Definition: An empty binary tree is balanced.  A non-empty binary tree is said to be balanced if both of its subtrees are balanced and their height difference is at most one.  Given an ordered LRStruct of Comparable objects, construct a balanced BST BiTree containing the same objects.  Recursively apply SplitHalf to build the tree without comparing any objects.  (Thus, you cannot use the BSTInserter visitor because it compares objects.)  For example, the list (1 2 3 4 5 6 7 8) should produce:
   
                                   5
                                 /    \
                              3       7
                              / \      / \
                            2   4   6   8
                           /
                         1
   
   
    

6. Complete all the exercises in Lab. 15.
   1. Exercises
      1. (0.25 pts) SmartArray toSmartArray(Object[] source)
      2. (0.25 pts) String toString(Object[] elts)
      3. (0.25 pts) String toString()
      4. (0.25 pts) void add(Object elt)
      5. (0.25 pts) Object remove(int ix)
      6. (0.25 pts) Object[] toArray()
      7. (0.25 pts) SmartArray remDup()
      8. (0.25 pts) SmartArray unzip()
      9. (0.25 pts) void zip(SmartArray other)
   2. Additional Exercises
      1. (0.25 pts) util.ArrayUtil
      2. (0.25 pts) remDupBetter
      3. (0.50 pts) unzipBetter
      4. (0.25 pts) Replacing for loops with while loops

Last Revised Thursday, 03-Jun-2010 09:50:12 CDT

©2006 Stephen Wong and Dung Nguyen