[A transcript of the SIGCSE 2008 conference: Table of Contents]
Last year's Nifty Assignments at SIGCSE merited only a retro-chic reference in my blog. I thought that was unusual until I looked back and noticed that I mentioned it not at all in 2006 or 2005. I guess that's not too surprising. The first few years of the now-annual panel were full of excitement, as many of the best-known folks in the SIGCSE shared some of their best assignments. These folks are also among the better teachers you'll find, and even when their assignments were only okay their presentations alone were worth seeing. As the years have passed, the excitement of the assignments and presentations alike have waned, even as the panel remains a must-see for many at the conference. Still, each year I seem to find some nugget to take home with me. This year's panel actually offered a couple of neat little assignments, and one good idea. The good idea came late in Cay Horstmann's presentation: have students build a small application using an open-source framework, and then critique the design of the framework. In courses where we want students to discuss design, too often we only read code and talk in the abstract. The best way to "get" a design is to live with it for a while. One small app may not be enough, but it's a start. One of the niftier assignments was a twist on an old standard, Huffman coding, that made it accessible to first-semester students. Creating a Huffman code is usually reserved for a course in data structures and algorithms because the technique involves growing a tree of character sets, and the idea of trees -- let alone implementing them -- is considered by most people beyond CS1 students. McGuire and Murtagh take advantage of a nifty fact: If you are interested only in determining how many bits you need to encode a sequence, not in doing the encoding itself, then all you need to do is execute the loop that replaces the two smallest values in the collection with their sum. A simple linear structure suffices, and the code comes to resemble the selection part of a selection sort. This assignment gives you a way to talk to students about data compression and how different techniques give different compression rates. The other twist in this assignment is that McGuire and Murtagh apply the coding to images, not text strings. This is something I tried in my media computation CS1 in the fall of 2006, with both sounds and images. I liked the result and will probably try something like it the next time I teach CS1.
The other assignment that grabbed my attention was
Baker Franke's
Catching Plagiarists.
This assignment isn't all that much different from many
of the common text processing tasks folks use in CS1, but
it is framed in a way that students find irresistible:
detecting plagiarism. I used to tell my intro students,
"Copy and paste is your life", which always drew a few
laughs. They knew just how true it was. With universal
web access and the growth of Wikipedia, I think my claim
is more true now than it was then, to the point that
students think nothing of liberal re-use of others'
words. This assignment gets students to think about
just how easy it is to detect certain kinds of copying.
So, putting the task in a context that is meaningful and
way relevant ups the niftiness factor by a notch or two.
The fact that it can use a data sets both small and large
means that the students can run head-first into the idea
that some algorithms use much more time or space
than others, and that their program may not have enough
of one or both of these resources to finish the job on
an input that they consider tiny -- a MB or two. (Heck,
that's not even enough space for a decent song.)
Another thing I liked about this assignment is that it
is, by most standards, underspecified. You could tell
students this little: "Write a program to find the common
word sequences among a set of documents. Your input
will be a set of plain-text documents and a number
n, and your output will be a display showing the
number of n-word sequences each document has in
common with every other document in the set." Franke
presented his assignment as requiring little prep, with
a simple problem statement of this sort, so I was a
little disappointed to see that his assignment write-up
is four pages with a lot more verbiage. I think it
would be neat to simply tell the students the motivating
story and then give them the five-line assignment. After
students have had a chance to think about their approach,
I'd like to talk to them about possibilities and help
them think through the design.
Then again, I have to cut Franke some slack. He is a
high school instructor, so his students are even younger
than mine. I'm encouraged to think that high school
students anywhere are working on such a cool problem.
-----