See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/221537512

Programming patterns and design patterns in the introductory computer

science course

Conference Paper in ACM SIGCSE Bulletin · March 2000

DOI: 10.1145/330908.331819 · Source: DBLP

CITATIONS READS
85 2,604

1 author:

Viera K. Proulx
Northeastern University
91 PUBLICATIONS 928 CITATIONS

SEE PROFILE

All content following this page was uploaded by Viera K. Proulx on 21 May 2014.

The user has requested enhancement of the downloaded file.

 Programming Patterns and Design Patterns
in the Introductory Computer Science Course

Viera K. Proulx
College of Computer Science
Northeastern University
Boston, MA 02115
vkp@ccs.neu.edu

In order to use pattern based problem solving in our

Abstract introductory computer science courses, we looked at all
decisions students must make when designing programs.
We look at the essential thinking skills students need to This inspired us to build a collection of programming and
learn in the introductory computer science course based on design patterns that lead students through all topics
object-oriented programming. We create a framework for typically covered in an introductory CS course. We decided
such a course based on the elementary programming and to present the patterns as tutorials that guide students from
design patterns. Some of these patterns are known in the the general considerations to the actual implementation in
pattern community, others enrich the collection. Our goal is the programming language (C++ or Java). In addition, we
to help students focus on mastering reasoning and design built a collection of practice problems that can be used to
skills before the language idiosynchracies muddy the water. master each of the patterns.
In the first section of this paper we discuss the problems
1 Introduction many of our students encounter when trying to write even
The first programming course is a major stumbling block simplest programs. We show how this experience helped us
for many students interested in computer science. As the to notice some of the patterns of thinking and reasoning we
languages get more complex, students spend inordinate as faculty take for granted. We follow by listing the types
amount of time learning minutia of language syntax and of patterns we identified and their role in learning
some semantics. Meanwhile the overall picture of what is programming and design. To illustrate our approach to
essential and how the pieces fit together is lost in a sea of presenting patterns we describe the pedagogy used in our
'stuff'. Seasoned programmers quickly recognize the key courses. This includes both the written materials for
elements needed to write parts of the program and are students and the actual organization of learning time. We
fluent in creating a complex program from small conclude with a brief description of our students'
interacting components. Some of these patterns have been experience in a pattern-centric course.
identified by the pattern community and are making their
way into the introductory curriculum. However, the
2 Learning To Program: Why Is It So Hard?
methods for presenting patterns to the pattern community
are not written as tutorials for novices. An instructor One of the most frustrating experiences when teaching
interested in using problem solving in the context of introductory course is meeting a bright student who
patterns often needs to rewrite these patterns. becomes lost when asked to write even the simplest
program. The fact that many students can hand-simulate an
______________________________________________
Partial support for this work has been provided by the National
algorithm and know exactly what needs to happen at each
Science Foundation Leadership in Laboratory Development, step - yet cannot program this algorithm has been noticed
award #DUE- 9650552 and by the Microsoft Corporation. before. But some of the otherwise competent students
Permission to make digital or hard copies of all or part of this work cannot program independently even the simplest loop. It
for personal or classroom use is granted without fee provided that seems like we see more of these students as the complexity
copies are not made or distributed for profit or commercial
of the programming languages grows and the core
advantage and that copies bear this notice and the full citation on the
programming and design ideas get lost in the mass of
supporting code (the downside of object-oriented
first page. To copy otherwise, or republish, to post on servers or to
languages).
redistribute to lists, requires prior specific permission and/or a fee.
SIGCSE 2000. Of course, the key ideas of how to write a loop appear in
Copyright 2000 ACM 1-58113-499-1/00/0006…$5.00. every textbook. So, the problem lies deeper. The program
infrastructure is much more complex than it used to be.
Students get lost in the mire and often just exclaim "I do • arrays
not even know where to start." One of our students • pointer variables
commented on the problem of understanding lectures but
not being able to solve lab problems as follows: "Concepts • templates
taught in the classroom tend to be an introduction. ... Three • user defined types
lines of code on the blackboard merely show the tool to me The declare step binds the identifier to a certain kind of
but that's about all I saw in the overall view." and later entity (data type, function with a given signature, object in
commented "It was like saying, here is...hm...some food, a given class). In many cases this step completely
this is the food...now make a meal out of it. Maybe to a determines what kind of operations are allowed for this
person learning to cook for a first time, all this may not identifier.
make all that much sense."
The second step (define, build, initialize) makes the
Looking at what we typically do when writing programs, identifier ready to be used with its full set of behaviors. For
we realize that we have 'canned methods' for deciding what variables, this is the initialization step. For a function, this
names to use when - and how to use them, we have a is where the implementation is specified. For a class, the
standard way of reading the input, of writing conversions two steps often overlap. Some of the member functions are
between different data representations, to name just a few defined inside the class declarations, others can be defined
'tricks of the trade'. We address all these problems first at later. Object instance creation immediately invokes a
the conceptual level. The programming language constructor and so the two steps are (almost) inseparable.
considerations come into play only once we know what we
want to do. By presenting these patterns of thinking and In each case, once the define/build step has been
reasoning we hope that students will be able to apply these completed, the user interface is specified and the identifier
methods to their own programs. is bound to a specific behavior. The use of an identifier
then follows this interface.
In the following section we will identify these basic
patterns and organize them into several categories and By introducing the destroy step early, we set the stage for
show how they cover the typical CS1 curriculum. discussing the memory allocation issues, and the scope and
lifetime of an object or variable. Of course, often this step
is implicit. However, by including it as a part of the naming
3 Programming Patterns and Design Patterns pattern students become more aware of how the names are
for Novices managed by the compiler.
The patterns we present here play different roles in the Arrays and pointer variables cover a broader pattern: This
design and implementation of a program. The categories pattern of indirect naming will be presented later.
often represent an evolving thread that is revisited several
times during the first year.
3.2 Reading Data Pattern
Considering the amount of time students spend reading
3.1 Name Use Patterns data it is a shame that the whole process is not treated as a
Every programming language uses 'identifiers' to represent serious task. In a typical course functions are used to
different kinds of entities in a program. Yet the use of all encapsulate even the simplest computation, yet students
identifiers follows a set pattern: declare - define/build - use keep writing from scratch the typical sequence "user
- destroy. This pattern helps students realize that every prompt - read data - verify - repeat". We believe students
identifier will explicitly or implicitly follow this pattern. should understand three levels of user input and use them
When a new kind of entity is presented, students anticipate correctly in their programs. The three levels are:
learning about the declaration, definition or build, use, and • raw input, where we expect only perfect data and
destruction. perform no error checking (never used in a production
We first list the kind of entities for which identifiers are program)
needed: • verified input, where we verify that the input conforms
• variables of built-in types and string objects (used for to the expected behavior (e.g. is a number if assigned
echo printing only) to a numeric variable)
• constants defined by const or enum • filtered input, where we also check that internal
• functions constraints are satisfied (e.g. age is >0 and < 150)
• file names (even though they may look like strings) Our students use IOTools toolkit [8] to perform the verified
input. They then learn to write similar utility functions by
• streams (or file control variables in other languages) implementing filtered input. For example, in a program that
• classes and structs computes a grade point average (GPA), the course grade
• object instances must be a valid grade from a given list.
 This organization takes us away from focusing on which
