an eight year old solves the bin packing packing problem

This year my eight year old daughter did another operations research science fair project. Check out her previous projects involving the subset sum project [Link] and rolling dice to see how likely it was to roll matching numbers [Link].

My daughter wanted to recreate her subset sum project from first grade (it was a lot of fun!). I proposed that she do a similar project that had the same fun features as her subset sub problem: dice and Velcro. She asked me for some help. I proposed the bin packing problem to my daughter instead so she could learn something new. I explained the idea in terms of pizza:

Suppose you have a bunch of boxes with some leftover pizza in them. How should you move the leftover pizza into the fewest number of boxes without breaking the pieces apart?

She was sold. Bin packing was more complicated than her first two projects. In the subset sum product, she simply had to identify the subset of items that added up to 10. Here, all items would have to be placed in a bin (“pizza box”). I was worried about a combinatorial explosion from even small problem instances (we had 10 items). To address this, I proposed that she use the first fit decreasing and the first fit increasing algorithms. This way, we had a control group (first fit increasing). We called them “big pieces first” or “little pieces first.”

For those of you who are curious about offline bin packing algorithms, the first fit decreasing and the first fit increasing algorithms both have approximation guarantees of 11/9 * OPT + 1. However, the first fit decreasing tends to work better in practice.

My daughter found solutions using both algorithms for ten randomly generated problem instances. At that point, the experimental set-up started to fall apart (the Velcro was better at sticking to itself than to her “pizza” pieces). In general, the first fit decreasing algorithm worked very well. In fact, she was not able to improve the solution by rearranging the pieces. The first fit increasing algorithm found the optimal solution in only three of the instances.

Here are a couple of pictures from her project.

There were things that I liked and disliked about the bin packing problem. I’ll start with my dislikes. I’ll be the first to admit that this is a complicated problem. She could not have come up with the topic on her own. Other kids, for example, chose simple M&M probability problems. Unlike the subset sum project that was a glorified addition problem (but very suitable for third graders), this bin packing problem involved a series of steps to solve an algorithm. This was a difference! My eight year old loves games that involve complicated sets of rules so this was right up her alley, but I cannot imagine all eight year olds being ready for this. This project could easily be “enough” for a high school student, although I would recommend that they replace the Velcro with programming.

Here is what I liked about the bin packing problem: it was manageable and fun for an eight year old, even with relatively small problem instances. I highly recommend randomly generating problem instances with dice. Once we made the experimental set-up, my daughter could do the project herself and record the data.

I also liked that this project focused on an algorithm rather than a math problem. I didn’t think about that when we set out. Kids don’t really get to learn about algorithms in K-12 education, at least not explicitly. They see algorithms all the time, especially in third grade when she has learned how to do long addition and subtraction. And she could understand the bin packing algorithms. I asked her which algorithm she thought would be best, and she was able to think her way through the process. It became quite obvious why the “big pieces first” algorithm performed so well after trying the algorithms once.

My daughter did this project at the heels of Mark Zuckerberg and Bill Gates’s plea for kids to learn how to program in K-12. It starts with learning about algorithms. The craft of breaking down a procedure into a series of logical step-by-step instructions is a big part of learning about algorithms, and that can be done at a very young age. The bin packing problem turned out to be a rather nice way to get my eight year old daughter started with algorithms.