Abstract:
The Huffman-Encoding problem of finding a minimum-cost prefix-free code, is a well known and understood one in computer science. It, and the equivalent problem of finding a tree with minimum weighted external path, can be easily solved using an O(n log n) time greedy algorithm.

In this talk we will survey some work on generalizations of the Huffman Coding problem and try to develop tools for handling such generalizations. As examples, we will discuss three different types of generalizations. The first is when the encoding symbols are defined to have unequal costs (lengths). The second is when the number of codewords to be generated is no longer finite but becomes countably infinite. The third requires that all of the codewords generated must obey some external constraint, e.g., they must all belong to a given regular language.

Biography:
After receiving his doctorate from Princeton University in 1990, Dr Golin worked as a researcher in the Project Algorithms of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France. In 1993 he took a position at the Department of Computer Science, the Hong Kong University of Science and Technology, where he is currently an Associate Professor. He has also been a visiting researcher at the Max-Planck-Institut fur Informatik in Saarbrucken, Germany, INRIA-Sophia in France, AT&T Labs-Research, and DIMACS.

Dr Golin's research interests are the theory, design and application of algorithms, computational geometry, information theory and combinatorics.