Unanswered Questions
738 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
12
votes
1
answer
5k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 280k
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
9
votes
0
answers
784
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,058
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
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
CommunityBot
- 1
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
97
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
CommunityBot
- 1
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
6
votes
1
answer
124
views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
- 6,188
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