2022 Developer Survey is open! Take survey.

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
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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)$ ...
user avatar
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 ...
user avatar
  • 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), ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
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: ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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?
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 696

1
3 4 5 6
7