Computer Science Group
Science Education Department
School of Education
Tel-Aviv University
Tel-Aviv, Israel
Elaborating Algorithmic
Patterns
for Developing Analysis
and Design Skills
Background
Psychological research suggests that programming expertise is partly represented by a knowledge base of pattern-like chunks, various named plans, templates, schemas or idioms [1,2,5,6,10,13]. Expert programmers have and use two types of programming knowledge: Programming plans, which are generic program fragments that represent stereotypic action sequences in programming, and rules of programming discourse, for composition of the plans into programs [11]. The notion of programming plan corresponds to the concept of schemas in diverse domains [9,11,12]. Similarly, templates are referred to as cohesive pieces of programming knowledge that link related information about a component of a program [5,8].
A
wide variety of research shows that good knowledge organization helps students
remember and reuse the information that they have learned [5]. Given a problem, the expert
programmer can retrieve the appropriate plan from memory [6]. When a plan cannot
be applied, a common strategy is to decompose the problem to subproblems.
Studies of expert programming revealed that knowledge of
programming was organized in larger conceptual structures rather then syntax,
involving algorithms and associated information.
Novice programmers usually do not
employ stepwise refinement as a design tool. They have not yet developed the
program patterns that allow the problem to be matched with a previously learned
solution [6,10]. Students often use a language
syntax-oriented organization of programming knowledge because that is how
information is presented. As a result, students have difficulty assembling
algorithms.
Within the “expert-novice” paradigm educators may identify the productive behavior of
competent problem solvers and use such behavior as a guide for instruction for
novices [9].
Experts are not always conscious of
the knowledge and strategies they employ [10]. The process of defining and using
patterns serves as opportunities to make this knowledge explicit.
The later concept of Design Pattern is introduced in the context of
object-oriented software design, as an attempt to capture the best practice in a
domain and to transfer the knowledge to other practitioners, designing solutions
to similar software design problems [1]. Design Patterns definition comprised of
the pattern’s name, motivation for use (the problem which provides a context in
which the pattern is applicable), components, results and tradeoffs of applying
it, sample code, examples of its use, and related patterns [1,2].
Efforts of developing programming
and pedagogical frameworks that supply support for using patterns throughout a
CS curriculum, in on-line templates libraries and courses organized around
selected patterns, are reported [1,2,8,13]. Most work was done for recognition,
cataloging and finding of patterns. Formal research on the effectiveness of
explicitly referring to templates and design patterns in the teaching of CS1 and
CS2 was conducted so far in a very limited extent [1,13].
In addition, a common pedagogical
approach, of introducing new CS concepts in an interweaving way with programming
language features (named: “Zipper approach”), is adopted in CS first courses
[3]. As a consequence, problems introduced to students are usually grouped and
directed for using those language features. While the focus on recurring
programming constructs is fundamental, a shift to an algorithmic perspective,
which combines correctness, efficiency, and conciseness considerations, may
yield to valuable results with respect to developing algorithm design and
analysis skills.
Research
Goals
Slightly
different patterns, Algorithmic Patterns, were defined by the Computer
Science Teaching group (I am a member of) in Tel-Aviv University. Supporting
instruction materials for high-school Computer Science Fundamentals course are
developed, aimed to emphasize algorithmic problem solving while introducing the
CS patterns concept. A set of about thirty AP’s was developed.
An Algorithmic
Pattern (AP) is a solution to a recurring algorithmic task, like:
computing the maximal value in a list, checking a list for existence of an
element that fulfils a given condition, and
circular shifting of a list of values.
AP’s
are problem oriented: they are linked to the problem they solve, and not to
programming language constructs, assuming that this may lead to an easier
recognition of analogical elements when facing a new algorithmic
problem.
An
Algorithmic Pattern definition contains several components (some synthesis of
Design Patterns and Plans definitions [1,2,10]): A name which captures the
essence of the task it performs, The initial state of the problem (what is
given), The goal which is its desired outcome, An algorithm for achieving the
goal which is “the heart” of the pattern, and Remarks that link a pattern to
related patterns, emphasize significant similarities and differences between
them, consider applicativity of the pattern in different situations, and other
characteristics of the pattern.
Algorithms
are written in pseudocode, and not in a particular programming language. In
order to make AP’s be associated with fundamental algorithmic problems they are
categorized and divided into groups: Numerical Computations, Searching and
Properties identifying, Counting and Accumulation, and Ordering, according to
the type of problem they solve.
The
collection of AP’s serves as a “toolbox” for developing algorithms, since the
schematic core each pattern represents reappears in a variety of contexts. The
pattern names extend the vocabulary used by instructors and students while
discussing problems and solutions.
The
abstractive nature of the pattern may be assimilated after using it in a large
variety of instances [7]. Materials include a variety of example problems to be
solved after introducing a new AP.
Problems are organized in a progressive manner. At first, solution to
problems can use AP with no or minimal modification, and later problems need
more significant accommodation work.
AP’s
may not be introduced to but explored by the students, when recognizing a
general principle or similar ideas recurring in different situations. Instructor
and students are encouraged to create new AP’s, beyond those defined, assuming
that the process enhances analogical thinking and
abstraction.
Materials
also define three methods for combining AP’s in an algorithm (also in [10]):
sequentially, by nesting, when one pattern contains another as a block, or by
merging, when two or more patterns are interleaved.
More
advanced problems demand using more than one pattern. They usually can be solved
in more than a single way, each involves different AP’s. An important issue concerns analyzing a
solution for its efficiency. Algorithm efficiency is a fundamental computer
science concept and (without the formal measures of complexity computation) can
be introduced early, in CS fundamental courses [3,4]. A student is asked to
compare the efficiency of solutions utilizing different AP’s, or combining them
differently.
Algorithmic
Patterns can be looked at in two perspectives. The first is: “as a whole” or a
“building block”. Reuse of the pattern is done by invocation of the pattern by
its name. The second is: As an “idea”, usually of a mathematical nature, that
enriches ones’ repertoire, and can be transferred to different problems. This
means that the algorithm components and logic must be well understood and
described explicitly!
Assimilation
process of the AP materials among teachers in
the field through lectures, workshops, booklets, and a designated web site
produced encouraging (informal) feedback so far. The pattern definition which is
independent of specific programming language, the method of organizing the
patterns by categories, and the variety of nonroutine problems presented are
accepted with much interest. Data collected during assimilation will serve as an
input for future research.
Research
goals are revealing and getting an insight of how, if at all, applying AP’s to
school CS program improves analogical reasoning, abstraction, and algorithm
analyzing and developing skills: Does learning with algorithmic patterns yield
effective insight into an algorithmic problem, decomposing a problem to
subproblems and invocation of suitable design components? Does using patterns
help students in identifying analogical elements in problems, and using a
precise language when describing the main idea of a solution (algorithm)? Does
learning with algorithmic patterns elaborate students’ confidence in their
algorithmic problem solving ability?
Current
stage
I am a first year
PhD student, currently writing my research proposal.
Joining the
Doctoral Consortium, I believe I can benefit from being acquainted with work
done on various topics by students in a more advanced stage, and from their
experience. I will also be glad to get others’ feedback to my research plans.
References
1.
Astrachan,
O., Berry, G., Cox, L., Mitchener, G. (1998). Design Patterns: An Essential
Component of CS Curricula. In The Papers of the Twenty-Ninth SIGCSE Technical
Symposium on Computer Science Education. ACM Press, pp.
153-160.
2.
Clancy,
M.J., Linn, M.C. (1999). Patterns and Pedagogy. Proceedings of the 29-th
SIGCSE Technical Symposium on CS Education, pp. 37-42.
3.
Gal-Ezer,
J., Beeri, C.,Harel, D.,Yehudai, A. (1995). A High School Program in Computer
Science. Computer , 28(10), pp. 73-80.
4.
Ginat,
D. (2001). Early Algorithm Efficiency with Design Patterns. Computer Science
Education. 11(1), pp. 1-21.
5.
Linn,
M.C., Clancy, M.J. (1992). The Case for Case Studies of Programming Problems.
Communications of the ACM, 35(3), pp. 121-132.
6.
Rist,
R.S. (1989). Schema Creation in Programming. Cognitive Science, 13, pp.
389-414.
7.
Robins,
S., Mayer, R.E. (1993). Schema Training in Analogical Reasoning. Journal of
educational Psychology, 85(3), pp. 529-538.
8.
Schank,
P., Linn, M.C. (1993). Supporting Pascal Programming with an on-line Template
Library an case studies. Interntional Journal of Man-Machine studies. 38,
pp.1031-1048.
9.
Schoenfeld,
A.H. (1992). Learning to Think Mathematically: Problem Solving, Metacognition,
and Sence Making in Mathematics. In D.A. Grouws, (Ed.) Handbook of Research
on Mathematics Teaching and Learning. New York: Macmillen Publishing
Company, pp.334-379.
10.
Soloway,
E. (1993). Learning to Program=Learning to Construct Mechanisms and
Explanations. Communications of the ACM, 29(9),
pp.1031-1048.
11.
Soloway,
E., Ehrlich, K. (1984). Empirical Studies of Programming Knowledge. IEEE
Transactions on software engineering, 10(5),
pp.595-609.
12.
VanLehn,
K., Jones, R.M. (1993). What mediates the self-explanation efect? Knowledge
gaps, schemas or analogies? Proceedings of the 5-th Annual conference of the
Cognitive Science society, pp.
1034-1039, Hilldale, N.J. Laurence Erlbaum.
13.
Wallingford,
E. (1996). Toward a first course based on object-oriented patterns. In The
Papers of the Twenty-Seven SIGCSE Technical Symposium on Computer Science
Education. ACM Press, pp. 27-31.