6.001/Recitation 9

Thoughts on the test

Some things to keep in mind about 6.001 tests:

6.001 tests are anal. For example, on evaluation questions, you need to be as close an approximation to a Scheme interpreter as you can. And never violate any abstractions -- you get 2 points off every time you do.
6.001 tests are devious. Expect trick questions. What's the point of these? Because:
6.001 tests are designed not to have a ceiling effect. A test where everybody scores in the high 90's is a cause for 6.001 staff to mourn, because it doesn't give them any information on who the best students are.

These are some useful procedures for manipulating the representations of objects.

"By representation" means that, for example, different lists with equal values are equal.
"By value" means that equivalent instances of simple values, like numbers and strings, are equal.
"By identity" means that only things with the same location in memory are equal. This equates symbols and identical references to the same list, but not strings, and not even necessarily numbers!

Let's implement compression using [Huffman codes]. Here's what we'll need:

Procedures that can create a representation set of items and pull out the one with the highest value.
A representation of binary trees.
A procedure that counts the frequencies of symbols in a text.
Objects to use as nodes for these trees, which can keep track of symbols and their frequencies.
Procedures that can walk down the Huffman tree to encode and decode text.

This may take longer than this recitation, but bear with me - I think it's useful practice.

Here are some things to generate Huffman trees for, and then encode:

Words with lots of A's
- Alphabet: (A B C D E F G H)
- Text: (B A C A D A E A F A B B A A A G A H)
50's rock songs
- Alphabet: (a boom get job na sha yip wa)
- Text:

(get a job
 sha na na na na na na na na
 get a job
 sha na na na na na na na na
 wah yip yip yip yip yip yip yip yip yip
 sha boom)