Toys Are Us: Presenting Mathematical Concepts in CS1/CS2

Paolo Bucci, Timothy J. Long, Bruce W. Weide (The Ohio State University)
Joe Hollingsworth (Indiana University Southeast)

1.  Abstract

2.  A Pedagogical Challenge

Our CS1/CS2 sequence is based first and foremost on system thinking.  Throughout CS1, students act as clients of many "off-the-shelf" software components without seeing the implementations of any of the components.  Instead, students are presented with a client description of each component, including a formal mathematical model of the values that objects can assume as well as formal pre- and post-conditions for all operations.  Thus, from the very beginning of CS1, students are expected to read and understand formal mathematical descriptions of software components.

Not surprisingly, this commitment to formal specifications in CS1 and CS2 presents interesting pedagogical challenges.  For example:

• Students may be asked to understand mathematical structures not yet introduced in any of their math courses, such as strings, binary trees, and weighted graphs.
• Even for mathematical structures that are familiar, students may be asked to understand new or different notation.  Mathematical concepts are often presented in a highly symbolic form.  Because of this, something as simple as different syntax can give the appearance of a new mathematical concept.
• The whole idea of taking mathematics outside its usual context -- the mathematics classroom -- and using it to model other things presents an intellectual hurdle.

When using mathematics to formally describe software components, we are interested primarily in students being able to read and understand mathematics as opposed to being able to write mathematics.  This observation is crucial because of its consequences; namely,  the central pedagogical challenge is to help students formulate appropriate mental models of mathematical concepts so they can attach "meanings" to the symbols they are reading.  Through appropriate mental models, students can translate written symbols into meaningful representations of those symbols in their minds.  In turn, they can formulate meaningful models for the behavior of software components.
 

3.  A "Low-Tech" Approach

The use of physical manipulatives has been part of mathematics instruction for several decades.  It has been shown that the use of manipulative materials can increase mathematics achievement and improve students' attitudes toward mathematics [6].  It is interesting to note that the same study did not find significant differences between instruction with pictures and diagrams and instruction with symbols.  There seems to be something special about the clear kinesthetic nature of physical manipulatives that gives them this edge with many students.  We, too, have found the use of physical manipulatives, such as children's stacking cups and Lego blocks, to be amazingly effective.  When mathematical models for software-component behavior are demonstrated and practiced using manipulatives, heretofore uninterpreted symbols acquire actual intuitive meaning!

In this paper, we illustrate our ideas through three examples.  Each example includes:

• a client description of a software component using formal mathematical models to describe component behavior, and
• a discussion of the physical manipulatives we use as metaphors to help students formulate appropriate mental models.

4.  Queue Modeled by Mathematical Strings

String theory is extremely useful for specifying software components.  We use it for stacks, text strings, one-way and two-way lists, and tokenizing machines, for example.  How do we help students in CS1 read and understand specifications involving string theory?  We use stacking plastic cups, the kind sold in the toddler section of toy stores.  Through in-class demonstrations using "strings of plastic cups", we can easily and quickly give meaning to the idea of a string of T and to equations such as q = #q * <#x>. Figures 4.1 and 4.2 show the behavior of the Add operation.
 

Figure 4.1. Add - before	Figure 4.2. Add - after

By the way, plastic stacking cups also work great for demonstrating sorting algorithms (see Figures 4.3-4.7 below for pictures of a queue being sorted with quicksort).  Our experience is that students grasp the algorithms much more quickly, requiring less class time, and that their implementations of the algorithms are less likely to be defective.
 

Figure 4.3. Queue before Quicksort	Figure 4.4. Selecting partition element

Figure 4.5. Two queues after partition	Figure 4.6. Two queues sorted

Figure 4.7. Original queue sorted

 

5.  Partial Map Modeled by Finite Mathematical Functions

• (d, r) is in #m (the incoming value of m maps d to the outgoing value of r; parameter d is preserved, so its incoming and outgoing values are the same)
• m = #m - {(d, r)} (the outgoing value of m is the incoming value of m without the pair (d, r))
• d = d_copy  (the outgoing value of d_copy will just be the "copy of d" that was in the incoming value of m and that m no longer needs).

