Decomposition diversity in computer science--beyond the top-down icon.

         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; Rist, 1989; Linn & Clancy, 1992). Design patterns are viewed as essential building blocks for designing modular and well-structured computer programs.

The teaching of program design with patterns is strongly tied to modular, top-down decomposition. The elaboration of top-down is most evident in the basic courses of programming and software design. It also transfers to the more advanced course of "Introduction to Algorithms," with the explicitly indicated design technique of divide-and-conquer (Aho et al., 1983; Cormen, Leiserson, & Rivest, 1991). In top-down, the decomposition is focused on recognition of subfunctions of the original task. The subfunctions may considerably vary. In the particular case of divide-and-conquer, the decomposition is focused on subfunctions that are reduced instances of the same function. Although very effective in numerous applications, these decompositions capture some, but not all, decomposition aspects.

Decomposition encapsulates partitioning. There are decomposition perspectives where the focus is on partitioning by values or locations of elements rather than by functionality of subfunctions. One such perspective is range decomposition. The concept underlying this perspective is that partitioning of the range of element values into subranges may yield effective processing schemes. Several data structures and algorithmic schemes are derived from this perspective. The concept of Hashing is based on partitioning the set of key values into subsets (according to some mapping function h(k)) (Aho et al., 1983). The scheme of Skip-Lists employs nested levels of lists used for coarse-grain-fine-grain searching in subranges of sought-after keys (Pugh, 1990). In the domain of distributed algorithms, the very efficient Mutual-Exclusion algorithm by Maekawa is based on partitioning a 1..N node-range into subranges of sqrt(N) size (Maekawa, 1985).

Another perspective, related to partitioning is element decomposition into subpieces. The notion behind this perspective is that partitioning of elements into their "atomic" components offers the inventive aspect of processing data elements by their subpieces. The fundamental sorting algorithms of Radix-Sort and Bucket-Sort are based on processing data "across" the input, digit by digit (Aho et al., 1983). The digits of each input element are separated and regarded as "atomic" subpieces. A variety of graph algorithms are based on processing by "atomic" bit components. Gabow's scaling algorithm for Single-Source Shortest Path is based on uncovering bits in the binary representation of graph-edge weights (Cormen et al., 1991). The 1-1 mapping between Euler Circuits and De-Bruijn Sequences stems from path construction by bits (Even, 1979). The fundamental scheme of Routing in Cubes and Hypercubes is based on binary representation of node names, where neighboring node names differ by exactly one bit (Manber, 1989). Processing by bits is the underlying principle in efficiently calculating the [N.sup.th] Power of a given number in O(lo[g.sub.2](N)) time (Manber, 1989).

A third perspective beyond top-down decomposition is linear decomposition. A solution derived from this perspective involves linear, inductive decomposition of a sequence of values into a short prefix, and a remaining postfix. The prefix is usually processed first, before advancing to the remaining postfix. Many algorithmic schemes derive from this perspective, but are not explicitly presented as the outcome of decomposition. On the fly computations, such as Polynomial Evaluation and Maximal Consecutive Subsequence (Manber, 1989), are two examples. In a broader sense, the idea of greedy computations (Cormen et al., 1991) involves this decomposition perspective. Decompositions that stem from this perspective can often be elegantly expressed with inductive invariant assertions.

Decomposition is a general problem solving heuristic (Polya, 1957). The previous perspectives relate it, through multiple aspects, to the specific domain of algorithm design. The explicit tie between a general problem solving element and a particular domain activity is a valuable pedagogical asset (Glazer, 1984; Gelman & Greeno, 1989). The following sections illustrate this tie with two particular examples.

SHORT ILLUSTRATION: TRIPLES OF INTEGERS

