Evan Sala

Evan Sala

Auto-generated profile, based on publicly available information

Evan Sala

University of Guelph, Ontario, Canada

Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 November 2024 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
ESEvan Sala
Evan Sala
JSJoe Sawada
Joe Sawada
AAAbbas Alhakim
Abbas Alhakim
The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert, Gray, Gurk, and Rubinoff in 1958. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length \(2^{n}\) de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this article, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using \(O(n)\) time per bit and only \(O(n)\) space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.