A Story About Odd and Even Numbers

This is a story my son and I wrote together when he was four. He came up with the basic story. I helped with the English and with the turtle character.

The Seven Jellybeans

Once upon a time, there was a lizard and a snake who were friends. They played together and had fun everyday until one day, the lizard's daddy gave them a bag of jellybeans to share.

In the bag, there were seven jellybeans. The lizard divided the jellybeans into two piles. His pile had 5 jellybeans, and the snake's pile had 2 jellybeans.

The snake said, “Wait a minute. That's not fair. You have more jellybeans than I do. You'd better give me one more jellybean.”

So the lizard gave the snake one more jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, that's still not fair. You still have more jellybeans than I do. You'd better give me one more jellybean.”

So the lizard gave the snake one more jellybean. And now the lizard had 3 jellybeans, and the snake had 4 jellybeans. Now the snake was happy, but the lizard said, “Hey, that's not fair. Now you have more jellybeans than I do. You'd better give me back one jellybean.”

So the snake gave the lizard back one jellybean. And now the lizard had 4 jellybeans, and the snake had 3 jellybeans. The snake said, “Hey, what happened? Now you have more jellybeans again. You must have cheated!”

And then the lizard and the snake began to fight.

While they were fighting, their friend the turtle walked by. He asked them why they were fighting, and the lizard and the snake told him.

“Hmm,” said the turtle. “If I solve your problem, will you give me one jellybean?”

The lizard and the snake didn't want to share their jellybeans, but they didn't want to fight either, so they agreed.

The turtle slowly ate one jellybean. Then he turned around and began to walk away.

“Wait a minute,"” shouted the lizard and the snake together. “You said that if we gave you one jellybean, you would solve our problem.”

“I just did,” said the turtle as he continued to walk away.

The lizard and the snake looked at their piles of jellybeans. The lizard had 3 jellybeans and the snake had 3 jellybeans. They happily ate their jellybeans, and soon all of the jellybeans disappeared.

The next day, the snake's mommy gave them a box of raisins to share. The lizard and the snake opened the box and counted seven raisins. “Oh no,” they said, and they went to look for the turtle to give him one of their raisins.

Designing a Data Structure

Students are rarely given an opportunity to design an algorithmically non-trivial data structure. We might give them a scenario and ask them to design how to represent the data, but that design decision is usually something like choosing between a hash table or an array or a linked-structure. Once that high level decision is made, there is very little left to design.

One reason for this is that many data structures depend on non-obvious invariants. Most students are pretty shaky on the whole idea of invariants to begin with; they're never going to spontaneously come up with something like the rules describing red-black trees or leftist heaps. With these kinds of data structures, we basically present the finished product and possibly ask them to implement and/or analyze the data structure, but we never ask them to design something like that.

For several years, I've been trying to give students a taste of real data structure design, using the sample priority queue below. I usually do this in class, where I can help steer them with gentle questioning, but I try very hard to make sure that they come up with the important parts.

I always do this at some point after the students have studied binary heaps (the kind typically used in heapsort). I briefly review the priority queue operations binary heaps support (insert, findMin, and deleteMin) and the basic idea of heap-ordered trees. Then, I introduce the idea of merging two heaps. With binary heaps, this takes O(N) time, or even O(N log N) time, if done naively. I ask them to design a new data structure to support merging in O(log n) time, while the other priority queue operations run in the same bounds as for binary heaps, O(1) for findMin and O(log N) for insert and deleteMin. I suggest that they use heap-ordered binary trees (real trees, rather than simulating trees using arrays like in binary heaps), but that they can modify these trees in any way that is helpful.

With heap-ordered trees, findMin is trivial—it just returns the root. To get their creative juices flowing, I then ask them to implement insert and deleteMin in terms of merge. This is also pretty easy: insert creates a new singleton tree and calls merge; deleteMin discards the root and calls merge on the two children of the root. So the whole problem boils down to merging two trees efficiently.

At this point, they usually flounder for a while, which is both ok and expected. Some floundering is good. Naturally, they'll start to get a little frustrated. That, too, is ok and expected. I just don't want them to get frustrated to the point where they shut down. If the floundering continues too long without any progress, I'll ask them what they can tell immediately about the result tree by only looking at the roots of the input trees. They'll quickly reply that the smaller of the two input roots becomes the root of the result tree. So I have them draw that much of the result. Depending on how things are going, I may further suggest that they draw two question marks for the children of the root in the result tree.