The following algorithmic task is a rather simple CS1 exercise. While some tutors may display its solution without particular reference to decomposition, we believe that the elegant way of solving it captures in a nutshell the decomposition perspectives described in the previous section.

     Same-Average Triples

     Given a positive integers N, generate all the triples of positive
     integers for which the average is N (consider triples such as
     <i,j,k> and <j,i,k> distinct from one another). In addition,
     indicate whether one of the triples is composed of three different
     powers-of-2.

     Examples: For the input 2, the output should include the following
     triples: <1,1,4> <1,4,1> <4,1,1> <1,2,3> <1,3,2> <2,1,3> <2,3,1>
     <3,1,2> <3,2,1> <2,2,2>; and an added note will indicate that there
     is no triple composed of three different powers-of-2. For the input
     7, the output should mention that there is a triple composed of
     three different powers-of-2 (e.g., the triple <1,4,16>).

For the first part of the task, some inexperienced programmers may not recognize an elegant enumeration scheme and perform an exhaustive search for the relevant triples through the range <1,1,1> ... <3N,3N,3N>. Others may try to generate the elements of each triple by viewing them from a "center of gravity perspective" as elements that are located in "balanced locations on two sides of the center." The former approach is very inefficient, and the latter is error-prone. For the second part of the task, we may expect most novices to check the elements in each triple for three different powers-of-2.

The elegant solution for both parts encapsulates decomposition perspectives. The sum of the three integers in each triple is 3N. One may view the first part of the task as generation of all the different partitions of the range {1, 2, 3 ... 3N} into three parts. The three part-sizes of each partition will embody a triple. The generation of the various triples of part-sizes will be performed in a linear, inductive decomposition process.

"Algorithmically speaking," two variables, i and j, will keep the sizes of the "left" and "middle" parts of each partition, and the expression 3N-i-j will keep the size of the "right" part. In the linear decomposition process, the variable i will be "run" inductively from 1 up to 3N-2, and j will be "run" from 1 up to 3N-i-1 for each value of i. Thus, for the input 2, the algorithm will first generate <1,1,4> <1,2,3> <1,3,2> <1,4,1>; then - <2,1,3> <2,2,2> <2,3,1>; then - <3,1,2> <3,2,1>; and finally - <4,1,1>.

For addressing the question of whether there is a triple composed of three distinct powers-of-2, it is most beneficial to turn to the binary representation of the sum 3N of the elements in a triple. The binary representation of 3N is composed of a sequence of atomic bits. If exactly three bits in the representation of 3N equal "1," then we can construct 3N by adding three different powers-of-2, which are three different binary numbers of the form 10 ... 0. Otherwise, such construction is impossible. For example, for the input 7, the binary representation of 21 is 10101, which equals the sum of: 10000, 100, 1 (implying the output "Yes"). For the input 2, the binary representation of 6 is 110, which equals the sum of only two distinct 10..0 binary numbers - 100 and 10 (implying the output "No").

In retrospect, we see the relevance of the three decomposition perspectives presented in the previous section. Range decomposition yielded the view of triples as range-partition sizes. Linear decomposition yielded a systematic enumeration of triples by inductively increasing the first and the second triple elements. Element decomposition yielded the view of bit values in determining different powers-of-2.

CASE STUDY: MAJORITY IN A LARGE SEQUENCE

The following, rather unfamiliar algorithmic challenge yields appealing alternative solutions that derive from decomposition. The most efficient and elegant solution was introduced by Boyer and Moore (1991). We devised two additional, enriching solutions. The three solutions are gradually presented, from the less efficient to the more efficient.

     Majority in a Large Sequence

     Imagine elections in a huge population and a very large set of
     candidates. Given a sequence of N integer votes, each in the range
     1..R of candidates, develop an algorithm for determining whether
     one of the values in the sequence of votes appears over N/2
     times. If there is such a value, then output it, otherwise output
     0.

     Assume that N and R may be very large - up to [2.sup.30], and the
     computer memory may only hold up to [2.sup.15] variables. An
     input scan is not a very cheap operation, time-wise, but one or
     two extra scans are allowed.

     Examples: For the sequence of integers: 3 5 6 5 5, the output
     should be 5; and for the sequence of integers: 3 5 6 5 5 4, the
     output should be 0.

Had the input sequence been short or the integer range small, the algorithmic task would be trivial. Either sorting, or simple counting could be used. For the latter, an array of counters--one for every possible integer value--would accumulate the number of appearances of each input value. Unfortunately, it is impossible to keep in memory an array of size larger than [2.sup.15], and there may be up to [2.sup.30] unique values.

