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
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
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.