Outline of Class 17: Algorithms, continued

Miscellaneous

• This week there are a number of Take Back the Night events. I strongly encourage you to go, particularly if you don't know or understand why we need such events.
• I've used quiz 3 to grade assignment five. I haven't commented on your individual answers, but I will note that
  • Few groups had uniform answers on the first two questions.
  • You need to think about what the last digit of 2.0/3.0 should be (is it 6 or 7)?
  • Surprisingly many of you didn't set a precision or padding on the first longer answer, which makes it unclear as to how you're going to ensure that things are aligned.
  • A number of you used readString() to read in the encoding, even though I said there was no whitespace between encoding and value.
• Get me group names by 5pm today!
• You have project proposals due on the last day before break.
• I'm disappointed that so few of you were at today's lunchtime video. While the first half was sleep-inducing, the rest had some interesting points about Java.
• Since bribe day was relatively successful, I'm continuing it again today. I've given a few of you candy before class. This is to indicate that I think you speak sufficiently much in class, and I'd like you to give others a chance today. today.
• Dan presents a case study today.
• Wyatt and Chris present case studies on Friday.
• Questions on the readings?

Huffman Coding

• In case you've forgotten, here's the basic Huffman algorithm

• Start with a set of characters and probabilities. We'll be using this set to make a tree, and then reading the code from the tree.
• Repeat the following steps until you have only one element in the set (only one tree)
  • Locate the two "characters" with the smallest probabilities
  • Replace them by a single "character" whose probability is the same as the sum of the probabilities of those characters.
  • Record what you've done by making a binary tree whose root node is the new "character" and whose children are the two subcharacters.
• Read the encoding off the tree. The code for any character is the path from the root to that character, with 0 representing "left branch" and 1 representing "right branch".
• Is this a valid encoding? Yes. For any sequence of bits, there is a unique decoding of that sequence into characters (the binary nature of the tree helps guarantee this).

An example

• Let's try a simple example of Huffman coding: coding grades.
• (Note that you can use Huffman coding on any alphabet; we're choosing a relatively simple one.)
• Why would you want to code grades? Since each student takes approximately 8 courses per year, and there are approximately 1500 students, there are 12,000 grades to store. While this isn't a lot, storage is tight on the Vax :-)
• If you use ASCII, you're using eight bits (more or less) per grade. Clearly, we can do better.
• What are the grades, and how many are there?
• Simply by numbering, we can use four bits (I think), per grade.
• Do we get an advantage from Huffman coding? Let's try it with some sample probabilities.