One scan over the very long input seems insufficient. Yet two or three scans are allowed. How may one benefit from this? One who follows the top-down/divide-and-conquer approach may try to devise a scheme of combining results of "majority-finding" in subsequences of the original input sequence. Such a scheme may be conceptually similar to Polyphase Merging in external sorting (Aho et al., 1983). However, there are two difficulties with this approach. First, it is not clear what result should be passed between phases of subsequence processing. Second, the limited memory size compared to the very long input sequence may yield many computation phases and many scans over the input. A different approach should be taken.

Range Decomposition

We noticed that "appearance-counting" for each possible value is impractical. However, the notion of appearance-counting may become practical if combined with decomposition. It may be beneficial to decompose the range of the possible input values into subranges, and perform appearance-counting of subranges. This yields the following solution idea: partition the original, very large range of possible element values into subranges; identify a subrange where the majority value resides; and look for the majority value in this subrange.

We call majority element the integer that appears a majority number of times in the input, and majority subrange a subrange whose elements appear a majority number of times in the input. We specify the following mathematical pattern about the relation between the majority element and the majority subrange:

Upon partitioning the original range into a set of disjoint subranges:

    If there is a majority element, then there is a majority subrange;
    otherwise, there may or may not be a (single) majority subrange.

Following this, it is possible to "zoom into" the majority element in stages. The original range will be partitioned into disjoint subranges, and a coarse-grain counting followed by a fine-grain counting will be performed in two separate scans over the input.

    1st Scan: Count for each subrange the number of its element
    appearances in the input; if there is a majority subrange, then
    perform the 2nd scan, else output 0.

    2nd Scan: Count for each element in the majority subrange
    the number of its appearances in the input; if there is a majority
    element, then output its value, else output 0.

The number of scans over the input is low enough. Is the memory cost low enough? Each scan requires an array of appearance counters. In the first scan, every input element will yield a counter increment, and different elements may cause the increase of the same counter. In the second scan, only input elements that belong to the majority subrange will contribute to the counting (each to a different counter).

The array of counters for the 1st scan can be reset and reused in the 2nd scan. The number of subranges dictates the number of elements per subrange and vice-versa. What is the lowest size for the array, given this constraint? The following pattern implies the optimal size:

     In an R-element range, which is partitioned into k intervals of R/k
     elements each, the lowest value which bounds both k and R/k is
     sqrt(R).

We return to the task data. Based on this pattern, we can partition the original integer range of size [2.sup.30] into [2.sup.15] subranges of [2.sup.15] elements each. Thus, each of the two scans will require [2.sup.15] counters, a valid bound for the array. (If we want to further reduce the bound on the array, we can extend the 2-scan scheme to a K-scan (K>2) "zooming" scheme.)

All in all, the previous solution scheme requires a total of sqrt(R) counters, where R is the range size of the input values. The scheme meets the task constraints of limited memory size and very limited number of scans over the input. Its implementation involves recurring utilization of two basic design patterns: simple mapping (element value into subrange) and counting.

The solution encapsulates range partitioning and a coarse-grain-fine-grain progress through a "zooming-in" process. Examples of range partitioning and coarse-grain-fine-grain schemes were mentioned in "Diverse Decomposition Perspectives." The notion of zooming-in appears in further examples, such as the fundamental algorithmic schemes of Binary Search, computation of the median, and B-trees (Cormen et al., 1991).

Element Decomposition

The range-partitioning solution involves a significant number of counters. In addition, it gathers a lot of information that may not be necessary for determining majority. It counts the number of elements in each subrange as well as the number of times that each of the majority subrange elements appears in the input. We may try to develop a more concise solution, which gathers less counting information and yields more efficient memory utilization.

So far, the input elements were viewed as atomic elements. However, an integer can be viewed as a sequence of bits. It might be useful to decompose each integer into its composing bits, and devise a solution that accumulates relevant bit information rather than element information.

