**Discrete Mathematics and Optimization Seminar**

**Alex Kreinin**

* Algorithmics*

Friday April 23rd at 1.30pm

* McConnell 320*

**Title. *** Lookup Tables, Magic Numbers and Hamiltonian Paths.*

**Abstract. **
We consider the problem of finding lookup tables for a sequence
*a*_{n}=2^{n}. This problem has many applications

in the compiler area. The lookup table is a one-to-one function, mapping
the finite sequence *a*_{n} on to the set of integer

numbers *{0, 1, ..., N-1}*. The technique of fast mapping of the
sequence *a*_{n}=2^{n}, *n=0,1,..., N-1*, where *N=2*^{k}, is

considered in the talk. The algorithm is based on the transformation
that is a composition of the usual integer multiplication

and shift
operator. The problem appeared to be related to the finding Hamiltonian
path in a certain class of graphs.