Home MembershipSpecial Interest GroupsSIGCT (Computing Teachers)JCSE Online - Journal of Computer Science EducationPast Issues2001-2002 April 2002

Gaining Algorithmic Insight through Simplifying Constraints

David Ginat
Tel-Aviv University

Abstract
Algorithmic insight is a key element in the preliminary analysis stage of algorithmic problem solving. Insight is often gained through heuristic search aimed at unfolding patterns and characteristics. One effective heuristic for preliminary problem analysis is simplifying constraints. This article focuses on explicit demonstration of the relevance and effectiveness of simplifying constraints. The article introduces three colorful illustrations that display the important role of this heuristic in algorithmic problem solving.

The heart of computer science lies in algorithmic problem solving. Design, analysis, and modeling of algorithms appear in various perspectives throughout the computer science syllabus. Some of the core courses—including CS1, Data Structures, and Introduction to Algorithms—focus on algorithm design at different levels of abstraction and complexity. The design involves a variety of design tools and techniques.

A primary group of design tools is the collection of design patterns (Astrachan, Berry, Cox, & Mitchener, 1998; Linn & Clancy, 1999). An additional group is the set of verification elements, in particular loop invariants, used for design that is done hand-in-hand with analysis (Dijkstra, 1976; Gries, 1981). The primary group of design techniques includes problem-solving methods such as decomposition, divide and conquer, backtracking, greedy computation, and dynamic programming (Aho, Hopcroft, & Ullman, 1983; Cormen, Leiserson, & Rivest, 1990).

Though algorithm design is presented with tools and techniques (sometimes only implicitly), the effort made by presenters to lead the student through the design process varies considerably. Some display a brief rationale and proceed to the end result, while others introduce a gradual development process with alternative considerations. Particularly enriching examples of incremental development are demonstrated in Gries (1981), Manber (1989), and Linn and Clancy (1992)—the first and second illustrating diversity of inductive designs, and the third a variety of problem decompositions.

Whether less or more gradual, many design illustrations start from a point where an initial level of insight is instantly displayed. However, the insight encapsulates characteristics that are not always straightforward. These characteristics are derived from a preliminary analysis of the algorithmic problem at hand. They often are the outcome of a heuristic search in which various exploration methods—such as analogy, generalization, and backward reasoning (Polya, 1957; Schoenfeld, 1985)—are employed to help one gain insight. This search is infrequently demonstrated.

Presentation of the search for problem characteristics demonstrates the process experts go through to gain insight into the problem. Such presentation enhances understanding and assimilation of studied material. Further enhancement can be obtained by pattern exploration practice (Schoenfeld, 1992). Both presentation and practice involve explicit indication of employed heuristics and elaborate the significant role of heuristics in reaching illuminating problem characteristics.

This article focuses on presenting the significant role of the heuristic simplifying constraints in algorithmic problem solving. Simplifying constraints involves simplification of a given problem to a problem in which constraints are imposed on the input data. The range of possible data is limited temporarily and yields a simpler problem with reduced complexity. The objective is to enable one to gain insight by initially exploring characteristics in a reduced domain. The identified characteristics of the simpler problem lay the foundation for the solution of the original problem. To achieve effective progress, one should carefully select the simplifying constraints. The constraints should considerably reduce complexity, but they should also maintain the core characteristics of the original problem.

Simplification can be performed in various ways, such as:

• Limiting the input of the original problem to a selected range of values with a particular characteristic, such as the even integers or the prime numbers.
• Setting one or more of the original problem parameters to a constant value.
• Starting from basic input values and gradually increasing them in a manner similar to induction.

In the next three sections, I illustrate the use of simplifying constraints in the three ways mentioned above. The illustrations display the process of gaining insight into different algorithmic problems. The first problem (the Josephus Problem) involves mathematical formulation of an algorithmic procedure, the second (Profiles) involves spatial calculations, and the third (Tensile Strength) involves optimization. None of the problems is straightforward. The role of the heuristic is evident during the process of gaining insight into the problems. In addition, the illustrations demonstrate the relevance of the heuristic used, not only for identifying characteristics but also for justifying the correctness of the algorithmic solutions.

