with Leigh Ann Yoder
Claude Shannon and Entropy
We opened class with a review of our homework. The students discovered that human error plays a role when it comes to coding and decoding a Huffman Code message, but hopefully can appreciate that computers don't make nearly as many errors. The students did excellent work on their Decision Trees from last week, and we quickly went over a bottom-up method of designing the tree. Lastly, I was pleased that most of the students were able to develop an algorithm for solving the Master Mind game played for homework.
We discussed a theory by Claude Shannon (first, we defined theory), which states that a message cannot be compressed less than its entropy. The students were taught the meaning of entropy and how to calculate it. They will be working on this for homework. The entire class will be testing Shannon’s theory that the entropy of text messages is, on average, 1.6. This simply means that it takes 1.6 guesses (on average) to guess each letter of a message.
Most of our class time was focused on introducing our new unit. Now that the students have a firm fundamental understanding of data representation, it is time to move on. In the next few weeks, we will focus on putting computers to work. Specifically, how we can access, store, and manipulate data efficiently for our benefit.
Algorithms and Linear Searching
I introduced the terms, Procedure, Sort, and Search as they pertain to Computer Science. These terms will continue to be reviewed and by the end of our unit the students will be confident of their meanings and applications. I also gave a very brief history lesson on the origins of the word algorithm. The word is related to the works of Muḥammad ibn Mūsā al-Khwārizmī, a mathematician who joined an academic center known as the House of Wisdom in Baghdad around 800 AD. He is also considered the father of Algebra.
Computers are often required to find information in large collections of data, which require quick and efficient methods. Using a simple Battleship-type game, the class is experimenting with different searching algorithms. Today we used Linear Searching to locate our partner’s ships. Students quickly identified the inefficiency of Linear Searching. Next week, we will play two more Battleship games, which will demonstrate more efficient searching methods.