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.
329
questions
4
votes
2answers
766 views
What are the prospects of research in database field?
I have been working with database management systems, and would like to focus on research in this very area some day.
I was having a look at the various research labs around the world,
...
22
votes
2answers
837 views
Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?
I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
62
votes
10answers
11k views
One Stack, Two Queues
background
Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
14
votes
2answers
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), ...
8
votes
3answers
637 views
Proving skip-lists strongly weight-balanced in expectation
Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor?
In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...
5
votes
1answer
5k views
Is it possible to convert a Max heap to a Min heap in place?
I was just wondering if this was possible?
Surely there maybe some naive methods of doing so, but I was just wondering if someone can suggest efficient ways to do so.
7
votes
3answers
7k views
Split or merge Binary Search Trees in O(log n)
We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.
The element with the largest value in $S_1$ is smaller than the ...
11
votes
1answer
397 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:
...
4
votes
1answer
793 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/...
14
votes
3answers
600 views
Associative hash mixing
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
21
votes
9answers
15k views
What is the recommended software for drawing data structures such as graphs and trees?
When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
13
votes
4answers
807 views
Reference for fundamental theorem on tree rotations
Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:
Let A and B be binary ...
52
votes
2answers
6k views
What are the outstanding questions in purely functional data structures?
This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.
I'll start with two questions I have:
Is there a purely functional set data ...
590
votes
6answers
120k views
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:
IntMap (also invented by ...
4
votes
1answer
4k 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 ...
14
votes
4answers
2k views
Subrange of a Red and Black Tree
While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
9
votes
2answers
355 views
Quick encoding of balanced vectors
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. ...
40
votes
10answers
12k views
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
8
votes
4answers
359 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 ...
33
votes
6answers
9k views
Is there a stable heap?
Is there a priority queue data structure that supports the following operations?
Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum ...
11
votes
2answers
4k views
Any fast algorithm for minimum cost feedback arc set problem?
In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.
If each edge is associated with a weight $w$, the minimum cost ...
22
votes
6answers
1k views
Analogs of compressed sensing
In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
36
votes
8answers
2k views
Higher-order algorithms
Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and ...
54
votes
13answers
3k views
For which algorithms is there a large gap between the theoretical analysis and reality?
Two ways of analyzing the efficiency of an algorithm are
to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.
I wonder if there are known cases where there ...
24
votes
2answers
548 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 ...
372
votes
92answers
111k views
Algorithms from the Book.
Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.
If ...
-6
votes
1answer
6k views
What is the advantage of red/black trees in comparison with unbalanced trees? [closed]
In which situations would I use a red/black tree instead of an unbalanced tree?
12
votes
2answers
653 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 ...
17
votes
1answer
1k views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
