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?
BTW if you are interested in the math around Binary Palindromes check out Counting Binary and Hexadecimal Palindromes on the Exploring Binary blog.
Comments
Anonymous
January 12, 2010
Writing a program to count palindromes is unnecessary, as you said, but doing so could motivate a search for a formula (if you hadn't already realized a formula was possible). A curious mind would see a pattern in the results and then look into the math behind it. (I do that all the time.) BTW, check out http://www.research.att.com/~njas/sequences/A050250. It gives a formula for the number of nonzero palindromes less than 10^n, and gives a list of the first n: 9, 18, 108, 198, 1098, 1998, 10998, 19998, ... . (they might have defined "palindrome" differently than you.)Anonymous
January 15, 2010
I agree with you that we want to teach students about how to analyze performance in addition to solving the problem correctly. I see just as much premature optimization as I see wasteful implementation. Now that there's no more AB exam for APCS, big O notation isn't in the curriculum. So how do we teach performance? One way that happened for me unintentionally this year was by using the Processing environment. http://processing.org I had a student who wanted to load a large number of pretty big images into memory. The environment runs on the JVM with some reasonable default, so it ran out of memory. And instead of letting him increase the allocation, I forced him to profile exactly how many images he could load, test the effect of smaller image dimensions, load and unload the images on the fly, etc. Another student hit performance problems because he was resizing many background images on each frame. I made him create a simple timer and wrap each call (one by one) to see what was taking up all the milliseconds. He found the problem within 10 minutes. These aren't formal approaches to performance but they're practical and closer to what a working programmer would do. Don't get me wrong: I love characterizing various algorithms in terms of time and space, and I think it's important that students eventually see how to do that. But a little motivation for why we use these formal tools goes a long way.Anonymous
January 23, 2010
Thanks for the plug Alfred (I was working on that article when your post came out -- lots of interest in binary palindromes this year as you pointed out.)Anonymous
January 25, 2010
The end of this article is totally true. During all my studies, bachlor degree and master degree. There was only one of all my projects which was unreallistic to do using brute force. It was about genetic algorithm. Before talk about complexity, and other problems, let us face the realy problems. I think that if we face the problem before having a solution will be more relevant. For instance why not start project before start course? Maybe this is a way tohave new solution to problems, or jsut a way to have a better comprehension about topics that we have during courses.