Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
0
votes
1answer
25 views
How MO'S algorithm with update query works?
MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing ...
1
vote
1answer
19 views
What is the index of the leftest child of node in a k-nery heap?
Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?
All questions regarding my problem I ...
-1
votes
0answers
18 views
2
votes
1answer
70 views
Generate all permutations of 1 to n with i stacks
Assume we have i stacks. the possible actions are:
push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output
If we have numbers of 1 to n starting from 1 ...
1
vote
1answer
43 views
Given n standard C++ STL maps, can I merge them? [closed]
I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick.
For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}}
Then the ...
1
vote
1answer
32 views
Shortest path in a incomplete graph
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
0
votes
0answers
43 views
On the same group data strcture
In a particular school, $n$ students are taught, and we are given a list of interrelations between students.
The teacher asks the students to divide into a maximum number of groups (on his part, ...
0
votes
0answers
15 views
Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)? [migrated]
The result by Driscoll et al 1989 states
Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) ...
5
votes
1answer
231 views
Data structure for selection of K elements and taking sum
The problem:
We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times:
We can select exactly $Z$ ...
0
votes
0answers
26 views
Choosing algorithms and/or data structures at runtime based on input characteristics
I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
1
vote
2answers
38 views
Check if two separate ranges have some number in common
We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there ...
3
votes
1answer
99 views
Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
0
votes
1answer
34 views
Best known (state of science) time complexity of an array access problem
Consider an Array $A$ with $n$ values and the following operations:
get(i): Returns the value of $A[i]$
insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the ...
2
votes
3answers
360 views
Do height-balanced binary trees have logarithmic depth?
A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.
Given a family of trees such that for every tree $t$ in the family, for every node $...
2
votes
0answers
16 views
Nested dissection vs kd-tree
Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
1
vote
1answer
18 views
Adding an ordered into a relationship without violating the functional dependencies
Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies:
$$A \to C$$
$$A \to B,D$$
is it possible to insert a tuple with $NULL$ values,...
1
vote
1answer
23 views
Find candidate keys given functional dependencies
In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a ...
1
vote
1answer
42 views
How to find highest normal form of a relation, given its functional dependencies
Let's say that I have a relational model, defined as:
$$X(A,B,C,D,E,F,G)$$ with the functional dependencies:
$$f_1: \{A,B,C\} \to \{D,E,F,G\}$$
$$f_2: \{A,B\} \to \{C\}$$
Using this information I ...
0
votes
0answers
17 views
Need an optimized way to handle combination of entities to improve performance
So, I am working on a feature in a web application. The problem is like this-
I have four different entities. Let's say those are - Item1, ...
0
votes
0answers
18 views
Do parent pointers affect path-copying in a persistent binary tree?
I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
1
vote
1answer
38 views
AVL Tree - Print ascending using in-order
Trying to understand how to write proof of correctness.
Searched over the internet on how to write proof of correctness but can't find a good solution for it.
The following sorting algorithm is ...
1
vote
1answer
26 views
Is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node represent?
this book "Fundamentals of Python: Data Structures 1st Edition" says
data items in hierarchical collections are ordered in a structure
resembling an upside-down tree. Each data item except the ...
4
votes
2answers
676 views
How to find sum of maximum K elements in range in array
Recently, I came up to the following problem:
Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum ...
1
vote
1answer
85 views
Shortest Path in Layerwise Complete Graph
Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
3
votes
0answers
35 views
DCEL with dynamic graph
Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely?
I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
0
votes
1answer
22 views
Functional data structure fast to add and unorded deletion
I am looking for a functional data structure that would work in this role.
Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way ...
0
votes
1answer
16 views
Orthogonal range reporting with fixed upper rectangular corner
Consider the following special case of orthogonal range searching:
Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, ...
2
votes
1answer
93 views
Suggest a Data Structure To Manage 2 Sets
I was given the following problem which really baffled me, and I would like some guidance in solving it.
I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
4
votes
0answers
38 views
Best data structure for queries about subsets?
I am interested in finding a data structure that supports the following operations:
Insert Set: Insert a set into the data structure.
Decide Subset: Determine whether a given set is a subset of any ...
1
vote
1answer
28 views
Number of ways of tiling a 3*N board with 2*1 dominoes problem
I came across this problem,
Tiling with Dominoes
and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
1
vote
1answer
53 views
If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?
I am learning the MIT course Introduction to Algorithms.
The professor is saying
In particular, as an example, position 2 is a peak if, and only if, b
greater than or equal to a, and b greater ...
3
votes
1answer
55 views
Fast hash function for set equality
I'm searching an hash function for integer set equality that must be fast.
It must support update (adding an element already in the set must not change the hash) and union.
MinHash has these 2 ...
2
votes
0answers
50 views
Red-black tree trinode restructuring after insertion and deletion
When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively?
My thoughts so far were: after inserting ...
0
votes
1answer
69 views
How to delete an element from a B-tree
There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.
For example, given the following tree, how would we delete 26 and ...
1
vote
1answer
39 views
Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?
I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a ...
2
votes
1answer
181 views
The origin of list data structure
Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
1
vote
3answers
70 views
Why is Binary Heap never unbalanced?
My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
0
votes
1answer
41 views
Which binary search trees have constant time rebalancing time at min/max?
Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or ...
1
vote
1answer
26 views
Priority queue with a buffer for delayed insertion and other tweaks
I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.).
One possible optimisation is to delay insertions ...
3
votes
0answers
46 views
Interesting applications of union-find
I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:
Kruskal's algorithm for MST
Tarjan's off-line ...
1
vote
2answers
128 views
Circular Doubly Linked List find length with single pointer
I have pointer to circular doubly linked list with random values of 0 or 1.
Example: [{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]
I have a single ...
0
votes
0answers
56 views
2-sat and vertex cover [duplicate]
I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of ...
3
votes
1answer
153 views
Data structure with insert, and delete-min (or max) in $O(1)$?
Is it possible to have a data structure that supports both insertion and delete-min (or max) in $O(1)$?
You can assume the numbers that will be inserted are integers in the range [0,n] and that you ...
2
votes
2answers
120 views
Constant factor of an array
In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:
Insertion into a full array can be handled by resizing, i.e.,
allocating a new array with ...
0
votes
0answers
10 views
Determining total of primitive operations and running time for code [duplicate]
i needed some help with these problem in DSA
For the given pseudo code:
...
0
votes
1answer
64 views
Circular Queue using Dynamic Array
I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,
Let capacity be the ...
3
votes
1answer
101 views
Search a sorted array that ends with zeros in O(log n) time
I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted.
If I make a binary search including the 0's I get $O(\log(m))$.
...
0
votes
0answers
25 views
Looking for an esoteric graph theory algorithm
So I'm sure this is an unusual question for this type of site, but I am to give a talk on algorithms for discrete graphs in a few weeks. It has been specified that the talk is to be on some algorithm ...
0
votes
0answers
38 views
Unite a forest if you know each tree's parent
I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively ...
0
votes
0answers
30 views
Red Black Tree Property
Although it may sound trivial...
I was going trough the definitions for Red Black Tree in the book "Introduction to Algorithms" and I still cannot understand, why this is not a RBT?
...
