Looking for interesting questions

For the winter break, I assigned this set of A exam questions (actually, just the three that don't deal with the case study) to my AP classes. I wanted to assign something that wasn't particularly heavy but I didn't want my students to forget everything over break.

As with most AP exam questions, they're long, wordy, and somewhat brain dead. They take a long time to read, but they frequently take you step by step through what they want you to do.

I remember the first time I really thought about this. It was back when the exam was given in Pascal. The curriculum required that classes cover one of the nlogn sorts but didn't specify which one. One of the free response questions literally walked the students, step by step, through the merge sort. Part one had them split an array in to two parts, part two had them write a routine that merged two sorted arrays (and explained step by step how to do it). You could get a perfect score and still know nothing about the algorithm, or even about writing a recursive routine (since the question told you exactly what to do).

I hate these types of questions. The exam tests coders, not computer scientists. Programming competition problems (such as from the USACO) are much more interesting, but from a beginners point of view they have their own problems. Beginners might not have enough tools to attack them, and at times they're all or nothing – they're not set up to develop a simple, working solution that you can then improve on.

So, I'm always looking for interesting questions for my students. Problems that a student can attack with a minimal skill set, but can be refined through analysis or upon studying more advanced techniques.

I guess the first problem of this nature that I usually do with my AP students, usually deals with counting frequencies of test student test scores, identifying students by their four digit ID number. Most students start by creating a huge list all the tests for all the students, but some, and soon all, realize that by using the ID number as an index into an array, they can solve this type of problem much more efficiently. Looking at this technique early also sets the stage for looking at topics such as radix sorting and hashing later on.

This weekend I stumbled upon this problem and we'll probably look at in in class some time this week. I like it because you can easily get a naive solution, but it lends it self to a step wise refinement that works well in the classroom.

A few years ago, I also discovered a wonderful article by David Ginat, titled "Effective binary perspectives in algorithmic problem solving" which you can get if you are an ACM member here.

Both the stuff in Ginat's piece and the bowling ball article are nice because they can be handled naively with brute force approaches using arrays, but with a little cleverness you can do much better.

Of course, as students progress through our classes, we have more flexibility as to types of questions. For example, once we do search and other recursive algorithms a few weeks from now, I can present problems that lead to dynamic programming solutions.

I'd love to hear any interesting accessible problems you've come across in your computing careers.