## May 7, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding

##
Saumi Bandyopadhyay

A SODA paper by Mordecai GOLIN, Xiaoming XU, and Jiajin YU

Abstract:
Given a probability distribution over a set of n words to be
transmitted, the Huffman Coding problem is to find a minimal-cost
prefix
free code for transmitting those words. The basic Huffman coding
problem
can be solved in O(n log n) time but variations are more difficult.
One
of the standard techniques for solving these variations utilizes a
top-down dynamic programming approach.
In this paper we show that this approach is amenable to dynamic
programming speedup techniques, permitting a speedup of an order of
magnitude for many algorithms in the literature for such variations
as
mixed radix, reserved length and one-ended coding. These speedups are
immediate implications of a general structural property that permits
batching together the calculation of many DP entries.