Speaker: Jeremy Barbay
University of Chile
Title: Prefix Free Codes in Linear Time
Considering the computation of an *optimal prefix-free code* over n symbols from their frequencies f_1,...,f_n given in arbitrary order, we give a *linear time algorithm* in the *word-RAM memory model* and an (input order oblivious) *instance optimal* algorithm in the *algebraic model*. These complexities improve over both the traditional O(n\lg n) algorithm from Huffman and the O(nk) adaptive algorithm from Belal and Elmasry, where k is the number of distinct code lengths in any optimal code.
**Please note the room change from BA 5256 to PT266