3.3 Read - Process - Write Pattern loop control statement to use (for vs. while). The focus is
on the nature of the problem and the best solution for that
To consider this a pattern may seem trivial or restrictive, situation. It becomes clear that the different loop control
but our focus is on the general concept. We focus on the statements implement the same algorithm.
fact that any segment of a program may be specified by
describing the input that is needed, the process that will
transform this input, and the output or resulting data that 3.6 Selection Pattern
will be generated. The input here may come from a sensor, This is another well researched and presented pattern. We
file, or mouse manipulation; the output may be sound, include it for completeness. Methods for designing
graphics, control signal, as well as plain text. Additionally, conditionals are included in this pattern [2].
the input may not come from an input device - but be
contained in function arguments, stored as member data of
object invoking a method or take other forms. The output 3.7 Traversal Patterns
again just means the information generated during the Any time we work with a collection of data, we need to
process stage and made available to the user of this code design a process that will look at all the relevant data items
segment - be it a function, method, or an entire program. one at a time. The purpose of a traversal is to deliver one
data item from a specified collection each time the traversal
3.4 Encapsulation Pattern method is called. For example, the Read Data Pattern may
use traversal of input stream to deliver the next item. The
In these patterns we try to bring into focus the situations following four traversal patterns may be introduced in the
where it is helpful to write a utility function or build a first course:
toolkit class. The computational part of these patterns
usually falls within a different category. Here the focus is • simple linear traversal (vectors, arrays, strings, file
on the need to build a utility tool. We identified four input if using counters or indices)
instances where this pattern applies - new ones may emerge • streamed traversal - typically terminated by the 'end-
later: of-input' indicator
• unit conversions (meters to miles, etc.) • linked traversal - traversal of a linked structure
• geometric scaling • iterator based traversal [9]
• encapsulate inner loop (part of repetition pattern) The last three patterns are closely related. They differ in
• encapsulate complex condition (part of repetition and how they handle the responsibility for advancing to the
selection patterns) next item and recognizing the end of available data.

