4 papers
cs.DS2026
A Geometric Derivation of the Bitner--Ehrlich--Reingold Loopless Gray Code Algorithm
Andrew Au
The Bitner--Ehrlich--Reingold algorithm generates the binary reflected Gray code with constant work per codeword, using a focus-pointer array. Its compact update is easy to state b…
cs.DS2026
Do We Really Need to Read the Input? An Optimality Proof for Stone Game III
Andrew Au
Stone Game III admits a standard backward dynamic program using time and auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple…
cs.DS2026
A Tight Lower Bound for Cycle Detection in Grid Graphs
Andrew Au
We prove that any algorithm for detecting cycles in an grid graph, where cells are colored and adjacency is defined by matching colors, must read all cells in the…
cs.DS2026
Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
Andrew Au
We prove that any algorithm computing the sum-exclude-self of an unsigned -bit integer array of length under sublinear space must perform two linear passes over the input. M…