Engr 691-06: Special Topics in Engineering Science
(Software Families)
Fall 2011
Assignment #3, Due Thursday, 3 November, Midnight

You may do this assignment as an individual or in groups of two students.

This assignment requires that you use the small Divide-and-Conquer framework described in Section 3 of the paper "Using Classic Problems to Teach Java Framework Design". Note that the paper describes the framework (DivConqTemplate, DivConqContext, and DivConqStrategy classes and Problem and Solution interfaces) and a sample quicksort application built using the framework.

Tasks:

• Use the Java or Scala version of the framework supplied by the instructor or implement the framework in some other reasonable object-oriented programming language of your choice.

• Generalize the given quicksort application to work for an array of more general objects. You cannot assume that these objects are builtin objects with predefined comparison operators, but you can assume that a total ordering can be defined on the set of all the objects that you need to sort in one execution of the program.

So you will need to work out a technique for defining the comparison in a manner that is flexible and supports resuse of the quicksort code. That is, it should not be necessary to modify the quicksort classes to change the type of objects. MODIFICATION: If you are using the Java version of the framework the instructor supplies, you may modify the classes and interfaces in the framework to be generic, taking type paramters for the Problem and Solution types. The Scala version of the framework does this.

• Implement a binary search algorithm using the framework.
• Implement some other divide and conquer algorithm using the framework--for example, mergesort or matrix multiplication.
• Test all implementations thoroughly.
• Document the code appropriately.

When this assignment is complete, submit the following items. Be sure that all items submitted are clearly labeled with your name and the assignment number.

• To the Blackboard site, electronic copies of:
  • the source code files for your applications of the framework (and for your reimplementation of the framework if you use a different language),
  • instructions on how to build and execute your programs,
  • a copy of the input files or test driver programs you used for testing.

• To your instructor, a paper listing of your program source code and the outputs from your testing of the program.

UP to ENGR 691 assignments document?