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.

Filter by
Sorted by
Tagged with
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: ...

1
3 4 5 6
7