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.
331
questions
8
votes
2
answers
807
views
What is the initialization time of a link-cut tree?
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
- 7,558
1
vote
3
answers
390
views
Is there a common mathematical symbology for collections?
Preface: So, it was suggested in 'Programmers' that I ask this over here.
I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to ...
- 21
4
votes
2
answers
793
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,
...
peuuwt
22
votes
2
answers
855
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)$ ...
- 591
63
votes
10
answers
12k
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 ...
- 16.3k
14
votes
2
answers
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), ...
- 2,386
8
votes
3
answers
651
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 ...
- 11k
5
votes
1
answer
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
3
answers
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
1
answer
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:
...
- 11k
4
votes
1
answer
850
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/...
- 1,428
14
votes
3
answers
662
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 ...
- 2,151
22
votes
9
answers
17k
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?
- 323
13
votes
4
answers
833
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 ...
- 2,151
53
votes
2
answers
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 ...
602
votes
6
answers
124k
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 ...
- 8,641
4
votes
1
answer
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 ...
- 157
14
votes
4
answers
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 ...
- 242
9
votes
2
answers
358
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. ...
- 971
40
votes
10
answers
13k
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, ...
Chris
8
votes
4
answers
362
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
6
answers
10k
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 ...
- 22.8k
11
votes
2
answers
5k
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 ...
- 161
22
votes
6
answers
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 ...
- 6,940
38
votes
8
answers
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 ...
- 8,641
54
votes
13
answers
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
2
answers
549
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 ...
- 31.7k
376
votes
92
answers
112k
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
1
answer
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?
- 783
12
votes
2
answers
673
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 ...
- 11k
17
votes
1
answer
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:
...
- 696