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.

314 questions
Filter by
Sorted by
Tagged with
22 views

Practical CS courework aimed at data structures/algorithms - experienced professsional [closed]

I am test development engineer who has some experience in C and now works in Java development for Android with Master of Science degree in Electrical Engineering. I would like to obtain a strong ...
87 views

Is there a simple, intuitive explanation for why trees in Fibonacci heaps have the sizes they do?

Fibonacci heaps have a simple rule that ensures its tree sizes grow exponentially with their ranks: A node can lose at most one child. Once that child is lost, the node must be cut from its parent. ...
80 views

Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
82 views

Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
64 views

Data structures for embedded simplicial complexes

I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
73 views

Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
58 views

Data structure for getting all matches of a prefix from a large list of strings [closed]

Suppose I have a very long list of strings (millions of them), ordered by importance. For example: ... barracudas oftwalj velasp offso skenep vitriolic offscre ... ...
42 views

Updating set of lists dependent upon a few indices

I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to ...
65 views

Data structure to report points in the intersection of two circles

The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly. This was solved beautifully ...
335 views

A dynamic data structure to list triangles

Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations? Insert an edge into the graph Delete an edge from the graph Given a query ...
164 views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

I'm following course material from the course Advanced Data Structures. The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which ...
27 views

Splay trees as dynamic weight-balanced trees?

Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows: The ...
93 views

Simple proof that splay trees have the dynamic finger property?

Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ...
449 views

Can three stacks be implemented in one array, with O(1) push/pop time?

Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
83 views

What degree of hash function independence is needed for Bloom filters?

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
102 views

Data structure for radial orderings of points on the plane

Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$. Consider shooting an ...
43 views

163 views

Algorithms in preprocessed universe [closed]

In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...
131 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
620 views

Purely(ish) functional data structure with fast append and forward iteration

I find I have need for a data structure with a specific set of requirements: It represents an immutable sequence of values (fixed sized integers if this matters) Appending a new value to the end (and ...
1k views

Reachability on DAG (best-known algorithm)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, ...
145 views