Preface

My introductory programming courses always start with some loose definitions. I define an algorithm as an unambiguous process for solving a problem using a finite amount of resources, and a heuristic as a problem solving process that is not guaranteed to be perfect/exact or finite. I then explain that algorithms/heuristics written for a computer are commonly written in languages, called (high-level) programming languages, that are easily understood by humans, unambiguous, and easily converted into machine-readable form. I then point out that an algorithm/heuristic written in a programming language is a program (or code), and the process of doing so is called programming (or coding), which is what they will be studying for the remainder of the term.

As a practical matter, most introductory programming courses, mine included, use a single, specific programming language and, not surprisingly, there is considerable debate about which language is best for teaching beginning programmers (or whether it matters). However, there is, generally, consensus about the role that the programming language plays and the goals of such courses. Indeed, most introductory programming courses make claims like the following:

1. The concepts covered using the particular programming language selected for the course are applicable across a wide variety of other programming languages.
2. The course teaches algorithmic thinking more than the syntax of the language(s) being used.

In my experience, these claims are not completely justified. While the first is often true from a teaching perspective, it is not true from a learning perspective. In other words, students have enormous trouble taking what they have learned in one language and applying it in another. The second is an honest description of what the instructor wants to cover, but is a goal that is rarely achieved.

In the worst cases, instructors in introductory programming courses spend all of their time teaching students syntax and tools, and leave it to the students to figure out how to solve problems. Using concepts from Bloom’s taxonomy of the cognitive domain, such courses only teach “remembering” and “understanding”, and expect students to “analyze”, “evaluate”, “apply” and “create” on their own.

In the better cases, instructors in introductory programming courses expose students to well-written code containing good solutions to problems and explain why the code is good. However, they only hope that the students will internalize these solutions and be able to apply them in other contexts; they do not explicitly teach them to do so. In other words, these courses only teach “remembering”, “understanding”, “analyzing” and “evaluating”, but not “applying” and “creating”.

In the best cases, instructors in introductory programming courses teach “applying” and “creating” as well. That is, they teach problem solving as well as programming. This book is designed to make it easier to do so.

Teaching Problem Solving with Patterns

I have had colleagues over the years who have argued that problem solving can’t be taught, that students either have the ability or they do not. I (and others) disagree; I believe students can be taught problem solving in the following way:

1. Demonstrate that it is possible to classify problems;
2. Help them learn how to evaluate the quality of different solutions;
3. Provide good general solutions for many classes of problems;
4. Help them learn how to classify new problems; and
5. Help them learn how to adapt an existing general solution to a new specific problem.

This is the essence of teaching problem solving using patterns, an approach based on the work of Christopher Alexander (i.e., the so-called pattern language movement in architecture).

The teaching of design and problem solving using patterns involves the presentation of:

1. An archetypal/canonical problem;
2. One or more inferior solutions to the problem;
3. A superior solution to the problem (i.e., a solution that uses the pattern);
4. Other problems to which the superior solution can be applied (with minor modification); and
5. Ways to determine that a particular pattern is an appropriate solution to a particular problem (i.e., identifying the class a problem belongs to).

In the end, this approach provides students with two things: a library of solutions that they can use and an understanding of how to add to that library themselves. When faced with a new problem, their job is most frequently to recognize that they already have a solution. Less frequently, their job is to recognize that they don’t have a solution readily available and understand that they must develop alternative solutions, evaluate those solutions, and select the best alternative.

Patterns for Beginning Programmers

This approach has been used successfully (under various names) in upper-level courses in software engineering and other engineering disciplines for many years. Unfortunately, it has not yet found its way into introductory programming courses. This book is an attempt to remedy that shortcoming.

Two things distinguish programming patterns from other kinds of patterns: the problem domain (i.e., programming) and the level of abstraction. Programming patterns are at a higher level of abstraction than idioms because the concepts are not specific to a language (or language family). In other words, a programming pattern is not a “turn of phrase” (i.e., idiom) in a particular programming language. Instead, it is a generic solution to a problem that might arise in many languages; it is a way of thinking programmatically. Programming patterns are at a lower level of abstraction than design patterns and architectural styles. In other words, the use of a programming pattern leads to the creation of a small fragment of code that will be a part of a larger system, whereas the use of a design pattern or architectural style leads to the creation of a description of the interactions between the entities in a large system.

