2
$\begingroup$

I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument

Statement: A binary tree corresponding to the optimal prefix code is full

Proof: This is easy to prove using an exchange argument. Let $T$ denote the binary tree corresponding to the optimal prefix code, and suppose it contains a node $u$ with exactly one child $v$. Now convert $T$ into a tree $T′$ by replacing node $u$ with $v$. To be precise, we need to distinguish two cases. If $u$ was the root of the tree, we simply delete node $u$ and use $v$ as the root. If $u$ is not the root, let $w$ be the parent of $u$ in T. Now we delete node $u$ and make $v$ be a child of $w$ in place of $u$. This change decreases the number of bits needed to encode any leaf in the subtree rooted at node $u$, and it does not affect other leaves. So the prefix code corresponding to $T′$ has a smaller average number of bits per letter than the prefix code for $T$, contradicting the optimality of $T$.

Number of things I do not understand.

1) I thought in an exchange argument, you assume you have a solution T and an optimal solution $T^{*}$ and you prove that your solution T is no worse than $T^{*}$ implying T is an optimal solution, but they're not doing that here.

2) They also state that they will "convert $T$ into a tree $T'$ by replacing node $u$ with $v$" but they don't assume that $T'$ is an optimal solution. Why?

3) How does contradicting optimality of $T$ prove that "A binary tree corresponding to the optimal prefix code is full"?

$\endgroup$
2
$\begingroup$

What Kleinberg and Tardos show is that given a tree $T$ containing a node with a single child, they can come up with a strictly better tree $T'$, showing that $T$ isn't optimal. Therefore an optimal tree cannot have a node with a single child. Whether this qualifies as an exchange argument or not is not so important.

More generally, the form of the argument is "if X doesn't satisfy P then X is not optimal; hence any optimal X satisfies P". In order to show that X not satisfying P cannot be optimal, they modify X to obtain a better X'. This is a common enough pattern which doesn't usually have a name attached to it.

$\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.