We shall view an integer as a sequence of 32 bits, and name them [b.sub.31], ... [b.sub.1],[b.sub.0], where [b.sub.31] is the most significant bit and [b.sub.0] is the least significant. We notice the following mathematical pattern with respect to majority:

   If there is a majority element, and its binary value is [v.sub.31]
   ... [v.sub.1][v.sub.0] ([v.sub.0] is the value of [b.sub.0],
   [v.sub.1] is the value of [b.sub.1], etc), then each [v.sub.i], for
   i[member of] 0..31, will appear a majority number of times in the
   [b.sub.i]-th bit of the input elements.

We call zer[o.sub.i] the number of times that the value 0 appears in bit [b.sub.i] of the input elements. Since each bit is either 0 or 1, the number of times that the value 1 appears in [b.sub.i] across the input is obtained from the expression: N-zer[o.sub.i]. We call majority value for [b.sub.i] the value (0 or 1) that appears in bit [b.sub.i] of the input elements more than N/2 times. Every bit [b.sub.i] has a majority value, unless its zer[o.sub.i] is exactly N/2. If there is a bit with no majority value then surely there is no majority element. If each of the bits has a majority value, then there may be a majority, and the majority element must have the majority values of the bits.

We illustrate the latter insight with a short example. Given the input sequence 3 5 6 5 5, its binary representation will be: 011 101 110 101 101. The values of the zer[o.sub.i]'s are: zer[o.sub.0]=1, zer[o.sub.1]=3, and zer[o.sub.2]=1. Therefore, the majority values of the different bits are: 1 for [b.sub.0], 0 for [b.sub.1], and 1 for [b.sub.2]. Thus, 101 is the only possible value for the majority element. In this example, 5 is indeed a majority. Yet, it may happen that all the bits will have majority values, but there will be no majority element; for example, in the case that the 5th input element is 4 (instead of 5).

A two-scan solution can be devised, based on the zer[o.sub.i] values of the input-elements' bits.

    1st Scan: Calculate the zer[o.sub.i] values "across" the
    input; if all the zer[o.sub.i] values are different than N/2, then
    construct a majority candidate variable according to the
    zer[o.sub.i] values (if zer[o.sub.i]>N/2 then the candidate's bit
    i will be 0; otherwise it will be 1) and perform the 2nd
    scan, else output 0.

    2nd Scan: Count the number of appearances of the candidate
    in the input; if it exceeds N/2, then output its value, else
    output 0.

This two-stage scheme, which employs the construction of a majority candidate, yields a major improvement over the range-partitioning scheme. It requires only lo[g.sub.2](R) counters--one for each bit in the binary representation of the input integers. Its implementation involves the design patterns of "decomposition-into-bits," counting, and candidate utilization.

The previous solution encapsulates the element decomposition perspective, as it involves the decomposition of the input elements into their "atomic," binary components, and the processing of these components "across" the input. Examples of processing based on element decomposition were mentioned in "Diverse Decomposition Perspectives," including that of processing "across" the input by "atomic" subpieces. The latter embodies "orthogonal processing," which is very effective both here and in Radix/Bucket Sort.

Linear Decomposition

The previous two perspectives focused on decomposition properties related to element values--range and composing bits. Perhaps a different decomposition approach will yield a more effective result. We may try to decompose the sequence of elements. We have seen in the beginning of "Case Study: Majority in a Large Sequence," that sequence decomposition into subsequences in a divide-and-conquer manner is impractical. However, we may consider a linear decomposition, in which the sequence will be decomposed into a very short prefix and a remaining postfix. For this, it should be beneficial to identify properties related to majority and inductive sequence reduction.

We may ask: is there an inductive element elimination that preserves the majority property? Elimination of a single element may violate the majority property. So does elimination of two identical elements. However, elimination of two different elements keeps the majority property invariant:

     If two elements in an N-element sequence are different and one of
     them is a majority element, then this element is also a majority
     element in the (N-2)-element sequence that remains after removing
     these two elements. This derives from the following
     inequality: K/N < K-1/N-2 (for every K and N greater than 2).

This invariant pattern yields a very elegant and simple solution. Every two different input elements will be removed. Eventually, either the sequence will be empty or one or more instances of the same element will remain. In the former case there is no majority. In the latter case, the value of the remaining (identical) elements is the (sole) candidate for majority.

