We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [ds.data-structures]

Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.

309 questions
Filter by
Sorted by
Tagged with
375 views

### Strongly weight-balanced deterministic skip lists

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as: For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants. They claim: ...
1k views

### Difference lists in functional programming

The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), ...
526 views

### Parallel Dynamic Search

Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ? More generally, what's the best we can do ...
670 views

### Offline multidimensional RMQ/RSQ in query model

Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ) you are given a $d$-dimensional array with $n$ elements, and given a $d$-dimensional box, you wish to determine the max/...
3k views

### 2D Cutting Stock Problem for Glass - Details mentioned

I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm? I am looking for kind of best acceptable solution for 2D ...
347 views

### Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how ...
610 views

### Simple balanced trees with O(1) concat?

In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data ...
It is easy to see that for any $n$ there exists a 1-1 mapping $F$ from {0,1}$^n$ to {0,1}$^{n+O(\log n)}$ such that for any $x$ the vector $F(x)$ is "balanced", i.e., it has equal number of 1s and 0s. ...