The classic Hufman Coding Problem of finding a minimum cost prefix-free code is almost completely understood. There still exist many variants of this problem which are not as well understood. In this thesis we consider four variants. The first variant requires that none of the codewords ends with a "1". In the literature, the best algorithm known for finding such codes runs in exponential time. The second variant requires that none of the codewords contains "000" as a substring. In the third variant, the size of the encoding alphabets depends on the position of the alphabets within the codewords. In this thesis we use similar approachs to develop simple dynamic programming algorithms for solving these three problems. The running times are O(n³), O(n⁵) and O(n⁴) respectively. The fourth...[ Read more ]

The classic Hufman Coding Problem of finding a minimum cost prefix-free code is almost completely understood. There still exist many variants of this problem which are not as well understood. In this thesis we consider four variants. The first variant requires that none of the codewords ends with a "1". In the literature, the best algorithm known for finding such codes runs in exponential time. The second variant requires that none of the codewords contains "000" as a substring. In the third variant, the size of the encoding alphabets depends on the position of the alphabets within the codewords. In this thesis we use similar approachs to develop simple dynamic programming algorithms for solving these three problems. The running times are O(n³), O(n⁵) and O(n⁴) respectively. The fourth variant, requires that the difference between the length of the longest codeword and the shortest codeword can be at most L. In this thesis we develop a simple O(nLlogn) algorithm for solving this problem.