Sunday, 26 December 2010

Algorithms, Data Structures, and Patterns

I have a feeling that this may be revisiting an old theme but as I relate to others, I realise that old definitions seem to change little over time.

An algorithm is defined by the idea of a sequence of instructions. This definition corresponds well with imperative or procedural programming but not so well with the object-oriented paradigm. Guzdial and Ericson (2005) introduce the algorithm terminology in their programming test but it doesn't maintain any prominence. They initially refer to both programs and algorithms as recipes. They then talk of the study of recipes in terms of "How a recipe works" (algorithm), "the units used in recipes" (data structures), and type of recipes (pp 3-4). They do use a couple of more formal definitions. The first being that an "Algorithm is a description of a process apart from any programming language" (p 6). As such an algorithm "can be written in English" (p 6). In the second definition, they say "An algorithm is a description of behaviour for solving a problem" (p 516). Although they make some other references to algorithm, it doesn't have the focus that I would have expected from the way that it is introduced.

Data structures as suggested by Guzdial and Ericson are units used in algorithms but in teaching data structures, algorithms may be taught that describe how to manage the data structure. How an algorithm is implemented for a data structure depends on the implementation language or maybe more accurately the programming paradigm that the programmer is using.

My interest here is that we place an emphasis on teaching algorithms. Often universities teach algorithm and data structure papers but few that focus on design patterns. It makes me wonder whether the issue of the difference between imperative programming and object-oriented programming has really been examined or considered as a real issue.

In the debate on teaching object-oriented programming there was the proposal to use elementary patterns as foundation for teaching (Wallingford 1998). Partially as I expected these patterns include loop and selection patterns. These cover wider range of patterns that I taught in my introductory programming course in the early 1990s. The patterns can be used to build a base for reasoning about program design and for constructing more complex programming logic.

The question then is whether elementary patterns can be used to describe algorithms and data structures? If they can then maybe we should teach patterns in our introductory courses to lay the foundation for later learning.

Is it possible that patterns can be programming paradigm independent or is the link between a paradigm and a pattern very fixed? I think there is a pattern that can be applied across paradigms and it is these that should be the foundation of introductory programming courses. In the same manner as I used logic diagrams as a foundation for teaching imperative programming, we should be able to use the patterns as generic representations or abstractions that are them implemented in specific constructs.

A further extension of this elementary patterns thinking is introductory implementation patterns (Beck 2007). In theory, Beck's patterns are language specific but he had already produced a similar Smalltalk (1997) and there are some overlaps. It is these overlaps that are significant. The question is whether, other paradigms (i.e. functional, logic, ...) have implementation patterns? I am sure that there are but they may not be called patterns.

What I believe we can talk about and use to teach are foundational patterns that have variable implementations in different programming paradigms.

The other use of patterns is pedagogical patterns (Bergin 1998, 2000). These tend to focus on class room practice rather than planning content. You could say they are teaching best practice.

From my own research, I am focused on patterns of variation in content that help bring focus to what should be learnt. Marton et al. (2003) have described four patterns of variation. What I would like to see is these formalised in a way that is easier to apply.

What I am looking at is utilising patterns as the building blocks for a course. Patterns of variation are used in conjunction with pedagogical patterns to teach elementary patterns that are implemented in the programming language.

References

Beck, K. (1997). Smalltalk best practice patterns (1st ed.). Upper Saddle River, NJ: Prentice Hall.

Beck, K. (2007). Implementation patterns. Upper Saddle River, NJ: Addison Wesley

Bergin, J. (1998, 11 May 2002). Some pedagogical patterns, from http://csis.pace.edu/~bergin/patterns/fewpedpats.html

Bergin, J. (2000, July). Fourteen pedagogical patterns, from http://csis.pace.edu/~bergin/PedPat1.3.html

Guzdial, M., & Ericson, B. (2005). Introduction to computing & programming with Java: A multimedia approach. Upper Saddle River, NJ: Prentice Hall.

Marton, F., Runesson, U., & Tsui, A. B. M. (2003). The space of learning. In F. Marton & A. B. M. Tsui (Eds.), Classroom discourse and the space of learning (pp. 3-40). Mahwah, NJ; London: Lawrence Erlbaum Associates, Publishers.

Wallingford, E. (1998, 17 July 1998). Elementary patterns and their role in instruction: A report on the ChiliPLoP'98 hot topic workshop, from www.cs.uni.edu/~wallingf/patterns/elementary/chiliplop98/summary.html

No comments: