One of the projects I like to assign involves counting the letters in a set of text. In other words, how many times does each unique letter appear in a string. How many “a”s, “b’”s, etc. I usually want some thing that looks like this:
Students generally understand what I am looking for very easily. Writing the code seems to be harder. Students tend to say they don’t know where to begin. At first this project is pretty abstract to them. So today I tried something different.
I put a sentence on the board and asked them to count the letters on paper. Five minutes later we talked about how they got their count.
This was pretty interesting to me. There were several different ways of doing this which were different from how I approached the problem. Several students took the first letter in the string (a “T” in this case), copied it to a piece of paper and then traveled the length of the string counting how many times “T” was there. Then they looked at the next letter, copied it and again searched through the rest of the string counting that letter. And so on.
Other students listed all 26 letters and went from letter to letter in the string making a hash mark next to the appropriate letter on their list.
There were subtle variations on these two solutions but the basics were the same. The second solution is the one I have coded many many times over the years to where it has become the only solution I think about. The first one though is pretty interesting though.
Having two solutions game me a wonderful opportunity to talk about analyzing algorithms for efficiency. In this case we have an obvious tradeoff between space (the first solution optimizes how many counters we use) with performance (the first solution does a lot more comparisons). I wish I could say I’d planned that.
Regardless of intent I think we had a good discussion. Now we’ll see how the students do at converting the ideas into code.
3 comments:
Hi,
could you kindly explain in more detail how you discuss these two solutions (advantages,disadvantages,...) with you students? From what I read in your blog I would guess that runtime implications are too complex, but do you mention this?
Regards,
Sascha
I talk about the trade off between space and performance a bit. For example the second method using a 26 element array creates a larger array than it might need if for example there are only a handful of unique letters in the string. The first method on the other hand checks each letter in the string many more times (an average of half the total number of letters in the string) than the second method which checks each letter only once. Comparisons are somewhat expensive operations (though I don't go into a lot of detail on that) than simple assignments. I don't spend a lot of time on it though I would spend more if I had a year long course.
Thanks for the interesting comment. I think it's the right decision to tell your students there is a difference without going into much detail.
Regards,
Sascha
Post a Comment