The approach presented here was part of a Didactics of Algorithmic Problem Solving course given to high school and college teachers during the fall 1999 and 2000 semesters. The course was part of their graduate studies in science teaching at Tel-Aviv University. The teachers were enthusiastic about this approach. Many incorporated it into their classes and reported that their students showed enhanced awareness and confidence in the process of algorithmic problem solving.

Mathematical Formulation through Simplifying Constraints

The first illustration is rather concise. The simplifying constraints heuristic appears in the form of limiting the original problem input to a selected range of values with a particular characteristic. The illustration involves gaining insight into a given algorithmic procedure. The procedure is a variant of Josephus Flavius' survival myth in a lethal circle during the unsuccessful Jewish revolt in the first century against the Romans. Josephus and 39 comrades were trapped in a cave and decided to put an end to their lives rather than fall in captivity. They formed a circle and executed every seventh man clockwise. Josephus instantly calculated the circle location of the last to go and took his place. As the last, he chose not to commit suicide (Herstein & Kaplansky, 1974). The following problem is a simpler variant of that myth.

Josephus Problem, with skips of 2

N people, numbered from 1 to N, form a circle. Starting a removal procedure at person number 2, every 2nd person is removed from the circle until only one remains. An inefficient way for obtaining the location of the survivor is to simulate the removal procedure. Find an efficient way for calculating the survivor's location.

Example: For N = 9, the removal procedure in the circle in Figure 1 results in the following eight removals: 2, 4, 6, 8, 1, 5, 9, 7. The location of the survivor is 3.

Figure 1.

The problem is not trivial. The first "round" is clear, as all the even indices are removed, but the next rounds and the final outcome are not at all obvious. (Give the problem a try before reading further.) Two common solution approaches are induction and recursion. Although it is possible to solve the problem in these approaches, they are not straightforward. They yield a rather limited view of the problem characteristics. The approach of simplifying constraints elegantly leads to deep and effective illumination.

In executing the procedure for small values of N, such as 2, 3, 4, 5, … 10, one notices that for N = 2, 4,and 8,the survivor is the person in location 1. This observation may hint at the simplifying constraint N = 2^k.

Examination of the problem under the simplifying constraint of N = 2^k, for k é 1, reveals that the location of the survivor for N = 2^k is 1.

This is due to the following property for N = 2^k: the number of people removed in each round is exactly half the even number of people in the beginning of the round. Every round ends by removing the person "just before" the person in location 1, therefore the person in location 1is always "skipped over" and survives.

We can now try to capitalize on the initial insight gained for the constrained cases of N = 2^k, and advance to the general case, in several steps:

1. For the general case of N, we shall call ithe location of the person whose removal leaves 2^k people in the circle for the first time (the highest possible k).
2. Based on the constrained case, the location of the survivor is i + 1. Thus, if we are able to determine i, we will have an elegant solution for the general case.
3. The number of removals that will leave 2^k people in the circle for the first time is the difference between N and the largest power of 2 that is smaller or equal to N.
4. Because advancement along the circle is in skips of 2, the value of i will be twice this difference.

We conclude the following general formula from the above steps:

The uniqueness of the approach presented above is in gradually unfolding the problem characteristics through the constrained case. The primary insight gained through simplifying constraints paved the way for the general case. Moreover, the above solution process not only yields the general formula but also portrays the argumentation for proving the correctness of the formula. Thus, the heuristic led us both to the problem solution and the proof its correctness.

Spatial Calculations through Simplifying Constraints

The second illustration is more involved. It involves the extraction of a three-dimensional (3-D) formation from two-dimensional formation. The significant role of simplifying constraints is in considerably limiting one parameter of the original problem without diminishing the essential problem features. The reduction simplifies the problem significantly and enables students to focus on the core characteristics. Once identified, the core characteristics yield the general-case solution.

