Thursday, April 15, Volen 101, 2:10-3:10 pm. (Refreshments at 2:00pm)
Huffman coding is a well-known data compression technique in which variable length binary codewords represent each of a set of source symbols so as to minimize average codeword length. The codewords are represented by paths through a binary tree. The Huffman code tree can also be interpreted as the solution to a particular combinatorial search problem: given a set of items, one of which is distinguished in some fashion, conduct a sequence of binary tests to identify this item while employing the minimum average number of tests. In the search tree, the sequence of test results is identified with a path through the tree.
There are many code and search problems like the Huffman problem, but with additional constraints or cost variables imposed or incorporating alternative or secondary performance criteria, which suggest interesting combinatorial optimization problems on weighted trees. In this talk I will describe some open problem variants in both the code and search contexts and present partial results.
Host: Marty Cohn