Maxed Out
This year I decided to switch up the lab where students first encounter the algorithm for finding the maximum value in an array. In the past, I’ve given them a Movie object that represents a film (title, genre, rating) and had them build a MovieTheater that contains an array of Movie objects and can tell you which of its Movies has the highest rating.
The problem was that the relationship between Movie and MovieTheater (a collection of Movies) isn’t immediately obvious. Maybe a MovieTheater is an object that displays Movies. Maybe a MovieTheater is an object that can match an AudienceMember with a Movie they’ll like. Who knows?
So I decided instead to go with a Song (still with title, genre, and rating properties) and a MusicPlayer. The relationship is much more obvious — everyone got that your MusicPlayer contains a list of Songs. We even agree on what that list is called: a playlist.
The vocab change was good, but it didn’t fix the fact that I was asking students to learn two things at the same time. First, there’s the algorithm itself — ingesting or generating the idea of one variable for the running maximum, another variable to hold the index of that max, and then the question of how to initialize those things properly. That’s okay. But then there’s also the concept of an array of objects, requiring us to access a property of the object in the array so we can use that property value for comparison purposes. Cognitive overload.
This double-whammy may be part of the reason people turn against the “objects-early” approach to CS education. It’s not like we can really get away from using primitives in a language like Java. The object-first way would have us embrace objects (and collection objects like ArrayList, and structures for traversing them, like the for-each loop) from the very start, so that the idea of a set of anything other than objects might seem strange. But to my thinking, objects themselves are more complex entities, comprising both state and functions, and they require a lot of boilerplate when we define them in Java — unless we use some kind of special programming environment.
This all seems a little contraptionary, and leads my thoughts back to TeachScheme, which I have been meaning to investigate since a bunch of people I respect, including Hélène Martin, have good things to say about it. The authors of How to Design Programs recently posted a draft of How to Design Classes and I’m looking forward to reading it more closely now that it’s public.
And Yet It Moves 
I think that you’ll find Python a friendlier approach than Scheme for this, as it allows some very simple code for the problem.
Python has explicit containers (like lists and sets), so you can have a list of song objects and do things like
best_rating = max( [s.rating for s in songs] )
favorite_songs = [ s for s in songs if s.rating==best_rating ]
print [s.name for s in songs]
I don’t think language matters — the point (as I understand it), isn’t to get the highest-rated song but to discover and practice applying a useful algorithmic technique.
That’s right — the challenge is for students to figure out how the Python built-in function max(iterable) could be implemented.
Yes! Yes, yes yes. I started reading your post and in the second paragraph I was thinking “I’m glad my students know how to find the maximum in a list without thinking about objects.” This is a great example of where all the objects overhead takes over when really I think you were trying to make a relatively straightforward algorithmic point — sometimes it’s useful to have some kind of value that’s initialized at the beginning and keeps track of information over a list.
To me, this fits in with cumulative sums, is the value X present in the collection and other kinds of little related algorithmic tricks. I explicitly teach all of those together and I find that when we reach OO, students reach for those tools fairly naturally. We’re then ready to use the Comparable interface and Collections.max which I think is what most Java programmers would use?
I highly recommend looking at the TeachScheme (now Program by Design) approach. It’s very deliberate in its pacing and gives students great mental models. I’m not really into How to Design Classes since it makes very idiosyncratic use of Java. It’s a little too ‘pure’ for my taste (‘this is how thou shalt program’ with complete dismissal of how people actually do) though there are great ideas to take from it.
I agree! All those algorithmic tricks should definitely be in the same Codingbat set (somewhere between the existing Array-1 and Array-2). We did this lab back at the end of September.
When you teach all these loop-based tricks, what is the motivation? I hate that use of the verb “motivate,” but do you know what I mean? I’m open to the possibility that I’m pseudoteaching by making up fake use cases for everything.
Call me old fashioned, but I’m skeptical of the use of ‘real’ context (dy/dan is staring at me angrily from somewhere, I’m sure). I think the whole point of teachers is that we can abstract out important, reusable concepts and add them to our students’ bag of tricks so that they can quickly get to a point where they can solve real problems of their choosing.
When I show a new idea, I like to ask students when they imagine it might come in handy. In this case, I might get suggestions like ‘if you’re looking for a single winner in a contest’ and stuff like that. I probably wouldn’t get your examples because really, when do you want to find the highest ranked movie? Don’t you generally want a sorted list? Once we’ve agreed that there’s a use for the generalized concept I want to teach, I teach it essentially devoid of context and stress that it’s broadly applicable.
I first showed these kinds of algorithms with Strings. Cumulative sums are neat for things like Caesar cyphers/ROT-13. You can look at whether a String contains a particular char (boolean flag kind of deal). You can ask the user for a bunch of Strings and report which was the longest.
If the point is to figure out how to implement max(iterable), then make that the explicit assignment. First have them learn how to use the built-in max, then do a “look under the hood” for them to figure out how to implement such a thing. Once they’ve seen what it is good for, you don’t need pseudocontext to get them interested in finding out how to implement it. Other iterable operators (like “sum”) could be handled the same way.
I just noticed a bug in my Python script—the last line should have been
print [s.name for s in favorite_songs]
Oh, I like this idea a lot: First, show how max is legitimately useful as a library method. Then go back and have the students implement it. You’re absolutely right that making up pseudocontext is lame. It’s way cooler to just see the goal and work to build our own implementation for the key methods. I’ve been doing a similar thing lately with search / sort (students comparing the performance of their sorting implementations versus Arrays.sort) and it’s working well.