The illustration involves minimum and maximum calculations related to counting in a 3-D environment. Computer monitors are stored in cubic boxes on a large matrix platform, such that some are piled on one another with their sides parallel to the platform sides. To decide whether there is need for a new monitor delivery, the storage manager has requested Kylie to estimate the number of monitors (boxes) in the storage hall. Kylie hates the shadowy and dusty storage hall. Realizing that the task requires only an estimate of the number of boxes, she devised a wily plan—instead of "going through" the box structure, stepping on the dusty boxes, moving them, and counting them directly, she will just draw the profiles of the box structure as seen from two sides. She will walk along the south and the west sides of the platform and draw the 2-D south profile and the 2-D west profile of the box structure. Although the exact number of boxes cannot be extracted from these two profiles, she will be able to calculate the minimum and maximum number of boxes in the structure—sufficient information for an estimate. Her task will then be the following:

Figure 2.

Figure 3a. South profile.		Figure 3b. West profile.

The problem is intriguing. Each profile provides only 2-D data and no depth information on the box structure. How should we derive the properties of the 3-D formation from the two-angle (south, west) descriptions? Should we calculate the amount of boxes that may be hidden in the structure? Will division of the problem into subproblems help? Shall we look for a similar problem on which to capitalize? These are some of the questions that may be posed by a problem solver starting the solution process.

We can try simplifying constraints and reduce to a minimum one of the problem parameters. Relevant parameters to consider are: the total length of a profile, the number of intervals in a profile, or the height variability in a profile. Which one shall we select?

Restriction of the profile length implies limitation on the variability of the heights and the number of intervals. Restriction of the number of intervals implies limitation on the variability of the heights. Restriction of the heights does not limit the variability of the other two parameters. In addition, height restrictions may elegantly yield basic forms of minimal and maximal structures.

We can restrict the profile heights to a maximum of 1—that is, interval heights of either 0 or 1—and examine simple cases of gradually increasing complexity. The first case is that of one-interval profiles for both sides—(1,1) for the south view and (1,2) for the west view. This simple case exemplifies a situation in which the minimum and the maximum number of boxes are equal. Figure 4 displays the south and west profiles and the view from above of this simple case. In Figure 4c, the bottom line describes the south profile, the left column describes the west profile, and the bold numbers describe the box placement.

Figure 4a. South view.		Figure 4b. West view.		Figure 4c. View from above.

We next examine, in Figure 5, a simple case that exemplifies a difference between the forms of minimal and maximal structures. The south profile is (1,2), and the west profile is (1,2).

Figure 5a. South view.		Figure 5b. West view.		Figure 5c. Minimal structure.		Figure 5d. Maximal structure.

We may conjecture that an underlying characteristic of the minimal structure is a "diagonal" placement (and there may be more than one such placement) and an underlying characteristic of the maximal structure is maximal filling. To raise our confidence in this conjecture, we slightly extend, in Figure 6, the above case to longer and a bit more complex profiles: south profile (1,3) and west profile {(1,1),(0,1),(1,2)}.

Figure 6a. South view.		Figure 6b. West view.		Figure 6c. Minimal structure.		Figure 6d. Maximal structure.

In this example, the total length of height 1 is 3 units in each profile, and so is the minimal number of boxes. However, the total length of height 1 could be different in the two profiles. For example, the south profile could be (1,4), or {(1,2),(0,1),(1,2)}, with a total length of 4 units of height 1. In this case, the minimal number of boxes would have been 4, as it cannot be less than the larger total length of height 1among the profiles.

For the simplifying constraint of heights 0 and 1, we can conclude the following:

• The number of intervals is unimportant. The important parameter is the total length of height 1 intervals in the two profiles.
• The minimal structure derives from a diagonal characteristic: a diagonal box placement implies that the number of boxes is equal to the larger total length of height 1 between the two profiles. There may be several minimal structures.
• The maximal structure derives from a maximal filling characteristic: the maximal number of boxes is the value obtained by multiplying the total lengths of height 1 of the two profiles. There is exactly one maximal structure.

