Brute Force or is there an easy way?

This year being ‘10 has lead to a lot of talk about numbers that look like binary numbers 1/11/10 or 11110 for example. Related to this is talk about palindrome dates. For example with a leading zero 1/11/10 becomes 011110 which is the same backwards and forwards. Of course a purist might point out that the year is 2010 and ask “didn’t you learn anything from the Y2K problem?” Or “real numbers don’t have leading zeros!” But purism is less fun so I ignore those people. Well at least when playing with numbers for fun. But I was thinking a bit about palindrome numbers while driving the other day. Hey, it’s safer than driving while Twittering. I started to think about writing code to count palindrome numbers. As I thought about how to get the computer to generate them I realized that the count could be easily calculated. Of course seeing myself as a programmer before a mathematician my mind went to a program before an algorithm. Silly probably but at least in my defense I worked on a couple of algorithms and thought things through a bit.

There are 19 two-digit palindrome numbers. There are 18 times 9 three-digit numbers. And so on. There is no need to write a program to count them. You can easily build an equation that calculates the number based on the number of digits. Go ahead do it. I’ll wait. Anyone come back?

I think all of us have to be careful when we think about solving problems. We all have favorite tools that we like to use but they are not always the best for the job. Sure you can bank a board with a hammer and get it to the right length but it is not going to be pretty. Using a saw is better for some jobs. Likewise we can’t always assume that the fast or best way to handle all mathematical tasks is a computer program or even a mathematical formula. For example while we can easily calculate the number of 5 digit palindrome numbers generating a list really calls for a program.

Of course there are easy and had ways to do that task as well. You could generate every five-digit number, run them through a method that checks to see if it is a palindrome and only print the numbers that pass the test. But that brute force way is pretty wasteful of time and resources. With a little thought you can come up with an algorithm that just generates and prints palindrome numbers with no waste. I’m leaving that to the student too.

I find that students look for the solution that is easiest to implement with little regard for performance. The AP CS curriculum teaches about performance calculations (emphasis on Big-O notation) but I wonder how much of it sinks in. How often do students apply that thinking to their own code? I suspect not as much as we’d all like. It’s an important topic though. Yes computers are getting faster but problems are getting larger. Somewhere in every problem there is a cross over between the time it takes to develop a really efficient algorithm and how much time it saves in the end. Brute force solutions only work for small problems. This is of course one of the problems with assigning small problems or small data sets for student projects. Ultimately we have to create projects that are manageable for students but that also force them to conceder performance. Failing to do that is a disservice I think. What do you think?