Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

361 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
152 views

Measuring how “balanced” a binary tree is

I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close ...
1
vote
0answers
23 views

How to chose the condition for expand in hash-table?

How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
1
vote
0answers
412 views

Graph data structures - Why is topological sorting so efficient?

Topological sorting on a graph seems like an immensely powerful operation: No matter whether the algorithm ends in success or failure, we obtain an important information about the topology of the ...
1
vote
0answers
16 views

Counting Number of Points Satisfying given Equation

I am given set of points S. I need to find the count of four vertices (A, B, C, D) satsfying the equation AB + CD = BC + AD, morever, the vertices should be pairwise distinct. Here, A, B, C, D ...
1
vote
0answers
71 views

Minimum changes to be made to get Max-flow between each pair of vertices in an undirected graph

I was asked the following problem in an interview: Let M be a N X N matrix, such that: ...
1
vote
0answers
91 views

What is the representation of a tree in a heap called?

Often a binary tree is represented in a particular implicit data structure packed into an array whereby the left and right children of t[x] are found at ...
1
vote
0answers
337 views

Online algorithm to find shortest subarray containing all k-elements

We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each ...
1
vote
0answers
80 views

Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
1
vote
0answers
193 views

Proof of Fenwick Tree's correctness

Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure ...
1
vote
0answers
246 views

Linear probing number of probe sequences

