1
$\begingroup$

I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property.

Here is what my professor said about the optimal substructure property:

Let C be an alphabet and x and y characters with the lowest frequency.

Let C' = C-{x,y}U{z} where z.frequency = x.frequency + y.frequency

Let T' (a binary tree) be an optimal prefix code for C' She then drew these pictures enter image description here

Let T be constructed from T' by replacing z with an internal node with children x and y. Then T is an optimal prefix code for C

And I don't really understand what/how this proves anything. All I see that she is doing is like..working backwards. First she replaced x and y with z, and now she is replacing z with x and y. What exactly is this showing? I'm really bad with proofs sometimes so I am just completely lost as to how this showed me anything about anything

$\endgroup$
  • $\begingroup$ What have you tried? We expect you to do a significant amount of self-study before asking. There are lots of textbooks and resources online that explain Huffman coding and prove why the algorithm is correct. Have you tried working through any of them? $\endgroup$ – D.W. Apr 2 '15 at 6:21
  • $\begingroup$ Which textbook are you using? This is covered quite thoroughly in Section 16.3 of CLRS (Cormen, Lieserson, Rivest & Stein). $\endgroup$ – Ken P Apr 2 '15 at 17:52
2
$\begingroup$

Your teacher are proving:

Lemma: If $T'$ is optimal for $C' = C \setminus \{ x, y \} + \{ z \}$, then $T$ is optimal for $C$.

Once you have this lemma, you can prove the correctness of Huffman algorithm by mathematical induction on the cardinality of the alphabet $|C|$.

  • Base Case: The base case of $|C| = 2$ is trivial.
  • Inductive Hypothesis: Suppose Huffman algorithm is correct for any $|C| < n$.
  • Inductive Step: Consider the case of $|C| = n$. According to Huffman algorithm, you reduce the problem to constructing $T'$ on $C'$ where $|C'| = n -1$. By inductive hypothesis, $T'$ is optimal for $C'$. By the lemma above, $T$ is then optimal for $C$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.