|
Article Excerpt
One fundamental problem solving approach in computer science is
decomposition. While decomposition encapsulates a variety of perspectives, its explicitly elaborated perspectives are top-down and divide-and-conquer. This article focuses on illuminating additional, relevant perspectives. The perspectives are illuminated in two stages--first by their description and ties to diverse algorithmic tasks, and then through a concise illustrating example and a more involved case study. The case study includes stimulating alternative solutions, based on various decompositions. The decompositions are presented in a gradual process--from perspectives, through mathematical patterns, to design patterns, and algorithmic schemes. The pedagogical assets of the article are two-fold: general elaboration of multiple decomposition perspectives and particular illustrations of their effective application.
**********
Jl. of Computers in Mathematics and Science Teaching (2003) 22(4), 365-379
Problem decomposition is a primary problem solving method in computer science. Task decomposition into subtasks is a fundamental means in algorithm and software design. Recursive decomposition is the inherent design tool in functional programming and logic programming. Composition and decomposition of design patterns are basic operations with reusable solution schemes (Astrachan, Berry, Cox, & Mitchener, 1998; Clancy & Linn, 1999). Decomposition in the form of divide-and-conquer is an essential algorithm design technique (Aho, Hopcroft, & Ullman, 1983).
The explicitly advocated perspective in these decompositions is top-down, with the underlying principle of complexity-reduction by problem division into "smaller" subproblems. The "smaller" subproblems may be distinct, or similar to one another. Their combined outcomes yield the desired result. There is no doubt that top-down is the most common and prevalent decomposition perspective in algorithm design. However, it is not the sole one. There are additional decomposition perspectives, not explicitly indicated, yet very relevant and effective.
The objective of this article is to shed light on decomposition perspectives beyond top-down, and elaborate the notion of decomposition diversity. Illumination of diverse perspectives is a valuable pedagogical tool for improving novices' competence, as novices, unlike experts, lack the awareness of exploring a problem from diverse perspectives and capitalizing on the cues derived from these perspectives (Glaser, 1984; Schoenfeld, 1992).
The article illuminates decomposition diversity in two stages. First, various perspectives beyond top-down are named, described, and related to a broad variety of algorithmic solution schemes. Then, these perspectives are illustrated. The illustration includes a rather short example followed by a case study. The case study is presented in an explicit-instruction manner (Sloane & Linn, 1988). It displays how diverse decomposition perspectives yield different mathematical patterns, which in turn yield alternative problem solutions.
Case study presentation, which embodies the notion of apprenticeship (Linn & Clancy, 1992), is an appealing means for illuminating perspective diversity. It emphasizes the problem solving process over the end product. Particular elements are made explicit along the process, including design aspects, underlying patterns, and various pros and cons considerations. In teaching novices the skill of algorithm design, it is most beneficial to display diverse considerations and their resulting outcome (Soloway, Sphorer, & Littman, 1988; Linn & Clancy, 1992).
The next section, introduces diverse decomposition perspectives and motivates their relevance. Each perspective is tied to a variety of algorithmic schemes that appear in the literature, often without explicit reference to decomposition. The section, "Short Illustration: Triples of Integers," illustrates through a concise CS1 example the relevance and effectiveness of the introduced perspectives. The section, "Case Study: Majority in a Large Sequence," provides a more involved, "Introduction to Algorithms" illustration, as a case study. It presents the invocation and use of decomposition diversity in solving the challenging algorithmic task of finding majority in a large sequence of elements. Particular emphasis is put on the significant role of underlying mathematical patterns and their resulting design schemes. The final section concludes the presentation and underlines the elaboration of perspective diversity.
DIVERSE DECOMPOSITION PERSPECTIVES
Novices tend to explore very few, and rather unproductive paths to the solution (Schoenfeld, 1992). Although their domain knowledge is often sufficient, their lack of effective invocation of problem solving heuristics in the domain context significantly limits their competence. Experts, in contrast, demonstrate proficiency by successfully combining domain principles with general problem solving heuristics, even when their domain knowledge is degraded (Schoenfeld, 1992; Glazer, 1984).
Cognitive explanations of this phenomenon underline the well-organized knowledge and diverse perspectives of experts, acquired with experience. In particular, experts develop schemata that link domain inventory with problem solving techniques and strategies. The schemata encapsulate knowledge and perspectives developed through experience with domain objects in problem solving situations and events (Glazer, 1984; Gelman & Greeno, 1989).
In the domain of computer science, studies have shown that experts' acquisition of knowledge and perspectives is tied to schemata that enfold programming patterns (Linn, 1985; Soloway, 1986; Rist, 1989). Computer science educators offer the development of programming skills with a collection of "design patterns" (Astrachan et al., 1998; Clancy & Linn, 1999), also called idioms, schemas, or templates (Soloway, 1986;...
|