We illustrate the previous with three short examples.

1. For the sequence 3 5 6 5 5 4, no element will remain as a candidate (pairs may be removed during a left-to-right scan). Thus, there is no majority.

2. For the sequence 5 5 5 6 6 4 4, one element will remain as a candidate. A left-to-right scan will yield 4 as the candidate. An additional input scan will show that 4 is not a majority.

3. For the sequence 5 5 5 6 5 4 4, the value 5 will be the candidate regardless of the order of pair removals. An additional input scan will show that it indeed is a majority element.

The solution scheme for implementing the previous idea involves two scans over the input, using two variables: a "sliding counter" and a "temporary candidate."

     1st Scan: Initialize the variable counter to 0. Upon
     reading the next input element: if counter =0 then increment it
     (by 1) and set the variable candidate to that element, else: if
     element=candidate then increment counter, otherwise decrement it.

     If counter >0 at the end of the scan then perform the 2nd
     scan, else output 0.

     2nd Scan: Count the number of appearances of candidate in
     the input; if it exceeds N/2 then output its value, else output 0.

The previous solution reduces the required computer memory to two variables--the temporary candidate and the sliding counter! Its implementation will be based on a "sliding-candidate counting" design pattern. Due to its pair-elimination method, this solution is independent of element representation. Elements can be integers, real numbers, or any symbols. Thus, this solution is not only very efficient but also more general than the previous two solutions.

This last solution encapsulates the linear decomposition perspective. Its underlying principle is sequence decomposition into a short prefix and a remaining postfix. The key point is the majority invariance under inductive, disjoint-pair elimination. The notion of inductive elimination is a relevant tool in a variety of algorithms. One example of its application is the elegant solution of the Celebrity Problem (Manber, 1989). Another example is that of Finding One-to-One Mapping (Manber, 1989). As in the element-decomposition solution, the notion of "candidate" was used. Here, the candidate was dynamically updated along the inductive computation.

Patterns and Efficiency

The presented case study illustrated several solution-process considerations in addition to that of perspective diversity. The various perspectives yielded different mathematical patterns, which were the core of each derived solution. This emphasized the essential role of mathematical patterns as seeds of algorithmic solutions. The mathematical pattern underlying the third solution was stated in an invariance manner. Invariant assertions are regarded by computer scientists as essential means for the design and analysis of algorithms (Dijkstra, 1976; Gries, 1981). The translation of the mathematical patterns into concrete algorithmic schemes involved instructive two-stage-counting solutions.

The three different solutions in the case study varied in their efficiency properties. They all required linear computation time with respect to the input length (two scans over the input), but considerably varied space-wise. The range decomposition required sqrt(R) space (recall that R is the range size of the input elements), the element decomposition required lo[g.sub.2](R) space, and the linear sequence decomposition required only two variables. It is interesting to note that the more concise the underlying mathematical pattern, the less information gathered in the computation and the more efficient the solution. This observation introduces an interesting angle of solution diversity with respect to pattern conciseness and efficiency.

CONCLUSION

This article elaborated the idea of decomposition diversity in algorithmic problem-solving. The article illuminated decomposition perspectives beyond top-down and divide-and-conquer, and named them: range decomposition, element decomposition, and linear decomposition. These perspectives were described, motivated, and tied to a variety of algorithmic solution schemes. Their effectiveness and relevance was demonstrated in a short illustrating example and a case study with three alternative solutions to a challenging algorithmic task.

Diverse views and alternative solutions are highly advocated by problem solving educators (Soloway et al., 1988; Linn & Clancy, 1992; Schoenfeld, 1992). These educators also advocate the incorporation of general problem solving heuristics within a specific domain (Linn, 1985; Gelman & Greeno, 1989; Schoenfeld, 1992). The displayed decomposition perspectives yield multiple views and thoroughly incorporate the general problem solving heuristic of decomposition (Polya, 1957) in the domain of algorithmic problem solving.

