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, binary partition 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 sliding delta 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 elementary patterns 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 these 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. -----