I’ve had my students working on a little exercise this week. It’s simple and I know that a lot of teachers use similar projects. The idea is to build a triangle or in this case two of them. 
Now as long as I have seen this project I have always used nested loops to generate the triangles. The outer loop controls the rows and the inner loop the columns. It’s a pretty natural way of thinking especially when it comes in the middle of a unit on loops in a first course. As far as I can recall all of my students have solved this the same basic way – nested loops.
Today I was trying to help a struggling student and realized that there was a way without nested loops. Well it turns out there are several ways one can do this. At least one depends on knowing about some methods built in to the string class in the .NET platform. Other ways should be easily determined by beginners so I’ll not go into that here. Besides, that is not the point of this post.
The point is that it is easy to get into ruts. Easy to fall into the same old solution time after time even as we add more tools to our toolbox. From time to time it is helpful to step back and look at old problems with new eyes. Grace Hopper used to promise her audiences that if they ever said “we’ve always done it that way” she would appear and haunt them. I can’t hear that phrase without thinking of her so I guess she was serious.
I wonder what other old projects I should be taking a new look at?
You're right; I think most people have used that example. I wouldn't beat yourself up on the nested loop solution. If the end goal is to teach nesting, then this is a very visual and satisfying way of doing things that the students "get" immediately.
ReplyDeleteOff hand, I can think of a couple of other ways of doing it - one with arrays and the other with string manipulation. I guess the bigger question is - is it important to get the exact output or is it important to understand the underlying and concepts and principles.
It never hurts to show multiple ways to solve a problem. It's then that you can talk about elegance in programming, efficiency, etc.
I'd be interested in seeing your new solution.
I agree with Doug - we do these types of problems during loops to both explore nested looping and also to discuss things that can arise.
ReplyDeleteWe usually factor out the inner loop into a "line" routine that builds lines of spaces or stars, for example.
Another thing worth discussing is hidden complexity. Even if you are using a built in string function to build a string of length n, it could still be looping internally. Maybe it's using something highly optimized like "rep movsb" or something, but it's still O(n) with respect to number of characters printed so in that regard, even without explicit nested loops you've got O(n^2).
It would be interesting to see how various solutions worked deep down after compilers got done with them. Lots of optimizations are possible. One solution I cam up with was to create full sized strings at the beginning and then use a Substring method for the display. My gut tells me that would be pretty efficient.
ReplyDeleteThat can get interesting.
ReplyDeleteIs the string a literal and potentially shared or allocated at run time (as in Java String literal vs allocated instances).
Does substring allocate a new string or does it index into an existing one?
More good discussion points
If I were writing substring I would index into an existing one. But then I would also pre-allocate string space if the optimizer could tell that a string would be extended later. :-)
ReplyDeleteOne of the best things about teaching kids that are just learning programming is that they are not stuck in convention. They find all sorts of interesting solutions to programming problems that experience would tell us is not the way to do the problem. Blame it on Google. My conversation usually goes:
ReplyDeleteMe "Where did you get this?"
Student "I found something online and modified it to work."
Me "Cool."
If I want to teach a particular method I have to be very specific. Last year I gave a text finding problem, find a particular string in a document. I got 3 very good solutions using methods that I did not even know of. Cool. Oh, 4 kids in the class.