The various decomposition perspectives presented in this article are relevant for CS1, CS2, "Introduction to Algorithms," and other CS courses that involve algorithmic problem- solving. The Triples example and similar examples, can be displayed in a rather early stage of CS1 as initial illustrations of decompositions beyond top-down. The Majority case study can be combined in "Introduction to Algorithms" for elaborating perspective diversity and alternative solutions. The challenges in both the example and the case study are attractive, and their solutions are stimulating. The essential asset of both is in the links between their decomposition-based solutions and a broad variety of algorithmic schemes.

Diverse perspectives enrich problem solvers' repertoires of solution approaches, broaden the view of studied material in a domain, link between various solution schemes, and offer an appealing synthesis of general problem solving heuristics with particular domain resources and literals. This article illuminated and illustrated the perspective diversity of decomposition. It should be beneficial to illuminate perspective diversity of additional problem solving methods, as such an illumination is a pedagogical means for elaborating students' mathematical and scientific values.

References

Aho, A. V., Hopcroft, J. E., & Ullam, J. D. (1983). Data structures and algorithms. Boston: Addison-Wesley.

Astrachan, O., Berry, G., Cox, L., & Mitchener, G. (1998). Design paterns: An essential component of CS curricula. Proceedings of the 29th SIGCSE Technical Symposium on CS Education, (pp. 153-160).

Boyer, R. S., & Moore, J. S. (1991). A fast majority vote algorithm. In R. S. Boyer (Ed.), Automated reasoning: Essays in honor of Woody Bledsoe, Automated reasoning series, (vol. 1), (pp. 105-117). Dordrecht, The Netherlands: Kluwer (the algorithm was invented in 1980).

Clancy, M. J., & Linn, M. C. (1999). Patterns and pedagogy. Proceedings of the 30th SIGCSE Technical Symposium on CS Education, (pp. 37-42).

Cormen, H. T., Leiserson, C. E., & Rivest, R. L. (1991). Introduction to algorithms. Cambridge, MA: MIT Press.

Dijkstra, E. W. (1976). A discipline of programming. Englewood Cliffs, NJ: Prentice-Hall.

Even, S. (1979). Graph algorithms. New York: W.H. Freeman.

Gelman, R., & Greeno, J. G. (1989). On the nature of competence: Principles for understanding in a domain. In L.B. Resnick (Ed.), Knowing, learning, and instruction--Essays in honor of Robert Glazer (pp. 125-186). Mahwah, NJ: Lawrence Erlbaum.

Glaser, R. (1984). Education and thinking--the role of knowledge. American Psychologist, 39, 93-104.

Gries, D. (1981). The science of programming. New York: Springer-Verlag.

Linn, M. C. (1985). The cognitive consequences of programming instruction in classrooms. Educational Researcher, 14, 29.

Linn, M. C., & Clancy, M. J. (1992). The case for case studies of programming problems. Communications of the ACM, 35, 121-132.

Maekawa, M. (1985). A sqrt(N) algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems, 3, 145-159.

Manber, U. (1989). Introduction to algorithms--a creative approach. Boston: Addison-Wesley.

Polya, G. (1957). How to solve it. Princeton, NJ: Princeton University Press.

Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33, 668-676.

Rist, S. R. (1989). Schema creation in programming. Cognitive Science, 13, 389-414.

Schoenfeld, A. H. (1992). Learning to think mathematically: Problem-solving, metacognition, and sense making in mathematics. In D.A. Grouws (Ed.), Handbook of research on mathematics teaching and learning, (pp. 334-370). New York: Macmillan.

Sloane, K. D., & Linn, M. C. (1988). Instructional conditions in Pascal programming classes. In R.E. Mayer (Ed.), Teaching and learning computer programming--multiple research perspectives, (pp. 207-235). Mahwah, NJ: Lawrence Erlbaum.

Soloway, E. (1986). Learning to program = learning to construct mechanisms and explanations. Communications of the ACM, 29, 850-858.

Soloway, E., Sphorer J., & Littman, D. (1988). E unum pluribus: Generating alternative designs. In R.E. Mayer (Ed.), Teaching and learning computer programming--multiple research perspectives, (pp. 137-152). Mahwah, NJ: Lawrence Erlbaum.

DAVID GINAT

Tel-Aviv University

Israel

[e-mail]