Friday, March 27, 2015

Morse Code Project

Project ideas come from all sorts of places. Textbooks, other teachers I work with, blogs, random conversations, conferences (do you know about Nifty Assignments from SIGCSE?) and more. Some of the best come from students. Not always intentionally though. The other day I caught a student playing around on a website while I was lecturing. Apparently I wasn’t doing enough to hold his interest. The website converted letters to Morse Code and back again. There are probably many of these sites on the Internet. My first reaction was that this makes a good programming project. (Does that make me weird?) So we started talking about it as a class.

Student’s first reaction was “that’s hard” and “I don’t know Morse Code.” But of course it’s not really that hard to implement if you know how to use arrays. The tedious part is building an array to use for conversion.

            Morse[0] = ".-";
Morse[1] = "-...";
Morse[2] = "-.-.";
Morse[3] = "-..";

I've decided to do that for my students. After all I want them to use the array not go crazy trying to build one.

Converting from ASCII letters to Morse Code using a string array like this is a simple and fast operation. Big O(1) for access. We’ve already done some work like this writing a program to count the number of times various letters occur in a string. Going the other way, from code to ASCII is a little harder.

In that case we have to do a search of some kind though the array. A simple sequential search is probably the easiest way to do things. I know there are other ways. We could create a hash which would probably be faster. Or a nice binary tree (see this method – Thanks to Rebecca Dovi for the link).

These methods would be more complicated though and this is a first programming class. So we’ll talk about other ways to do it and maybe in the AP Class they’ll implement something faster and/or more complicated.

We will have a good chance to talk about the various performance issues and the various ways that arrays can be searched. I’m looking forward to the discussion.



Garth said...

Just thinking but how about converting dot and dashes to 1 and 2 then look at the sum. That breaks the letters into 7 categories. (Using 0 and 1 only gets 3 categories.) So if the dots and dashes add up to a 6 then we know it is a c,o,x, or z. In those sub groups I think you only have to look at the first three dash/dot to get the solution letter. Maybe even better the first dash/dot is a 1/2, the 2nd a 3/4 and so on. More sum categories. I should probably go do some work now.

Garth said...

After thirty seconds of Google there are a lot of Java and Python solutions out there. They involve knowing the details of the language (hashmaps in Java for instance) instead of building an algorithm. How boring.

Anonymous said...

Convert to binary (dit = 1, dah = 0), use the result as an index into an array: O(1)

Alfred Thompson said...

I got a couple of people thinking. I win! :-) Thanks for the comments guys.

Desiree said...

You definitely got people thinking.

Anonymous said...

Can you post a sample solution to his problem ?

Alfred C Thompson II said...

I could post a solution but I'd rather not do so. Too many students look for solutions and use them without understanding them. A teacher who sent me email from a verifiable school account could get one from me though.