3.5 Repetition Patterns 3.8 Cumulative Result Patterns

This is of course well known topic - both as a formal These are composite patterns built out of several earlier
pattern and as concept covered in every CS class [1]. Our patterns. Some variations are known in the pattern world,
variation divides this pattern into four parts: but we believe that the programmer needs to make several
independent and interdependent decisions when designing
• counting - including increments other than one solutions to this type of problems. The goal is to traverse
• conditioned repetition (usually a while loop) some collection of data, collecting partial information into
• polled loop (busy wait for external event - e.g. mouse some accumulator entity and presenting the composite
click) result at the end. We identify the following four separate
components a programmer must consider:
• repetition with exits (usually via break or continue
statement) • design the accumulator (Name Use Pattern)
Our approach is to divide repetition into five stages: initial • design update operations (Reading Data Pattern,
setup, verifying loop condition, loop body, loop condition Selection, Conversion, Formatting Output and other
update, and post-mortem. patterns)
We also include here two loop design strategies: • select traversal (Traversal Pattern)

• design loop body first (to make loop understandable • design post-mortem (may use Formatting Output
and simple) Pattern)
• remove from loop repeated computations of the same This pattern has two variations. At the basic level only one
quantities accumulator is used. A multipurpose variation may include
several accumulators that perform different functions (e.g.
computing minimum and maximum in one pass) or even an
array of accumulators (for example when computing a In our curriculum, most of these will be introduced in the
histogram). second course. The patterns at this higher level are more
likely to be recognized and identified in the pattern
literature. Our goal was to create a framework for
3.9 Conversion Patterns designing simple programs that will help students
Multitudes of textbooks include the conversion of understand what are the key questions to ask and what
temperature data from Fahrenheit to Celsius and vice versa. considerations need to be made before the design is
However, this is just the tip of the iceberg. Conversion completed.
permeates all computing and should be identified as such
whenever students encounter it. We classify conversion
patterns as follows: 4 Pedagogical Considerations
• basic scaling (conversion between frames of reference:
minutes and seconds, feet and inches, miles and meters 4.1 Our Course Organization
as well as real vs. drawing coordinates) [5] To guide students through the sea of new ideas introduced
• casting (either automatic of forced; discusses loss of in the introductory programming based course, we organize
precision or accuracy, impossibility of some the course as follows. Three weekly lectures introduce the
conversions key concepts and outline the relevant patterns. Students
• formatting output (implicit conversion of integers into read the pattern tutorials together with a problem set
strings, etc.) document that contains several completely solved
problems, several unsolved problems, and a short
• table lookup based conversion (mapping is determined introduction that suggests a problem solving strategy that
by a table) student should use when trying to solve the problems and
• encapsulated scaling (constructing scaling class and highlights the relevant patterns. Problem sets are discussed
scaling function object[5]) during weekly recitation sessions conducted in small
groups of no more than 20 students. Students are then
required to program and run some of the unsolved
3.10 Indirect Reference Patterns problems. The other weekly class meeting of the small
Indirect naming comes in several forms. Reference group is a closed lab where students implement part of a
arguments in function calls and array references are the substantial project that illustrates the use of the new
first encounters. Later follows the use of explicit pointer concepts in the context of an interesting application of
variables and the introduction of iterators. However, they computer science.
key idea here is that there are several identifiers or
identifier-like entities that represent several different kinds
of data and each of them is bound to a different behavior. It 4.2 Pattern Tutorials
is best illustrated in the context of arrays. Array name Each pattern tutorial is presented in a separate document.
represents a location in memory where the array is stored. The format for pattern tutorials is a modified version of the
It is a pointer. Array index is an integer, with all integer standard used by the pattern community, to achieve our
arithmetic and relational operator at our disposal - and with pedagogical goals. In each pattern we use three levels of
no guarantees about the range. The index is a modifier that explanation: introduce a problem, explore the idea and the
may affect the actual location referenced by the pointer. related concerns, and finally present the solutions in the
Finally, the array item is identified by a composite name context of a particular programming language.
(e.g. a[i]) and its behavior is bound to the base array type. The patterns are written to guide a novice with little or no
Following N. Parlante, we refer to this entity as pointee. programming experience who needs a more structured
Understanding the Name Use Pattern helps us in explaining guidance in learning how to program. Better students will
the different behavior of the pointer, pointee, and the also benefit from reading the tutorials, just as it helps
modifier. experienced programmers to read about patterns. The
intuitive decisions become more focused, some of the
issues that may have been overlooked will come to the
3.11 Other Patterns forefront, and possible misconceptions will be corrected. In
This collection of patterns is not yet complete. We did not addition, naming the patterns helps in communicating
look at recursion, algorithmic problem solving patterns about the program design with other students and
(e.g. divide and conquer), or data organization patterns. instructors.
There is a 'class definition pattern' that includes 'constructor We describe briefly the Name Use Pattern tutorial to
building pattern'. There are also patterns for objects, for illustrate the three levels of explanations we use.
example function objects, state objects, data container
objects, and derived objects [7]. The first section is called Intent and Motivation. In the
Name Use Pattern we explain the need to name each
 entity that a program will use, the fact that the handout was set up, giving a definition of a term,
programming language has fixed rules how this can be explaining it, and then giving several examples on how it
done and that one needs to know what kind of entity a works and is used." Overall, we felt the course was a
particular identifier represents. success. Students performed better on the midterm exam
The next two sections discuss the problem at the conceptual and seemed more confident than in the past.
level, without using any actual program code. The pattern tutorials and the problem sets are available at
The Problem Examples section gives a few examples with our web site: http://www.ccs.neu.edu/teaching/EdGroup/
only a rudimentary reference to a programming language.
For example, we are printing a weather report, so we will 5 Acknowledgements
need to record name of each city (string object) and the
temperature (integer). I want to thank Joe Bergin for introducing me to the pattern
community and providing the inspiration for this work. I
The next section, Problem and Context, explains the four also want to thank Richard Rasala, for years of
steps: declare, define/build, use, destroy and what happens conversations and collaboration that helps in turning ideas
in each step as the program is compiled and executed (i.e. a into reality. I also acknowledge with gratitude the support
name is entered into a dictionary and space is allocated, of the NSF and the Microsoft Corporation.
space is filled with a value, value is accessed or modified,
space is released and the name is deleted from the
dictionary). References
The next two sections then focus on the implementation of [1] Astrachan, O. and Wallingford, E. (1998) Loop
the pattern in a programming language of choice. Patterns. Available:
The Required Elements and Structure section looks at the http://www.cs.duke.edu/~ola/patterns/plopd/loops.html
actual code that can be used to implement the four steps in [2] Bergin, J. (1999) Patterns for Selection. Available:
this pattern and explains the semantics of the relevant http://csis.pace.edu/~bergin/patterns/selection.html
statements and directives. [3] Bergin, J. (1997) Ten Pedagogical Patterns for
This is followed by a section of Implementation Examples Teaching Computer Science. Available:
that illustrates all four steps in the context of a several http://csis.pace.edu/~bergin/PedPat1.2.html.
simple problems. [4] Bergin, J. (1998) Six Pedagogical Patterns. Available:
The Summary section helps student in remembering the key http://csis.pace.edu/~bergin/fivepedpat.html.
issues needed to apply the pattern and serves as a quick [5] Deek., F. P., Turoff, M., and McHugh, J. A., A
reference. Common Model for Problem Solving and Program
A section on Further Explorations contains references to Development, IEEE Transactions on Education, 4
other related resources and patterns as well as a brief (1999), 331-336.
outline of related but more advanced topics, such as scope, [6] Fell, H. J., Proulx, V. K., and Rasala, R. Scaling: A
lifetime, memory allocation and deallocation. Design Pattern in Introductory Computer Science.
ACM SIGCSE Bulletin 1 (1998), 326-330.
4.3 Our Experiences [7] Rasala, R.. Function Objects, Function Templates, and
To make sure students actually read the tutorials, they were Passage by Behavior in C++. ACM SIGCSE Bulletin 1
required to comment in writing on their usefulness and on (1997), 35-38.
any problems they encountered. Most of the novice [8] Rasala, R. (1999) Toolkits in Freshman Computer
programmers found the tutorials very helpful, though Science: A Pedagogical Imperative, ACM SIGCSE
students with more programming experience felt they Bulletin 1 (1999), to appear.
already knew most of what was discussed. Some of the [9] Rasala, R. A Model Tree Iterator Class for Binary
comments stated "I thought the information in this section Search Trees. ACM SIGCSE Bulletin, 1 (1997), 72-76.
was well though out and clearly presented. The main
reason for this clarity is that the information was organized [10] Wolz, U., and Koffman, E. simpleIO: A Java Package
very well and also presented in laymen's terms. Another for Novice Interactive and Graphic Programming,
excellent addition was using both verbal description to Proceedings of the 4th Annual SIGCSE/SIGCUE
point out the different steps and properties of a function, ITiCSE’99 Conference, (June 1999), 139-142.
and also concrete examples that the reader could follow
easily and apply his/her understanding of the definitions",
or " This packet gives a student a much better visual
understanding than our text book", or "very helpful, covers
a lot, whenever I need to know a specific thing about
functions it is there. Thank you.", and "I liked how the

View publication stats