Unanswered Questions
488 questions with no upvoted or accepted answers
19
votes
1
answer
1k
views
Why hasn't functional programming researched dynamic trees?
Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
CommunityBot
- 1
11
votes
0
answers
1k
views
Alternative to Bloom filter for extreme parameters
A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).
I am interested in a ...
- 391
8
votes
0
answers
117
views
Data Structures for Non-Orientable Manifolds
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
- 73.1k
8
votes
0
answers
587
views
Predecessor query where the insertion order is known
Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and <...
CommunityBot
- 1
7
votes
0
answers
134
views
Is it possible to efficiently maintain a directed graph where nodes unreachable from the root are deleted?
I have an infinite set of possible nodes $V$ and a "root node" $r \in V$. I would like to maintain a directed graph with the invariant that all nodes in the graph are reachable from $r$. ...
- 195
7
votes
0
answers
353
views
What was the first public reference to bloom filters where the number of hash functions vary?
In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.
This idea is ...
- 529
7
votes
0
answers
1k
views
Double Hashing and Variations for Bloom Filters
I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively
$...
- 113
6
votes
0
answers
380
views
Why most purely functional red-black trees are left-leaning?
Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation?
I've not researched very deeply into this ...
- 203
6
votes
0
answers
327
views
Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)
Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$.
Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
CommunityBot
- 1
5
votes
0
answers
73
views
Data structure that supports adding to evenly spaced indices
I need an array-like data structure that stores integers and supports fast addition to multiple evenly spaced elements on given interval. Formally, if $n$ is length of the array, it has to support ...
D.W.♦
- 167k
5
votes
0
answers
186
views
removing an item from n lists in $O(n^{1-\epsilon})$ amortized time
I have a straightforward task that can be done in $O(n^2)$ time. I'm now wondering if the task can be done in time $O(n^{2-\epsilon})$ if we are allowed to do some pre-processing.
The problem exists ...
- 2,471
5
votes
0
answers
655
views
How to find the Expected height of a randomly built binary tree
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
- 51
5
votes
0
answers
604
views
Data structures for quantum computers
In classical computers we have List,Queue,Tree & etc data structures, since classical computers using 1's & 0's on those data structures. Then what happens when it comes to quantum computers,
...
- 151
5
votes
1
answer
130
views
Can we find the largest intersecting subfamily of convex polygons in quadratic time?
Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
CommunityBot
- 1
5
votes
0
answers
148
views
What is the intuition behind the Geometric Burrows-Wheeler Transform?
What is the intuition behind the Geometric Burrows-Wheeler Transform? And how can I use a GBWT with blocking factor $d$ to match a given pattern $P$ of length $|P| = m$ with
$m \ge d$
$m < d$
...
- 175