TITLE: Algorithmic Patterns
AUTHOR: Eugene Wallingford
DATE: July 21, 2004  5:38 PM
DESC: algorithmic patterns need forces and context
-----
BODY:
The most recent SIGCSE Bulletin (Volume 36, Number 2, June 2004) reached
my mailbox yesterday.  Several articles caught my eye, and I'll probably
write each about them over the next week or so.

I turned first to David Ginat's article on algorithmic patterns.  David
and I had a nice chat about elementary patterns during a lunch at SIGCSE
2003, so I knew of his interest in how the ideas of patterns might help
us to understand algorithm design better, or at least to help us help our
students to understand it better.

What is an algorithmic pattern?  Ginat distinguishes between the mathematical
features of an algorithm, such as boundaries on a sequence of search ranges,
and the computational features of how it might processes data.  For Ginat,
and algorithmic pattern combines mathematical features with a certain
computational "theme".  For example, <I>binary partition</I> is an
algorithmic pattern whose computational theme is "processing by halves"
and whose mathematical core is a log n bound on the number of partitions
considered.

The bulk of this paper illustrates the value of thinking in terms of an
algorithmic pattern, using the Ginat's example of the <I>sliding delta</I>
pattern.  A sliding delta is an on-the-fly accumulator that enables an
algorithm to compute a value of interest by updating the accumulator as
it encounters new data values.  This counting pattern shows up in many
forms, from computing the winner of an election to determining the maximally
covered point in a collection of ranges.  Ginat defines this pattern as a
computational theme-mathematical core pair and illustrates its application
to several seemingly disparate problems.

The assertion that struck closest to home for me is that students who
don't know about the sliding delta pattern are almost certainly doomed to
implement naive and incredibly inefficient solutions to common problems
in computing.  In the best possible world, a student may implement a
sliding delta, but only after going through laborious effort to discover
the idea.

This is one of the driving ideas behind the
<A HREF="http://www.cs.uni.edu/~wallingf/patterns/elementary/">elementary
patterns</A> project.  Students learn best when they learn the patterns of
a domain, because these are the structures they will want to build into
their algorithms, their designs, and their code.  I design my courses on
design and programming around the elementary patterns students need to
know.  I'm even designing my fall algorithms course around what Ginat
calls algorithmic patterns.

But to me, they are just patterns.  Calling them 'algorithmic' patterns,
to distinguish them from 'design' patterns and 'coding' patterns, does
serve a useful purpose, I suppose.  It may help his readers avoid any
negative connotations they have associated with the older terms.
("Design patterns are too complex for my students."  "Coding patterns
are just idioms.")

Recognizing algorithmic patterns as patterns can help us to make them
more useful.  Ginat's pattern form lacks a couple of elements considered
essential by the patterns community.  Their absence accounts for my only
misgiving about this paper:  Just showing students patterns isn't enough.
They need to learn when to use the pattern.

For examples, how do I know when to use a sliding delta?  What features
of a problem push me toward a sliding delta?  What features push me away
from the pattern?  When I use a sliding delta, what new problems may result,
and what other patterns could help me resolve them?

Context.  Forces.  Resulting context.  Defining <I>these</I> for the
sliding delta pattern would make it a lot more useful to its readers.
They are essential knowledge for any algorithm designer: how to balance
the requirements of the problem and its context with the features of
the pattern.

Ginat laments that students often don't apply sliding delta to problems
like his Dot Connections and Crocodiles.  He suggests that introducing
students to the pattern and occasionally categorizing problems solved by
the pattern will be enough to help them learn to apply the pattern to
new problems.  He does hint at more, though -- the instructor should
"underline the effective role" of the pattern.  Perhaps we can abstract
from this information some wisdom for recignizing a pattern's effectiveness
beforehand?

I hope that my suggestion for improvement doesn't give the wrong impression.
I like Ginat's idea a lot.  I think this paper is a contribution to CS
education, and I hope he develops this area further.  I do hope, though,
that he'll document the forces that drive algorithm design.  They are the
key to design -- and to learning how to design.  As a Chinese adage holds,
the Master paints not the created thing but the forces that created it.
-----