Rajamani Sundar

FOCS Conference 1992 Conference Paper

Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

• Adam L. Buchsbaum
• Rajamani Sundar
• Robert Endre Tarjan

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure. >

FOCS Conference 1991 Conference Paper

A Lower Bound for the Dictionary Problem under a Hashing Model

• Rajamani Sundar

A fundamental open question in data structures concerns the existence of a dictionary data structure that processes the operations in constant amortized time and uses space polynomial in the dictionary size. The complexity of the dictionary problem is studied under a multilevel hashing model that is based on A. C. Yao's (1981) cell probe model, and it is proved that dictionary operations require log-algorithmic amortized time jn this model. The model encompasses many known solutions to the dictionary problem, and the result is the first nontrivial lower bound for the problem in a reasonably general model that takes into account the limited wordsize of memory locations and realistically measures the cost of update operations. This lower bound separates the deterministic and randomized complexities of the problem under this model. >

STOC Conference 1990 Conference Paper

Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences

• Rajamani Sundar
• Robert Endre Tarjan

FOCS Conference 1989 Conference Paper

Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem

• Rajamani Sundar

Nearly tight upper and lower bounds on the maximum number of various rotational operations that can be performed on a binary tree are proved. One of the lower bound results refutes D. E. Sleator's turn conjecture for binary trees (see R. E. Tarjan, SIAM J. Alg. Disc. Meth. , vol. 2, p. 306-318, 1985). The upper bound results are used to derive an inverse Ackerman bound for Tarjan's deque conjecture on the performance of the splay tree. Two new proofs of Tarjan's scanning theorem are provided. One proof generalizes the theorem, whereas the other is a simple, potential-based proof. >