Campus Event Calendar
Event Entry
New for: D3
What and Who
A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
Xiaoming Xu
Fudan University, Shanghai
PhD Application Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 16 February 2010
11:10
90 Minutes
E1 4
024
Saarbrücken
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.
Contact
IMRPS-CS Office Team
0681 93 25 225
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Stephanie Jörg, 02/12/2010 11:01 -- Created document.