Title: Dynamic Programming Speedups in Generic Huffman Coding problems

Speaker:  Xiaomin Xu
Fudan  University

Date: Friday, May 31, 2008
Time 11:00-12:00PM
Venue: Room 3530, HKUST

Abstract:
Given a probability distribution over a set of n words, 
the Huffman Coding problem is to find a minimal-cost 
prefix free code for transmitting/storing  those words. 

The basic Huffman coding problem can be solved in  
O(n log n) time using a simple greedy algorithm.  
This greedy algorithm fail even for slight variations
-- e.g., length-limited,  reserved length, mixed-arity 
coding --  of the original problem.  One standard approach 
towards attacking these variations is to use dynamic 
programming to build optimal coding trees from the top-down.  

 In this talk we show that this generic top-down dynamic 
programming approach is amenible to dynamic programming 
speedup techniques, permitting a speedup of an order of 
magnitude for many existing algorithms in the literature.


This talk is based on joint work with Jiajin Yu and Mordecai Golin