Unlike books on design patterns and architectural styles used in upper-level courses, this book does not stand alone. Instead, it is a supplement to the traditional textbooks used in introductory programming courses. A traditional textbook helps in the teaching of “remembering”, “understanding”, “analyzing” and “evaluating”. This book helps in the teaching of “applying” and “creating”. It assumes that the reader already knows the syntax of the statements in the fragments (which can be learned using a standard textbook) and focuses instead on the reasoning process that leads to the fragments.

Questions of Style

Teaching with patterns necessarily involves evaluating different solutions to the same problem, and these solutions can be evaluated using a variety of different criteria. This book attempts to focus on the criteria that are related to the solution without regard to issues of style. For example, a method to identify the maximum of two numbers could be implemented in three different ways. In the first, an intermediate variable and default initialization is used.

public static int  max(int  a, int  b) {
    int  result;
    result = b;
    if (a > b) result = a;
    return result;
}

In the second, an intermediate variable is used, but the two cases are handled explicitly (i.e., there is an else block as well as an if block).

public static int max(int a, int b) {
    int result;
    if (a > b) result = a;
    else result = b;
    return result;
}

In the third, there are multiple return statements and no need for an intermediate variable.

public static int max(int a, int b) {
    if (a > b) return a;
    else       return b;
}

Good arguments can be made for all three of these solutions, and the relative merits may vary with the experience of the programmer. However, the differences are more about the programming of the solution than they are about the solution itself. That is, they are stylistic differences.

Similarly, given a max() method, one might implement a min() method a number of different ways. One might, for example, argue that the following implementation is preferred because it is consistent with the implementation of the max() (assuming the third implementation was chosen).

public static int min(int a, int b) {
    if (a < b) return a;
    else       return b;
}

Alternatively, one might argue that the following implementation is preferred because it involves less code duplication.

public static int  min(int  a, int  b) {
    return -max(-a, -b);
}

Again, these arguments are more about the programming of the solution (i.e., the style) than they are about the solution itself.

As a final example, given max() and min() methods, one might implement a clamp() method in different ways. One might argue that consistency dictates the following implementation:

public static int clamp(int x, int lower, int upper) {
    if (x < lower) return lower;
    if (x > upper) return upper;
    return x;
}

or one might argue that re-use dictates the following implementation:

public static int  clamp(int  x, int  lower, int  upper) {
    return max(lower, min(upper, x));
}

To reiterate, this book attempts to avoid the use of stylistic criteria when evaluating different solutions. In other words, it attempts to compare solutions that differ in more than just their style.

The Organization of this Book

The patterns in this book are organized according to the topics that are covered in traditional introductory programming textbooks.

• Part I considers solutions to problems that only involve arithmetic operators (and related topics). So, an understanding of the declaration of variables, assignment statements, and arithmetic operators is all that is needed to consider the problems in Part I.
• Part II considers solutions to problems that require the use of logical operators, relational operators, conditions, and methods. After that,
• Part III considers patterns that require the use of loops, arrays, and (rudimentary) input/output. Next,
• Part IV covers problems and solutions that require the use of array members (especially the length attribute) and arrays of arrays (sometimes called multi-dimensional arrays) and
• Part V covers problems and solutions involving String objects. Finally,
• Part VI considers patterns involving the use of references.

In many cases, the patterns build on each other. So, with a few exceptions, the parts of the book need to be considered in order. Unfortunately, since different introductory programming courses/textbooks cover these topics in different orders, it may be necessary to gain a cursory understanding of some chapters, and then come back to them again later. For example, some courses/textbooks cover methods before arrays (as in this book) while others cover them in the opposite order. Hence, it may be necessary to gloss over some of the patterns in Part III until after methods have been covered.

Every chapter includes a motivation (i.e., a situation in which the problem being considered arises), the pattern (i.e., the solution to the problem), and examples. Many chapters also include one or more warnings, usually about not over-generalizing. Some chapters also include a “look ahead” at where the pattern might appear in later courses. The material in those sections is often more advanced and can be omitted (i.e., it is not required for subsequent chapters).

Acknowledgments

My wife writes well. I do not. Despite her best efforts to make this book readable, which I gratefully acknowledge, she has failed miserably. The fault lies with me, however, so please don’t blame her. (I can’t mention her by name because we are both on the faculty at JMU and I don’t tell my students her name so that they don’t send her pitying notes.)

I would also like to acknowledge the contribution of two of my colleagues at JMU, Chris Mayfield and Chris Fox. They both read an early draft very carefully, and suggested an enormous number of changes that have improved the current version tremendously. I can’t thank them enough.