Arrow Research search

Author name cluster

Amr Elmasry

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

MFCS Conference 2013 Conference Paper

In-Place Binary Counters

  • Amr Elmasry
  • Jyrki Katajainen

Abstract We introduce a binary counter that supports increments and decrements in O (1) worst-case time per operation. (We assume that arithmetic operations on an index variable that is stored in one computer word can be performed in O (1) time each.) To represent any integer in the range from 0 to 2 n − 1, our counter uses an array of at most n bits plus few words of \(\lceil \lg (1 + n) \rceil\) bits each. Extended-regular and strictly-regular counters are known to also support increments and decrements in O (1) worst-case time per operation, but the implementation of these counters would require O ( n ) words of extra space, whereas our counter only needs O (1) words of extra space. Compared to other space-efficient counters, which rely on Gray codes, our counter utilizes codes with binary weights allowing for its usage in the construction of efficient data structures.

Details

MFCS Conference 2012 Conference Paper

In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses

  • Jingsen Chen
  • Stefan Edelkamp
  • Amr Elmasry
  • Jyrki Katajainen

Abstract We show how to build a binary heap in-place in linear time by performing ~ 1. 625 n element comparisons, at most ~ 2. 125 n element moves, and ~ n / B cache misses, where n is the size of the input array, B the capacity of the cache line, and ~ f ( n ) approaches f ( n ) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ( n ) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size \(\Theta(\lg n)\) and adjust the heap order at the upper levels using Floyd’s sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.

Details

SODA Conference 2009 Conference Paper

Pairing heaps with O (log log n ) decrease cost

  • Amr Elmasry

We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps. Namely, our heap structure requires O (1) for insert and find-min, O (log n ) for delete-min, and O (log log n ) for decrease-key and meld (all the bounds are in the amortized sense except for find-min).

Details