This is an assignment on generic programming that follows up on the in-class group exercise we did on Thursday, 12 February.
You may do this individually or in groups of two or three people. All members of a group are expected to contribute to the final product.
DivConq
that contains a method solve. Method solve
must be a template method for a broad family of
design-and-conquer algorithms. That is, it should implement the
general recursive divide-and-conquer algorithm with abstract
operations for the parts of the algorithm that vary among the specific
cases. (I distributed a few pages on divide-and-conquer algorithms
for the in-class exercise.)
One approach would be to make DivConq an abstract class
and solve a final method of that class. The
solve method calls other methods of the class that are
deferred. Then a specific algorithm can be implemented by extending
class DivConq by implementing the deferred operations for
the specific algorithm.
Another approach might be to make DivConq a concrete
class (perhaps final) and pass it (either as an argument
to the constructor or to solve) an object that implements
the needed abstract operations. (Use a Java interface to
specify the operations.)
If you use Pizza, you probably can make the abstract operations
functions that are passed into either the DivConq
constructor or the solve method.
There might be other reasonable ways to approach this. A solution
where you reimplement the general divide-and-conquer method
solve for each specific case is not
acceptable, however.
DivConq framework you developed above,
design and implement an algorithm to do a binary search.
Challenge: You might make the binary search itself quite generic. You could generalize it so that you can work with arrays of any type. Or you might consider a generalization where you can search the domain of function instead of an array.
UP to Engr 691 Assignments page?