Discrete Math - Day 36

Today was a transition day to begin reviewing for the upcoming mid-term. The mid-term will cover all material up to this point. Because we have a Spring break next week, I didn't want to start looking at congruence and modulo arithmetic until after the break. This leaves two full days for review.

Today, I started class by giving them a cipher function and asking them to use it. I debated in my mind whether or not to use a valid cipher function. I elected to use C(x) = 2x + 3. When using this cipher function, some letters get mapped to the same value. What I debated with was whether or not this would be the time to introduce the idea that not all equations work as cipher functions.

Students worked through the cipher and did notice that the cipher mapped different letters to the same value. I told them that we would look at why this happened after the break but to just proceed for now since we weren't going to decipher any messages. I believe this will enable me to re-introduce this idea after the break and ask the question of what went wrong with the cipher function and how we could avoid a similar problem. The result we need is directly connected to the concepts of congruence and modular arithmetic that we will be studying.

After ciphering text I asked students to find D(x), the decipher function, for C(x). Many students struggled with this. They would come up with a result and I would ask them if they tried verifying their result. They were unsure how to do this. I told them if they picked a value and passed it through C(x) then when that result was put in D(x), in essence calculating D(C(x)), the should get their original value used for x back. Once they tried this for a specific value they could see that their decipher function was not correct.

Eventually, students started to remember how to find inverse functions of linear equations and found that D(x) = (x - 3) / 2.

The next problem I posed was related to data encoding. I reviewed the ideas of bits and bytes and then asked students to count the number of characters that could be represented by one byte, which consists of eight bits containing either a zero or one. Students were somewhat tentative, but most figured out that the result was 28 = 256 characters.

I briefly described how this allowed the representation of 26 lower-case letters, 26 upper-case letters, 10 digits, plus many special characters such as punctuation with allowance to represent additional characters. However, the Chinese character set contains over 2,000 characters. How many bits are need to represent 2,000 characters?

Students quickly figured out that 11 bits would be able to represent 2,000 characters. Computers use bytes as their base unit of storage, so 11 bits means that we actually need to use two bytes. How many characters can two bytes hold? Students extended what they were doing to see that two bytes hold 216 = 65,536 characters.

These problems are perfect extensions for the material that was just covered. They connect the ideas of data encoding that are fundamental to cryptography with the basic concepts of counting. The need to know how many things can be represented in one or two bytes is a critical aspect of data representation in computer science. Historically, it was a significant change to convert from single-byte to double-byte representations to address issues arising from the expansion of the world wide web and the global economy.

Visit the class summary for a student's perspective and to view the lesson slides.