Then the students will play for a while with how to fill in those question marks. There are two slots for subtrees, but we have three subtrees that need to go in those slots: the two subtrees of the “winning” input root plus the “losing” input root. To fit three subtrees into two slots, naturally we need to merge two of them and leave one unchanged. But which two should be merged?

Usually, the students will begin with some fixed strategy, such as always merge the two subtrees of the winning root. But it's easy to come up with counter-examples where such a strategy will take O(N) time.

Once it becomes clear that some smarter strategy is required, the students focus on the question of which two of the three subtrees to merge. Usually the next thing they try is merging the two subtrees with the smallest roots, which fails on the same kinds of counterexamples as before.

Eventually, based on the intuition that merge should run faster on small trees than on big trees, they try merging the two smallest trees. This is always a good learning point about ambiguity, as we realize that there are three different possible meanings of “smallest”: the smallest root according to the ordering on keys, the smallest subtree according to number of nodes, or the smallest subtree according to the height of the subtrees. We've already shot down the first one, but either of the other two will work, so I just go with whichever one the class prefers (usually smallest in number of nodes).

One catch is that to efficiently compare sizes of subtrees (either number of nodes or height), we need to store the sizes at every node. But that's easy to do by adding an extra field, and maintaining that size information is also easy, albeit slightly easier for number of nodes than for height.

Typically, we don't have a lot of time left in class at this point, so I help them with the analysis, but it's easy to show that this design supports merge in O(log N) time. And there was much rejoicing!

I call this data structure maxiphobic heaps because of the way merge avoids the biggest subtree at every step. But I don't tell the students that name until after they've already come up with the design.

On Balanced Trees and Car Insurance

I usually don't teach our Data Structures course, but I often give a guest lecture about balanced binary search trees. This comes right after they've learned about plain (unbalanced) binary search trees. Often the previous lesson has ended with an illustration of what happens when values are inserted into the tree in sorted order.

After reviewing that pathological case and how it can easily arise in practice, I dive in and explain how to keep the trees balanced. In my case, I use red-black trees, but the exact choice of balancing scheme isn't critical to my point here. At the end of class, I ask them how much faster they think the balanced trees are than the unbalanced trees. They're shocked when I tell them that, most of the time, the balanced trees are slower than the unbalanced trees. As long as the data arrives in a reasonably random order, the plain binary search trees will actually end up being fairly balanced, without doing any extra work. No mucking around with colors, no rotations—of course the balanced trees are slower!

So why bother?

I tell them that it's like buying car insurance. When you buy car insurance, you hope that you're just throwing your money away. At the end of the year, if you haven't been in any accidents, you're happy to have wasted that money. Why bother? To protect against the uncommon case, to keep one unlucky event from turning into catastrophe. You pay a little bit extra all the time to keep from paying a lot extra every once in a while.

Barriers to Creativity

Last week, I had lunch with some friends of mine, all college-level instructors. I brought up the subject of creativity, which has been much on my mind lately. Our discussion highlighted some of the barriers to creativity in education, especially from the side of the instructor.

Creativity means artsy, doesn't it?

