14 citations · 19 across the 3 of their papers we have counts for
3 papers
Insertion Sort is O(n log n)
Michael A. Bender, Martin Farach-Colton, Miguel Mosteiro
Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accele…
Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes
Vicky Choi, Martin Farach-Colton
We propose an assembly algorithm {\sc Barnacle} for sequences generated by the clone-based approach. We illustrate our approach by assembling the human genome. Our novel method aba…
Efficient Tree Layout in a Multilevel Memory Hierarchy
Stephen Alstrup, Michael A. Bender, Erik D. Demaine +3
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed duri…