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

Transversal of matrices [on hold]

Pseudocode too will do the job
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? ...