Engr 691-12: Special Topics in Engineering Science
Software Architecture
Fall Semester 2000

Assignment #3
4:00 P.M., Monday, 23 October, 2000

This is an individual programming assignment.

1. Design and implement a Java class 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 divide-and-conquer algorithm with abstract operations (i.e. hook methods) for the parts of the algorithm that vary among the specific cases. Most of the information should be passed among the methods as method arguments and function return values. (See the attachment for more information on the divide and conquer approach.)

   One approach would be to use the Template Method pattern, that is, 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 would be to use the Strategy pattern, that is, 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. You can use a Java interface to specify the operations on the Strategy class.

   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.

2. Using the 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.

3. Implement at least one other divide and conquer algorithm with your package. Possible algorithms include mergesort, quicksort, matrix multiplication, exponentiation, selecting the kth smallest element, and the Fast Fourier Transform.

4. Document and test your programs appropriately. When complete, submit a paper listing of your source code. Also submit a listing showing your testing of the package. I also ask you to submit an electronic copy on a diskette (unless I give you other instructions later).

UP to Engr 691 Assignments page?