Orna Muller

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.