From markaf@MIT.EDU Fri Mar  7 20:53:06 2003
Date: Fri, 7 Mar 2003 20:46:18 -0500 (EST)
From: Mark Alan Finlayson <markaf@MIT.EDU>
To: 6.050-students@MIT.EDU
Subject: [2.110/6.050] Problem Set #4 graded

Hi Class,

Thank you all for your timely and neat submissions of problem set #4.

The stats are:

Average			8.3
Std Dev			1.8
Maximum			10
Minimum			4
Full Credit Score	10
Maximum Possible	10

There seemed to be some confusion for some students as to the derivation
of the Huffman code.  In Section 5.9 there is an algorithm for the
derivation of the Huffman code, and step 3 was where some students got
confused.  It is important that, of all the symbol sets you have left,
that you take the two with the *lowest probabilities* and combine them;
don't combine the set with the lowest probability with the largest set.
This latter, incorrect method will give you a code like this:

  p     1
  e     01
  space 001
  c     0001
  i     00001
  k     000001
  r     0000001
  d     00000001
  a     000000001
  f     0000000001
  l     00000000001
  o     000000000001
  s     0000000000001
  t     0000000000000

Whereas the correct derivation gives you something like:

  p  	00
  e	01
  space 110
  c  	1000
  i  	1001
  k  	1010
  r  	1011
  d  	11100
  a  	111010
  f  	111011
  l  	111100
  o  	111101
  s  	111110
  t  	111111

You can see that the two are quite different.  In fact the first is
extraordinarily inefficient.

Mark

--------------
Mark Finlayson
Teaching Assistant for 2.110J/6.050J
office: 38-344c
email:  markaf@mit.edu
phone:  617.452.2845
mobile: 617.515.0708