According to Cormen book,number of probe sequences possible in linear probing if hash function is given as $h(k,i) =( h' (k) + i)$ $\text % m $ is m if h'(k) = k modulo 5 and m = 10, then how can ...
1
vote
0answers
71 views

How to select cuckoo filter parameters?

If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?
1
vote
0answers
100 views

why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
1
vote
2answers
8k views

Order of a leaf node in B+ Tree

Going with the definition, that order of a B+ tree is the maximum number of children a node can have. What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node ...
1
vote
0answers
349 views

I'm looking for best algorithms to compare two Circular Linked List?

I'm looking for best algorithms to compare two Circular Linked List? For example : List 1 = 1-3-5 List 2 = 3-5-1 I want to compare "same" or "not same" but need fast algorithm.
1
vote
0answers
61 views

How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure. I somehow do not know how to do ...
1
vote
0answers
24 views

Accounting value of Splay trees?

In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: ...
1
vote
0answers
9 views

Is there a special name for a queue that works with groups of elements

I have a data type that accepts and returns byte arrays. However, the input is from a network callback or loading a huge file in piecemeal and the output is CRLF-terminated lines. The internal storage ...
1
vote
0answers
43 views

Dynamic non-Euclidean closest pair

Given a set $S$ and some symmetric distance function $d(i, j)$ defined over the elements of $S$, we must maintain the closest pair of elements (i.e., $(c_1, c_2) \mid d(c_1, c_2) \leq d(i, j) \forall ...
1
vote
0answers
62 views

combine divergent persistent red-black tree instances

Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent ...
1
vote
0answers
563 views

Algorithms for tabulating/counting/frequency counting?

It is common in data science to receive two equal length vectors (array of dimension 1), say Categories and Weights. We aim to find all unique values of Categories and sum up the corresponding ...
1
vote
0answers
451 views

How to calculate multibit trie storage size?

I wish to use a multi-bit trie structure for storing IPv4 forwarding information with a fixed stride width of 8 bits, I think this is also called a "radix of 8" (so for any IP prefix 4 levels will ...
1
vote
0answers
35 views

Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ ...
1
vote
0answers
101 views

Update and find-smallest-absolute-value operations on a tree

I have a balanced binary tree that stores a number in each node, initially zero. I want to build a data structure that will support the following two operations: Given a vertex $v$ in the tree and a ...
1
vote
0answers
117 views

Advantage of bulkloading in a B-Tree

https://en.wikipedia.org/wiki/B-tree#Initial_construction Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key. In the wiki example the keys are sorted, ...
1
vote
0answers
55 views

amortized analysis

I am trying to find a general solution for the given A,B,C in dynamic arrays. Those veriables presents factors in the following operations : given : c_i the size of the array after operation O_i (...
1
vote
0answers
131 views

Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
1
vote
0answers
58 views

Canonical permutation faster than O(n)

Given a set of permutations $P$ of size $n$, is it possible to create a data structure that, given a sequence $s$, returns $p \cdot s$ where $p \in P$ such that $p \cdot s$ is canonical wrt. $\{\,q \...
1
vote
0answers
334 views

Is the ratio between a bloom filter intersection and a bloom filter union equal to that of their original sets?

Given two sets, S1 and S2, and their corresponding bloom filters, BF1 and BF2, is there a way to prove that |BF1 ∩ BF2|/|BF1 ∪ BF2| = |S1 ∩ S2|/|S1 ∪ S2| (we can assume both bloom filters are ...
1
vote
0answers
547 views

Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
1
vote
0answers
40 views

Naming for (memory near optimal) datastructres

Assume that we wish to solve some problem that has a information theoretic memory lower bound of $\mathcal B$ bits. In computer science, there are a few classes for data structures which are close to ...
1
vote
0answers
36 views

How to store topic-to-topic relationships efficiently and accurately with two huge tables?

I am scanning Wikipedia's DB and retrieving topics (page names, mostly) and their relationships. I want to use it later to create a visual map. A topic table stores the id and the label of each topic....
1
vote
0answers
535 views

Complexity of set oprations in algorithm

I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership). Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone ...
1
vote
0answers
289 views

Trie end-of-word node

I read about TRIE data-structure and is slightly confused about detecting end-of-word. Why do we create another node to detect end-of-word? why cant same node be used it. For example, we have to ...
1
vote
0answers
83 views

Improvement on djikstra's algorithm for shortest paths

We all know about the djikstra's algorithm for computing single source shortest path and the complexity for the same as O(m log n) ( m being the number of edges and n the number of vertices ), this ...
1
vote
0answers
37 views

Why is maximum size of root is 2n + 1 in Splay trees?

In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys and $v$ be a node of $T$. We define $size(v)$ as the number of nodes in the subtree rooted at $...
1
vote
0answers
177 views

Domain Specific Language for Data Structures

Question Does there exist a DSL for describing data structures and their manipulation? I realize that a "normal" programming language describes data structures, but they also do a lot more (e.g. IO)....
1
vote
0answers
82 views

Text on data structures to use along with Lipschutz

I will be teaching a data structures course this Fall semester for second year computer science undergraduates. The textbook and syllabus currently used follow the text "Schaum's outlines: Data ...
1
vote
0answers
232 views

Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
1
vote
0answers
259 views

Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
1
vote
0answers
42 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
1
vote
0answers
170 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
1
vote
0answers
996 views

Can partial sums of a counter array be computed in O(log n) time?

Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A: Add(i, y): Increment the value of $A[i]$ by $y$. PartialSum(k)...
1
vote
0answers
166 views

What data structure is best suited for nested values and count of values?

I have incoming stream of data which has following values. Country, City, State Along with maximum number of unique values to store (e.g. 50,22,12). I need to design a system which will keep count of ...
1
vote
0answers
270 views

Binary Indexed Tree(Fenwick Tree) - Range update and point Query

With the help of TopCoder Tutorial and this post, I was able to understand the basic idea of how basic the cumulative frequency sum is stored in the left subtree of a BIT node.I was successfully able ...
1
vote
0answers
2k views

Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
1
vote
0answers
190 views

why are integers considered as an ADT?

According to the definition of ADT on wikipedia , it is given that ADT is a mathematical model for data types , And as per wikipedia, definition of mathematical model says that it is composed of ...
1
vote
0answers
93 views

Respresting data when I have to move back and forth

I am having data where I would be given customers and there priorities. The priority would be food type and there flavours. In total there are N food type and 2 flavour (spicy and non spicy) so in ...
1
vote
0answers
47 views

Data structure to store a large power-law graph with constantly updated structure

I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights ...
1
vote
0answers
35 views

What is an easy-to-implement linear or non-quadratic suffix array construction algorithm?

The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? ...
1
vote
0answers
64 views

Looking for name of siblings-first-depth-second traversal order

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name. The requirements of the algorithm are: it visits the parent before the children. it visits ...

1 2 3
4
5
8