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 an=2n. This problem has many applications
in the compiler area. The lookup table is a one-to-one function, mapping the finite sequence an on to the set of integer
numbers {0, 1, ..., N-1}. The technique of fast mapping of the sequence an=2n, n=0,1,..., N-1, where N=2k, 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.