The analysis of the simplified cases, of maximal height 1, led us to significant insight. We recognized underlying characteristics for both the minimal and the maximal structures. At this point we may return to the original problem. We advance to the general case in two steps:

1. Examination of cases in which the structure height is bounded by 2 (rather than 1).
2. Generalization of the accumulated observations, and formulation for the general case.

We examine, in Figure 7, the case of: south profile {(2,1),(1,2),(2,1)} and west profile {(1,1),(2,2),(1,2)}.

Figure 7a. South view.		Figure 7b. West view.		Figure 7c. Minimal structure.		Figure 7d. Maximal structure.

For this case, of height bounded by 2, we notice the following:

• The minimal structure maintains a decomposition property: the height 1 box formation is independent of the height 2 box formation.
• The maximal structure maintains an intersection-per-square property: the height value of each matrix square is the minimum of the heights of the square's corresponding locations (coordinates) in the south and west profiles.

The decomposition property implies that capitalization on the diagonal characteristic, which was revealed in the initial simplification, can be separately applied for each height value. The intersection-per-square property extends the maximal filling characteristic of the initial simplification—in each square, we should fill as many boxes as possible without violating the heights of that square in both profiles.

Before summarizing our findings, we should examine whether a certain height value that appears in one profile must also appear in the other. In examining variations of the above example, we can clearly notice the following properties with respect to the structure heights:

• Height property 1: the highest structure height must appear in both profile.
• Height property 2: any height below the highest may only appear in one of the profiles.

The following is an example of the latter property. The description—south profile {(2,1),(0,2),(2,1)} and west profile {(1,1),(2,2),(1,2)}—is a description of a legal structure even though intervals of height 1 appear only in the West profile. In such a case, the minimal structure will include boxes that will be viewed only from one profile, as can be seen in Figure 8.

Figure 8a. South view.		Figure 8b. West view.		Figure 8c. Minimal structure.		Figure 8d. Maximal structure.

We can summarize our accumulated observations and formulate the underlying characteristics for the general case, in which the structure height is not restricted. We define for each height value h (appearing in one or both profiles) the following sums: SL_h, the total sum of the lengths of height h intervals in the South profile, and WL_h, the total sum of the lengths of height h intervals in the West profile.

Minimal Structure Characteristics

1. The box formation of each height value h is independent of the box formation of the other heights.
2. For each height value h, the minimal number of boxes satisfying the height h intervals of both profiles is: h_(max(SL_h,WL_h)).
3. For each height value h, the box formation will be: min(SL_h,WL_h) 'pillars' of boxes of height h that are spread diagonally and cover a length of min(SL_h,WL_h) of height h in each profile, and max(SL_h,WL_h) – min(SL_h,WL_h) pillars that cover the remaining (height h) length in the profile in which the sum of lengths of height h is larger.

Maximal Structure Characteristic

1. The pillar (box) height in every square of the matrix platform is the minimum of the heights of the square's corresponding locations in the south and west profiles.

The above characteristics imply that the ordering of the intervals in each profile is irrelevant. This allows us to group together for each profile all the intervals of the same height. The grouping can be done in the beginning of the computation by sorting the intervals according to their heights. Then, for the minimal structure, the number of boxes can be calculated separately for each height group following the diagonal characteristic. For the maximal structure, the number of boxes can be calculated by filling each rectangular area created by the intersection of every height group in one profile with every height group in the other profile. The remaining challenge is to implement this computation scheme by properly utilizing relevant design patterns.

As in the solution of the previous problem, we gradually unfolded the problem characteristics by capitalizing on insight gained by simplifying constraints. The heuristic appeared in the form of limiting the structure height to minimum and almost-minimum values (1 and 2). The insight accumulated through these limitations paved the way to the formulation of the general characteristics. In addition, the process of gaining insight revealed the argumentation for proving the solution correctness.

