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.