| |
Yao, Andrew |
 |
|
| |
|
Date Reviewed |
|
 |
|
|
|
| |
1 - 4
of 4 reviews |
|
|
|
|
|
|
| |
Lower bounds for algebraic computation trees with integer inputs
Yao A. (ed) SIAM Journal on Computing 20(4): 655-668, 1991. Type: Article
The problem of deciding whether x ∈ Z n is a member of a scale-invariant and rationally dispersed W ∈ &RR; n has complexity &OHgr; ( ... |
Jul 1 1992 |
|
|
|
|
|
| |
On optimal arrangements of keys with double hashing
Yao A. (ed) Journal of Algorithms 6(2): 253-264, 1985. Type: Article
Given a set of n keys, the keys are arranged in a hash table of size n such that the worst-case retrieval time is minimized. It is shown that, when double hashing is used, one can, with probability 1−o(1)...... |
Jan 1 1986 |
|
|
|
|
|
| |
Uniform hashing is optimal
Yao A. (ed) Journal of the ACM 32(3): 687-693, 1985. Type: Article
Open addressing is a method for constructing hash tables. Under this method, the key of a record maps to a sequence that is a permutation of all the locations of a hash table. A record is inserted in the first free location found by fo...... |
Dec 1 1985 |
|
|
|
|
|
| |
On the expected performance of path compression algorithms
Yao A. (ed) SIAM Journal on Computing 14(1): 129-133, 1985. Type: Article
The average time needed to form unions of disjoint equivalence classes is analyzed for a particular set merging scheme. Starting with n equivalent classes each containing one element, an equivalence instruction asks whether two ...... |
Dec 1 1985 |
|
|
|
|
|
|
|
|
| |
|
|