Optimization through Simplifying Constraints

The last illustration involves an optimization task. In this illustration, the heuristic simplifying constraints is applied in a manner that reminds us of induction. Gaining insight into the problem involves a base case and an inductive step. Gradual progression along the solution path occurs through analyzing an inductive increase in the number of objects in the given problem. The base case is easy to handle. The challenge is in properly formulating the inductive step, possibly with recursion.

The following algorithmic problem involves selection of the best possible subset of a set of elements. In a construction site, two rows of steel pillars have to be connected with cables. The connecting cables should be chosen from a set of cables of various tensile strengths. The goal is to calculate the strength of the subset of cables that yields the strongest connection under the restricting condition of no crossing cables.

Figure 9.

The difficulty in this problem stems from the variety of subsets of cables. Enumeration of all the possible subsets requires exponential time. We should try to capitalize on the restricting condition of no crossing cables and examine as few connection combinations as possible.

We turn again to simplifying constraints. The underlying principle is to start from a very basic pillar formation (in rows A and B) and gradually expand this formation. The simplification is implemented in two stages. At first we examine a base case, where the number of pillars in row A is 1. Then, we advance to the inductive step, by setting the number of pillars in row A to 2 and gradually increasing the number of pillars in row B.

For the simplifying constraint of one pillar in row A, we notice the trivial observation:

• The output will include all the cables between the single pillar in row A and the pillars in row B, as there are no crossing cables.

For the simplifying constraint of two pillars in row A, we gradually examine connections to pillars in B. We first notice the following:

• The case of one pillar in B is trivial. The case of two pillars in B involves crossing and non-crossing cables. The cables connecting the lower ends (A₁ – B₁) and upper ends (A₂ – B₂) do not cross any other cables, and therefore can surely be included (if they exist) in the solution. The other cables (A₁ – B₂ and A₂ – B₁) may cross one another. The better (stronger) alternative should be chosen.

In examining the latter case, we notice that the two cables A₁ – B₁, A₁ – B₂ are actually the solution for the case of the first pillar in A with the two pillars in B. Similarly, the two cables A₁ – B₁, A₂ – B₁ are the solution for the case of the two pillars in A with the first pillar in B. Thus, the solution for the case of the two pillars in A with the two pillars in B can be viewed as a selection between two reduced cases, plus the upper ends cable A₂ – B₂. We can advance to the next case by combining this observation with a recursive perspective.

• The case of two pillars in A and three pillars in B, can be as follows. The upper end's cable (A₂ – B₃) should be included and added to the better alternative among the solution that excludes the upper-end pillar in A (A₂) and the solution that excludes the upper-end pillar in B (B₃).

This recursive perspective reduces the current problem instance into a selection between two alternatives that encapsulate resolution of all the possible crossing conflicts of smaller problem instances. This yields avoidance of direct enumeration and examination of all the crossing conflicts of the current instance.

The recursive perspective can be elegantly formulated. We call Solution[i,j] the maximal tensile strength for the case of the first i pillars in A and the first j pillars in B, and Cable[i,j] the tensile strength of the cable A_i – B_j (the strength is 0 if no cable A_i – B_j).

Thus, Solution[2,3], the maximal strength for the first two pillars in A and the first three pillars in B will be: Cable[2,3] + max(Solution[1,3],Solution[2,2]). Notice that any legal combination of cables from the two pillars in A to the three pillars in B, excluding the cable A₂ – B₃, is included in Solution[1,3] or Solution[2,2].

We can summarize the insight accumulated so far in the following general formula:

Solution[1,1] = Cable[1,1] /* base case */

Solution[1,j] = Cable[1,j]+Solution[1,j-1] /* for j > 1 */

Solution[i,1] = Cable[i,1]+Solution[i-1,1] /* for i > 1 */

Solution[i,j] = Cable[i,j] /* for i,j > 1 */

+ max(Solution[i,j-1],Solution[i-1,j])

