K-ary Huffman Tree is Optimal
Yao Ziyuan
We know the construction of a k-ary Huffman tree for Huffman encoding.
The problem is how to prove the k-ary Huffman tree is optimal?
He expects a quick response...
TIA.
Rick Decker
Yao Ziyuan wrote:
Hehe. This friend not only wants someone to do his homework,
but also has the gall to demand that it be produced quickly.
Tell you what, have your friend tell you what he's tried
so far and then post his response here. Since this is a moderate
traffic newsgroup, someone here might post a hint within
a day or two. You report this hint back to your friend
and see if it helps. If it doesn't, ask your friend where
he's stuck then and post his response here. Within a
day or two, you might get a response which, using a
now-familiar process, you'll report back to your friend.
Continue this process until your friend gets the answer.
With any luck, the whole process will terminate within
a few weeks.
Hope this helps,
Rick "grinning as he types"
Yao Ziyuan
sites abroad like Google. However, I gave him this Google result as some
clue:
[PDF] Best Huffman trees
File Format: PDF/Adobe Acrobat
... only binary trees will be considered, since the results in the k-ary
case can be derived in a straightforward manner from the results ...
Best Huffman Trees ... Proof. ...
www.springerlink.com/index/QQ27516521011678.pdf - Similar pages
And he decided to omit the proof in his homework but cite this reference
("Best Huffman Trees") instead... Clever, isn't he?
So actually he doesn't need the proof any more.
gcrh...@yahoo.com
> He in in China's educational network therefore has not direct access
to
> sites abroad like Google. However, I gave him this Google result as
some
> clue:
>
> [PDF] Best Huffman trees
> File Format: PDF/Adobe Acrobat
> ... only binary trees will be considered, since the results in the
k-ary
> case can be derived in a straightforward manner from the results ...
> Best Huffman Trees ... Proof. ...
> www.springerlink.com/index/QQ27516521011678.pdf - Similar pages
>
> And he decided to omit the proof in his homework but cite this
reference
> ("Best Huffman Trees") instead... Clever, isn't he?
>
> So actually he doesn't need the proof any more.
IMO, such an answer is not worth much. The point of the HW is to
get the student to think about and get a better understanding of
huffman trees. Simply citing a reference or copying a proof verbatim
tells me that he doesn't understand the proof; and if he doesn't
understand it, then why should he get credit for it?
Rick Decker
gcrh...@yahoo.com wrote:
> Yao Ziyuan wrote:
>
>>He in in China's educational network therefore has not direct access
>
> to
>
>>sites abroad like Google. However, I gave him this Google result as
>
> some
>
>>clue:
>>
>>[PDF] Best Huffman trees
>>File Format: PDF/Adobe Acrobat
>>... only binary trees will be considered, since the results in the
>
> k-ary
>
>>case can be derived in a straightforward manner from the results ...
>>Best Huffman Trees ... Proof. ...
>>www.springerlink.com/index/QQ27516521011678.pdf - Similar pages
>>
>>And he decided to omit the proof in his homework but cite this
>
> reference
>
>>("Best Huffman Trees") instead... Clever, isn't he?
Arguable. See below.
>>
>>So actually he doesn't need the proof any more.
>
>
> IMO, such an answer is not worth much. The point of the HW is to
> get the student to think about and get a better understanding of
> huffman trees. Simply citing a reference or copying a proof verbatim
> tells me that he doesn't understand the proof; and if he doesn't
> understand it, then why should he get credit for it?
>
I agree, but I recognize as well that my view might be
derive from my American provincialism. For all I know
(and I'd be interested in hearing from people who can speak
with authority on this), this sort of thing might be perfectly
acceptable in Chinese schools. What my feeble attempt at
humor was really getting at was that at least this American
faculty member would find this sort of question completely
unacceptable from one of his students.
Regards,
Rick
Yao Ziyuan
won a silver medal in a recent International Olympiad in Informatics, he
just wanted to save energy and time on it. He was doing his own proof
until I told him that Google result...
Yao Ziyuan
student.