Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 50 Issue 3, May 2003

P. van Beek and R. Dechter's theorem on constraint looseness and local consistency
Yuanlin Zhang, Roland H. C. Yap
Pages: 277-279
DOI: 10.1145/765568.765569

A differential approach to inference in Bayesian networks
Adnan Darwiche
Pages: 280-305
DOI: 10.1145/765568.765570
We present a new approach to inference in Bayesian networks, which is based on representing the network using a polynomial and then retrieving answers to probabilistic queries by evaluating and differentiating the polynomial. The network polynomial...

The height of a random binary search tree
Bruce Reed
Pages: 306-332
DOI: 10.1145/765568.765571
Let Hn be the height of a random binary search tree on n nodes. We show that there exist constants α = 4.311… and β = 1.953… such that E(Hn) = αln n...

An analytic approach to the height of binary search trees II
Michael Drmota
Pages: 333-374
DOI: 10.1145/765568.765572
It is shown that all centralized absolute moments E|HnEHn|α (α ≥ 0) of the height Hn of binary search trees of size n and of...

Algorithms for computing the static single assignment form
Gianfranco Bilardi, Keshav Pingali
Pages: 375-425
DOI: 10.1145/765568.765573
The Static Single Assignment (SSA) form is a program representation used in many optimizing compilers. The key step in converting a program to SSA form is called φ-placement. Many algorithms for φ-placement have been proposed in the...