# DIMACS

*Reconnecting Two Year College Faculty*

to the Mathematical Sciences Enterprise

Series of Two Two-Day Workshops for Two-Year College Teachers

Dates: May 18 & 19, 1998, November 14, 1998 and February 6, 1999

### A G E N D A

*Meals will be served at DIMACS in the 4th floor lounge.*

9:00 - 10:00 Continental breakfast
10:00 - 11:00 Professor Mordecai Golin, Hong Kong University of
Science and Technology
12:00 - 1:00 Lunch
1:00 - 2:00 Group meetings
2:00 - 5:00 Group presentations
5:00 - Dinner

### Mordecai Golin

*Hong Kong University of Science & Technology*

**"Huffman codes and one ended codes"**

__ABSTRACT__

A code is a set of binary words (words built with
"O"s and "1"s). A prefix free code is a code in which
no word is the prefix, or start, of any other word.
Building a low cost prefix-free code is a standard
problem in data compression, called the Huffman problem,
and there is a fast, simple algorithm, the Huffman
algorithm, for doing so.

A new variation of prefix-free codes has recently proven
useful. In this variation every codeword is restricted to
end with the character "1". The problem addressed in this
talk is to develop an algorithm for finding a minimum cost
prefix-free code that satisfies this restriction.

The Huffman algorithm does not work in this case so
our approach will be to go back to first principles and
develop a new algorithm for solving the Huffman Problem.
We will then be able to modify this new algorithm to
work in the restricted case as well.

This is joint work with Chan Sze-Lok.