At one point, I asked the chemistry professor in our group about the role of creativity in the first few college-level chemistry courses. She was confused by the question at first, because she thought I meant something like writing poems about chemical reactions. (That reminds me of a scene in Lois McMaster Bujold's A Civil Campaign, in which a biochemist decides to rewrite the abstract to his dissertation in sonnet form. “Can you think of a word to rhyme with glyoxylate?”)

Actually, I meant creativity in the sense of creative problem solving. You know, the kind of thing MacGyver might do with 2 aspirins, a tube of superglue, and a Diet Coke. This misconception that creativity is the exclusive property of the arts is quite common. If we the instructors of techncial courses don't think of what we do as creative, then we are hardly likely to portray our discipline in a way that encourages creativity.

I'm using the word “arts” here to mean traditional arts like painting or poetry or music. I happen to think an elegant algorithm can be quite beautiful and artistic, but I don't expect a layperson to recognize it as art.

Foundations, Foundations, Foundations

A common theme in instructor comments was that students need to learn the foundations and basic skills of the discipline before they can do much that's creative. There's certainly some truth to this. But how long of an apprenticeship can we expect somebody to serve before finally exposing them to the beauty and wonder, the fun of the creative side? Do we save up all the creative parts for a senior-level capstone course (or even later), or can we intersperse skill development with appropriately-scaled opportunities to use those skills creatively?

A favorite movie of many teachers is The Karate Kid, especially the part where Mr. Miyagi teaches Daniel karate by having him do household chores such as waxing cars or painting fences. Eventually Daniel rebels at what he sees as pointless menial labor, and Mr. Miyagi demonstrates that Daniel has been learning valuable defensive moves all along. The point teachers usually draw from this example is that students can learn valuable lessons without realizing that they are learning, but there's another point here as well. What if, instead of confronting Mr. Miyagi, Daniel simply quit coming to his lessons? That's the situation we face as college teachers. If we give students too much skills development up front without any hint of a payoff, they'll simply stop taking our courses and never come back.

There's another danger as well. I saw this among my fellow students in graduate school. Students who had spent their entire undergraduate careers very successfully learning foundations and practicing skills were often lost when they were finally expected to do creative research. It was completely different from what they were used to, and often they found that they didn't like it.

Think of a piano teacher who makes her students practice nothing but scales for four years. By the time she feels her students are finally ready to play real music, she may find that the only students she has left are the ones who would rather play scales than anything else.

But...it's hard!

Incorporating creativity into a college classroom can be hard, especially in large classes. The lecture format is particularly bad at nurturing creativity in the listeners, but a teacher facing several hundred students often has little choice.

Grading also becomes substantially more difficult if you design assignments that allow students room for creativity. Suddenly, there's no longer a single, “approved” solution that can be easily checked for. Instead, you need judgement to evaluate quite different solutions individually. This can be especially difficult in a course where TAs are expected to do most of the grading.

Fortunately, I suppose, I don't have large class sizes and I don't have any TAs, so I don't have those excuses to fall back on.

Beware Pseudo-Arrays

I'm always fascinated by the kinds of programming mistakes that novices make, and what they say about that student's state of mind. I particularly enjoy mistakes that aren't really mistakes, in the sense that the student has actually gotten the code to work, but where the code clearly demostrates some flaw in that student's mental model of programming. For example, see my previous post on Boolean confusion.

Here's another example involving arrays, or rather the lack of them. I was reminded of this example just yesterday when multiple teams tried to use this idea in a local programming contest.

Suppose you are rolling some standard six-sided dice, and keeping track of how many times each number has appeared. The most natural way to do this would be to use an array indexed from 1-6. In a language with zero-based arrays, you might use indices 0-5 and subtract 1 from each die value, or you might use indices 0-6 and simply ignore index 0.

However, many novices faced with this decision will reject arrays altogether and use six separate variables, perhaps named count1, count2, count3, count4, count5, and count6. (Or, if they are really gluttons for punishment, ones, twos, threes, fours, fives, and sixes.) I call these kinds of variables pseudo-arrays.

Why use pseudo-arrays? Because real arrays are scary. Plain variables and if-statements are much friendlier! After all, why write

   count[dieValue]++;

when you could write

   if (dieValue == 1) {
      count1++;
   }
   else if (dieValue == 2) {
      count2++;
   }
   else if (dieValue == 3) {
      count3++;
   }
   else if (dieValue == 4) {
      count4++;
   }
   else if (dieValue == 5) {
      count5++;
   }
   else {
      count6++;
   }

Oh, and don't bother suggesting a switch-statement — if-statements are good enough, thank you very much.

Why do so many novices do this? In many cases, I think it is because they were first exposed to if-statements, and found them easy, and then later were exposed to loops, and found them difficult. Arrays are usually processed using loops, and are usually introduced while the beginner is still reeling from the trauma of loops. Thus, arrays become tainted and suspect. In such a novice's mind, the approach with variables and if-statements truly is easier, especially because so many of the if-statements can be programmed using cut-and-paste — the favorite editing commands of most novice programmers!

Every once in a while, I see code by somebody who has gotten over their fear of loops, but has not yet become reconciled with arrays. This can lead to gems where the student tries to loop through a pseudo-array, as in

   for (int d = 1; d <= 6; d++) {
      if (d == 1) {
         System.out.println(count1);
      }
      else if (d == 2) {
         System.out.println(count2);
      }
      else if (d == 3) {
         System.out.println(count3);
      }
      else if (d == 4) {
         System.out.println(count4);
      }
      else if (d == 5) {
         System.out.println(count5);
      }
      else {
         System.out.println(count6);
      }
   }

As Dave Barry would say, I am not making this up.