Skip to main content
7 votes
Accepted

Does Huffman coding always produce shorter codes than the Shannon code?

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample. And if you want a really nice ...
Peter Shor 's user avatar
7 votes
Accepted

Does a given regular language contain an infinite prefix-free subset?

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are ...
Mikhail Rudoy's user avatar
3 votes

Lower bound on the number of objects in the universe

Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure.
kodlu's user avatar
  • 2,070
3 votes
Accepted

Lower bound on prefix code lengths

I'll try to show this, hope I interpreted the question correctly. Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup ...
kodlu's user avatar
  • 2,070
3 votes
Accepted

Prefix free code unbalancing 0 and 1 bits

This answer does not quite answer the question. Rather, it describes a trivial solution and shows that it is close to optimal. FWIW I conjecture that the solution is actually optimal. Let $n$ be ...
Neal Young's user avatar
  • 10.8k
2 votes

Does a given regular language contain an infinite prefix-free subset?

Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots $ and $v_1,\...
xavierm02's user avatar
  • 556
1 vote

Definition of a prefix-free Turing machine

[Second major edit since first posting:] This is a supplement to @CarlMummert's answer, with some slight disagreement or clarification. (He surely knows more than I do in this area, though, so I may ...
Mars's user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible