|
Comp201: Principles of Object-Oriented Programming I
|
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.
Submit this part of the extra-credit work as instructed in HW 12.
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));
() -- 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
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.
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:
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