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.