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


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

For information on the extra credit Challenge Problem given in class, please see the bottom of this page.

100 pts:   Complete the extra-credit HW12

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

105 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);
    }
    
Where LRSEqual is the visitor from the 2006 Exam 2 (Prob. 2.ii).

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. (5 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. (5 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. (5 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. (10 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:

    () -- 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.  (5 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.  Technically, this algorithm doesn't depend on the LRS being ordered, but the resultant BiTree only makes sense as a BST if it is.   Note that the configuration of a balanced BST for any given set of values is not unique, which means that this problem has multiple possible solutions and results when run.   For example, the lists (1 2 3 4 5 6 7 8)  and (1, 2, 3, 4, 5) might produce:

                  4                     3
                /   \
                     /   \
             
     2      6               1     4
              /
    \   / \               \     \ 
             
    1   3  5   7               2     5
                    
       \
      
                      8

    You do NOT have to exactly replicate these examples, so long as your code produces a balanced BST.
     

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

 

205 pts total.


Challenge Problem (25-50 pts):

Write an IVisitor algorithm that returns the number of data elements in a BiTree, given the following restrictions:

  1.  The algorithm must be a forward accumulation algorithm.
  2. The algorithm must be fully tail-recursive.    The result of any recursive call cannot be further processed in any manner except to be immediately returned itself.  For instance, the recursive result from recurring down one sub-tree cannot be added to another value.
  3. The algorithm cannot use any data structure class or object that acts as a memory or storage device.   For example, a RAC cannot be used.   This essentially rules out any class with a field in it.   Classes or objects which are used purely for their behavior capabilities and not for any data storage capabilities are allowed.
  4. High quality coding is expected, e.g. the code should have maximal encapsulation with a minimum of exposed methods.

Your submitted challenge problem project should include full testing code.

Almost every concept used in this class will be needed to create this algorithm.

You may work in a group on this problem.  A minimum of 25 pts will be awarded for submitting an algorithm that meets the above requirements.  An additional 25 pts will be split amongst all contributors for a solution.   Be sure to include the names of all contributors in your submission!

Submit this problem SEPARATELY from your extra credit submission above.

 

 

 

 

 


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

©2008 Stephen Wong and Dung Nguyen