To help students understand the mathematical model for the Partial_Map component, we use a clear plastic bag, like a sandwich bag, and Lego blocks.  The plastic bag represents the set.  Small Lego blocks are the domain items, and larger Lego blocks are the range items.  When a "domain" Lego (D-Lego) is mapped to a "range" Lego (R-Lego), the D-Lego is snapped onto the R-Lego and the pair is put into the plastic bag.  It is easy to distinguish between a D-Lego and an R-Lego because they are different sizes, and it is easy to distinguish among R-Legos or R-Legos because they are different colors.  Math operations such as IS_DEFINED (m, d) are easy to explain -- just look into the plastic bag and see if there is a D-Lego equal to (i.e., the same color as) d.  The function property is equally easy to explain -- each color of D-Lego can appear in the bag at most once. Figures 5.1 and 5.2 show the behavior of the Undefine operation.
 

Figure 5.1. Undefine - before	Figure 5.2. Undefine - after

 

6.  Binary Tree Modeled by Mathematical Binary Trees

To help students understand the mathematical concept of a binary tree, we use PVC pipe (white plastic pipe used for plumbing projects).  The items in the tree are PVC joints with bright colors, such as red and blue.  If an item, say a, is the left child of an item, say b, then there is a section of white PVC pipe connecting the two PVC joints for a and b and this represents the parent/child relationship in a binary tree.  To illustrate the effect of COMPOSE, it is a simple matter to take two PVC models of binary trees and a new PVC-joint item, and "hook them up" with two new sections of pipe.  Explaining the inverse operation and the recursive structure of binary trees is just as easy. Figures 6.1 and 6.2 show the behavior of the Decompose operation.
 

Figure 6.1. Decompose - before	Figure 6.2. Decompose - after

PVC toys also work great for illustrating more complex binary tree operations such as inserting into a binary search tree or deleting from a heap.  Item values can be written on post-it notes and stuck on the PVC joints.  Then, the algorithm is "animated" by moving the post-it notes according to the movement of values by the algorithms.  (PVC pipes and different kinds of joints are also useful when illustrating template instantiation, which is explained as analogous to plumbing.  The details of this metaphor are a bit too complicated to include in this short paper.)
 

7.  What Do Students Think?

8.  Final Comments

9.  Acknowledgments

References

Appendix: Component Specifications

parameters

  type T

interface

  type Queue is string of T
    initialization ensures q = empty_string

  operation Add (
      alters    q: Queue
      consumes  x: T
    )
    ensures q = #q * <#x>

  operation Remove (
      alters    q: Queue
      produces  x: T
    )
    requires q /= empty_string
    ensures  #q = <x> * q

  operation Size (
      preserves q: Queue
    ): Integer
    ensures Size = |q|

parameters

  type D, R

interface

  type Partial_Map is finite set of
      (d_value: D, r_value: R)
    constraint
      for all d: D, r1, r2: R
        (((d,r1) is in m and (d,r2) is in m)
          implies r1 = r2)
    initialization ensures m = empty_set

  operation Define (
      alters    m: Partial_Map
      consumes  d: D
      consumes  r: R
    )
    requires not IS_DEFINED (m, d)
    ensures  m = #m union {(#d,#r)}

  operation Undefine (
      alters    m: Partial_Map
      preserves d: D
      produces  d_copy: D
      produces  r: R
    )
    requires IS_DEFINED (m, d)
    ensures  (d,r) is in #m and
              m = #m - {(d,r)} and
              d = d_copy

  operation Undefine_Any (
      alters    m: Partial_Map
      produces  d: D
      produces  r: R
    )
    requires  m /= empty_set
    ensures   (d,r) is in #m and
               m = #m - {(d,r)}

  operation Is_Defined (
      preserves m: Partial_Map
      preserves d: D
    ): Boolean
    ensures Is_Defined = IS_DEFINED (m, d)

  operation Size (
      preserves m: Partial_Map
    ): Integer
    ensures Size = |m|

parameters

  type T

interface

  type Binary_Tree is binary tree of T
    initialization ensures t = empty_tree

  operation Compose (
      produces  t: Binary_Tree
      consumes  x: T
      consumes  left: Binary_Tree
      consumes  right: Binary_Tree
    )
    ensures t = COMPOSE (#x, #left, #right)

  operation Decompose (
      consumes  t: Binary_Tree
      produces  x: T
      produces  left: Binary_Tree
      produces  right: Binary_Tree
    )
    requires t /= empty_tree
    ensures  #t = COMPOSE (x, left, right)

  operation Size (
      preserves t: Binary_Tree
    ): Integer
    ensures Size = |t|