PhD Seminar – Dennis Wong

The School of Computer Science is pleased to announce the following seminar, A Surprisingly Simple de Bruijn Sequence Construction, presented by PhD Student Dennis Wong. The seminar will take place June 18, 2014 in Reynolds 219 at 1:30 pm.

Title

A Surprisingly Simple de Bruijn Sequence Construction

Abstract

A de Bruijn sequence is a cyclic sequence of length 2n where each substring of length n corresponds to a unique string in the set of length n binary strings. The number of unique de Bruijn sequences for a given n is a whopping 2^k, where k=2^n-1-n, however, only a very small number are known to be constructed efficiently and practically (using a polynomial amount of space). This small number of known efficient de Bruijn sequence constructions is perhaps best captured by a quote from Fredericksen from 1982: When a mathematician on the street is presented with the problem of generating a full cycle (de Bruijn sequence), one of the three things happens: he gives up, or produces a sequence based on a primitive polynomial, or produces the prefer-one sequence. Only rarely is a new algorithm pro-posed. In this seminar, we introduce a novel shift-based construction to produce a new de Bruijn sequence.

Advisor: Joseph Sawada