Transcript Using the Divide an Conquer Strategy to Teach Java

Using the Divide & Conquer
Strategy to Teach Java
Framework Design
Conrad Cunningham, Yi Liu
University of Mississippi
Cuihua Zhang
Northwest Vista College
Purpose

Use a familiar topic such as divide and
conquer to introduce students to more
alien-sounding concepts
– Program families
– Frameworks
– Design patterns
2
Program Family
Set of programs
– sharing many common properties
– worthwhile to study (and design) as a group
David Parnas:
“If you are developing a family of programs,
you must do that consciously, or you will
incur unnecessary long-term costs.”
3
Framework


Generic application allowing creation of
specific members of family
In OOP, framework described by
– set of abstract classes
– way that instances of those classes collaborate

Family members
– share same abstract classes
– differ in implementations of concrete classes
4
Design Pattern
Well-established solutions to
recurring program design
problems
5
Framework Design

Identify common aspects (frozen spots)
– represent by set of ABSTRACT classes that
collaborate in some structure
– implement common behaviors by concrete
template methods in base class

Identify variable aspects (hot spots)
– represent by abstract hook methods in base class
– realize by concrete methods in an application of
the family
6
Framework Construction
Principles


Unification
– use inheritance to implement hotspot
subsystem
Separation
– use delegation to implement hotspot
subsystem
7
Template Method Pattern
Unification principle
AbstractClass
TemplateMethods
HookMethods
ConcreteClass
HookMethods
8
Strategy Pattern
Separation principle
Context
TemplateMethods
strategy
Strategy
HookMethods
ConcreteStrategyA
ConcreteStrategyB
ConcreteStrategyC
HookMethods
HookMethods
HookMethods
9
Divide & Conquer Approach

Divide original problem into
subproblems of same type

Solve each subproblem independently

Combine subproblem solutions into
solution for original problem
10
Well-Known Examples






Mergesort
Quicksort
Heapify
Binary search
Fast matrix multiplication
Fast Fourier Transform (FFT)
11
Example: Mergesort
1 12 10 6
1
12
10
12
1
6
10
6
6
1 12
10
1 6 10 12
12
Divide & Conquer Pseudocode
function solve(p)
{ if isSimple(p)
return simplySolve(p);
else
{
Problem [] sp = decompose(p);
for (i = 0; i<sp.length; i = i + 1)
sol[i] = solve(sp[i]);
return combine (sol);
}
13
Divide & Conquer Functions


template method:
– solve()
hook methods:
– isSimple()
– simplySolve()
– decompose()
– combine()
14
Framework:
Template Method Pattern
DivConqTemplate
final void solve()
abstract isSimple()
abstract simplySolve()
abstract decompose()
abstract combine()
QuickSort
MergeSort
isSimple()
simplySolve()
decompose()
combine()
isSimple()
simplySolve()
decompose()
combine()
Divide and Conquer
BinarySearch
isSimple()
simplySolve()
decompose()
combine()
15
Template Method Class
abstract public class DivConqTemplate
{ final public Solution solve(Problem p) // takes Problem description
{
Problem[] pp;
// and returns Solution description
if (isSimple(p)) { return simplySolve(p); }
else
{ pp = decompose(p); }
Solution[] ss = new Solution[pp.length];
for(int i=0; i < pp.length; i++)
{
ss[i] = solve(pp[i]); }
return combine(p,ss);
}
abstract protected boolean isSimple (Problem p);
abstract protected Solution simplySolve (Problem p);
abstract protected Problem[] decompose (Problem p);
abstract protected Solution combine (Problem p, Solution[] ss);
}
16
Framework Application:
Quicksort



Divide and conquer task: sort a sequence in place
Mapping problem into divide and conquer framework
– decompose: partition into two segments about a
pivot value (rearranges values in array)
– recursively sort each segment until just one
element (isSimple and simplySolve)
– combine: values already in needed location
Describing the problem and solution
– identify sequence of values
– identify beginning and ending elements of segment
17
Problem and Solution
Description
Simplifying assumption: sort integer arrays
 Problem description for sort
– overall array
– beginning and ending indices of segment

Solution description for sort
– same as Problem description
– except array values rearranged in place

QuickSortDesc object to represent both
18
QuickSortDesc Class
public class QuickSortDesc implements Problem,Solution
{ public QuickSortDesc(int[] arr, int first, int last)
{
this.arr = arr;
this.first = first; this.last = last;
}
public int getFirst () { return first; }
public int getLast () { return last; }
private int[] arr;
private int first, last;
}
19
Quicksort Subclass (1 of 3)
public class QuickSort extends DivConqTemplate
{
protected boolean isSimple (Problem p)
{
return ( ((QuickSortDesc)p).getFirst()
>= ((QuickSortDesc)p).getLast() );
}
protected Solution simplySolve (Problem p)
{
return (Solution) p ; }
20
Quicksort Subclass (2 of 3)
protected Problem[] decompose (Problem p)
{
int first = ((QuickSortDesc)p).getFirst();
int last = ((QuickSortDesc)p).getLast();
int[] a = ((QuickSortDesc)p).getArr ();
int x = a[first]; // pivot value
int sp = first;
for (int i = first + 1; i <= last; i++)
{
if (a[i] < x) { swap (a, ++sp, i); } }
swap (a, first, sp);
Problem[] ps = new QuickSortDesc[2];
ps[0] = new QuickSortDesc(a,first,sp-1);
ps[1] = new QuickSortDesc(a,sp+1,last);
return ps;
}
21
Quicksort Subclass (3 of 3)
protected Solution combine (Problem p, Solution[] ss)
{ return (Solution) p; }
private void swap (int [] a, int first, int last)
{ int temp = a[first];
a[first] = a[last];
a[last] = temp;
}
}
22
To Build a Framework



Represent common aspects as abstract
classes and concrete template methods
Represent variable aspects as abstract
hook methods and concrete hook
methods in hot spot subsystems
Organize using unification or separation
principle
23
To Use a Framework

Implement concrete hook methods

Plug subsystems into hot spots
24
Educational Observations





Students should learn to design program families
Students should be explicitly taught appropriate
design and programming techniques
Frameworks are understandable by students familiar
with OOP
Divide and Conquer algorithmic strategy provides a
familiar, understandable environment for learning
Other exercises are needed to teach students to
identify and design appropriate hot spots
25
Summary



Targeted at Java programming or software
design courses
Provides a simple example to teach
computing students design and use of
frameworks
Aimed at improving students’ abilities to
construct and use abstractions in design of
program families
26
Acknowledgements

Acxiom Corporation grant
– “Acxiom Laboratory for Software
Architecture and Component
Engineering (ALSACE)”

Students in ENGR 660 in Fall 2003
27