The above formula represents inductive accumulation of subproblem solutions. The simple implementation of this formula is with recursion. However, the recursive execution will invoke repeated computations and require exponential time (in the size of the input). The repeated computations can be avoided by replacing the Top-down recursion by the Bottom-up scheme of dynamic programming (e.g., Cormen et al., 1990). This will only require quadratic computation time.

The dynamic programming implementation requires a table for keeping intermediate solutions on the way to the final solution. We illustrate it on the example in the problem definition (and Figure 9). For brevity, we use S[i,j] rather than Solution[i,j]:

S[1,1]=0, S[1,2]=4, S[1,3]=9, S[1,4]=0 (no cable)

S[2,1]=4, S[2,2]=7, S[2,3]=10, S[2,4]=10

S[3,1]=0, S[3,2]=14, S[3,3]=14, S[3,4]=15

Notice, for example, that S[2,2] = Cable[2,2] + max(s[1,2],s[2,1]) and

S[3,3] = Cable[3,3] + max(s[2,3],s[3,2]) (the value of Cable[3,3] is 0 because it does not exist).

Although we unfolded the whole table, a two-line array will suffice for the computation, as each table value is derived from a value in the previous table line and a value in the previous table column. Initially the first table line—the values of Solution[1,j] for all j—will be calculated, and then the array will repeatedly hold the values of the last-calculated line and the currently calculated line.

In reflection on the solution process, we can see that here, again, the problem characteristics were gradually unfolded. The insight gained into the problem was developed through an inductive formulation that was reached by turning to simplifying constraints. Incremental progress was led by gradually increasing the number of elements in row A and row B.

Conclusion

This article described and illustrated the effectiveness of the heuristic simplifying constraints in the primary analysis of algorithmic problem solving. The illustrations included three very different algorithmic problems. In the first illustration, the heuristic led to gaining insight through limiting the input of the original problem to a selected range of values. In the second, insight was gained by setting one problem parameter to a minimum value, and in the third, through an inductive progress. The insight gained in all the illustrations not only led to the underlying solution characteristics but also revealed the argumentation for proving the solution correctness.

The use of heuristics in the early stage of problem analysis is a key element for illuminating problem characteristics. The simplifying constraints heuristic expands the repertoire of algorithmic problem solvers. In addition, the explicit indication and demonstration of the heuristic, as illustrated here, elaborates the awareness of the solution process rather than the end result. Such elaboration is a constructive tool for developing problem solvers' competence.

References

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

Astrachan, O. L., Berry, G. C., Cox, L. P., & Mitchener, G. (1998). Design patterns: An essential component of CS curricula. In J. Lewis, J. Prey, & D. Joyce (Eds.), SIGCSE '98: The proceedings of the Twenty-ninth SIGCSE Technical Symposium on Computer Science Education (pp. 153–160). New York: Association for Computing Machinery.

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

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

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

Herstein I. N., & Kaplansky I. (1974). Matters mathematical. New York: Harper & Row.

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

Linn, M. C., & Clancy, M. J. (1999). Patterns and pedagogy. In R. E. Noonan, J. Prey, & D. Joyce (Eds.), SIGCSE '99: The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education (pp. 37–42). New York: Association for Computing Machinery.

Manber, U. (1989). Introduction to algorithms—A creative approach. Reading, MA: Addison-Wesley.

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

Schoenfeld, A. H. (1985). Mathematical problem solving. Orlando, FL: Academic Press.

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.

Contributor

David Ginat is a faculty member in the Science Education Department at Tel-Aviv University. His PhD is in the area of distributed algorithms. His research and teaching during the last 10 years focus on the development of algorithmic problem-solving skills, at all levels, including that of Olympiad students.

Contact

David Ginat
Computer Science Group
Science Education Department
Tel-Aviv University
Tel-Aviv 69978 Israel
ginat@post.tau.ac.il
www.tau.ac.il/education/homepg/ginat.html

Copyright © 2002, ISTE (International Society for Technology in Education). All rights reserved.