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
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
vote
0answers
78 views

What is this GlueList Data Structure?

I came across a new list data structure called GlueList that claims faster than classic list implementations. How does it work ? How can it be faster than ArrayList and LinkedList ?
1
vote
0answers
57 views

Find unique vectors by linear algorithm

I was thinking about the homework problem: Given $n$ vectors in 3D: $(\mathbf{v_1},\mathbf{v_2},\dots, \mathbf{v_n})$. Their coordinates are positive integers and less than $10^9$. We should ...
1
vote
0answers
57 views

Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says: Furthermore, the element stored in min does not appear in any of the recursive $vEB( \sqrt[\...
1
vote
0answers
108 views

Any applications that need fast insert or delete for quadtrees?

I know that quadtree could be used in collision detection. But most articles I found are related with quadtree construction and retrieval. I wonder if there are some circumstances which involve both a ...
1
vote
0answers
32 views

Problem occurring when changing hash table size

I'm practicing an exam for a data structures course. There's a question about a hash table with hash function: $$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where $$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k \...
1
vote
0answers
370 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
1
vote
0answers
89 views

Longest increasing subsequence using 2-3 tree

While preparing for my data structures final I came across this problem: A - a given array of integers of length n. Propose data structure which supports the following operations: Init(A) - ...
1
vote
0answers
124 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
1
vote
0answers
177 views

Efficient data structure for set to union of sets mapping

What I have is the following: A mapping $f : key \rightarrow set$ that works in constant time An inefficient mapping $g : \{key\} \rightarrow \cup_{k \in \{key\}} f(k)$ where this union is slow Is ...
1
vote
0answers
112 views

Terminology for a partially unlinked doubly linked list?

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
1
vote
0answers
72 views

Algorithm for the function “drop” in a binary random-access list

In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks: Write a function drop of type ...
1
vote
0answers
67 views

Algorithm for keeping the Maximum and allowing Splits of Strings/sequences

The problem is as follows: Given $k$ strings of size $n$, propose a data structure to support the following operations: Return the maximum of a string. Given an index $i$, and $2$ strings $a$ and $b$...
1
vote
0answers
466 views

Triangle mesh surface area after affine transformation

Let $\mathbb{M}$ be the set of all 3D triangle meshes. Let $a:\mathbb{M} \rightarrow \mathbb{R}$ be a function that computes surface area of the mesh. Let $\mathbb{T}$ be the set of 3D affine ...
1
vote
0answers
164 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
0answers
90 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
1
vote
0answers
44 views

Algorithm for query comparison

Lets say I have a global dataset and I run queries over those data set. For example my dataset would be #id, #Name, #Employee, #Birthdate, #number_of_children 1, Nick, Nasa, 1982, 1 2, Jack, Exon, ...
1
vote
1answer
51 views

How to speed up finding a subset of a given set?

Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data? For example, let's say that I have a collection of sets: ...
1
vote
1answer
182 views

What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss?

The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted ...
0
votes
0answers
6 views

When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?

In what applications would you choose an edge list over an adjacency list or an adjacency matrix? Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph ...
0
votes
0answers
36 views

Which advanced data structure to use?

For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
0
votes
1answer
11 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
0
votes
0answers
11 views

What is the insertion algorithm for an AVL tree with balance constraint of 2?

What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
0
votes
0answers
26 views

Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5). We are asked: "What is the minimal t we can choose?" ($t$ is the minimal degree, in ...
0
votes
1answer
25 views

Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
0
votes
0answers
20 views

Best way to find and store difference between two strings

I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
0
votes
0answers
22 views

What datastructure does google use to store its search engine indexes?

To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for ...
0
votes
0answers
15 views

Alternate Range in Van Emde Boas Tree

DISCLAIMER: I initially asked this question of Stack Overflow but that seems like the wrong place in hindsight so I want to ask here as well since this site is more meant for students and their ...
0
votes
0answers
16 views

How to reconstruct an existing splay tree by insertion?

I'm trying to figure out the same problem as stated in this question. In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
0
votes
0answers
27 views

How to trace Subset from Boolean DP table in the Subset Sum Problem

I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ...
0
votes
0answers
21 views

Benefits of linked lists over forests for disjoint sets

CLRS discusses two specific data structures for disjoint sets: Single linked lists, where each set is represented by a single linked list, and each node has two pointers, one to the list head and ...
0
votes
1answer
21 views

Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

I have some propositions regarding BSTs , please can someone confirm whether they are true or false: Question : 1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$ 2.We wish ...
0
votes
0answers
11 views

parallelized data structure

I'm searching a data structure that supports O(1) concurrent insertions (thread number is known in advance) and iteration over its elements (insertion order doesn't need to be preserved). While one ...
0
votes
0answers
54 views

Monotone priority queues

I'm a little confused about how monotone priority queues work. As far as I understand: A queue is a FIFO data structure A priority queue is a queue where the current element of highest (or lowest) ...
0
votes
0answers
29 views

Is it necessary that Minimum/Maximum Heap must be a Binary Heap?

I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
0
votes
3answers
83 views

Formal definition of the Dynamic Array - what is the Dynamic Array

I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points. ...
0
votes
1answer
203 views

Rank of root in AVL tree

Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree, i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ ...
0
votes
0answers
19 views

What Is The Best Data Structure To Implement Min Priority Queue For Dikstra's Shortest Path Algorithm?

Dikstra's shortest path algorithm uses a min-priority queue for getting the minimum vertex at every iteration. What I want to know is the best data structure to use for this algorithm. From my ...
0
votes
0answers
26 views

Please explain the algorithm for finding bridges in graph?

let, low[] and disc[] be two 1D arrays disc[i] stores the discovery time of node[I] low[i] stores the lowest value between disc[i] and discovery time of children of node[i] I'm curious that what is ...
0
votes
0answers
18 views

How to generate unique keys for different two dimensional matrices having different sizes?

No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
0answers
22 views

Hashfunction for unique character distributions

The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
0
votes
0answers
18 views

Need explanation of Node Structure, Search, Insertion and Deletion operations in R-Trees?

I am finding it hard to visually understand the R-Tree concepts and its primitive operations, Search, Insert and Delete(which are applicable to any type of tree). I am unable to find good sources for ...
0
votes
0answers
13 views

Data structure for revising ordering given a (largely) ordered stream of data

I have an input stream of timestamped data that is largely sorted in ascending order by timestamp. There are occasionally out-of-order elements, at which point I need to do each of the following: ...
0
votes
0answers
13 views

Data Model or Data Structure for Stored Procedures in Databases

I know that Relational Algebra is the goto data model for storing information related to SQL queries. I am however yet to find a standard data model that can encapsulate constructs of stored ...
0
votes
0answers
21 views

Runtime of tree sort algorithm confusion

Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
0
votes
1answer
39 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0
votes
0answers
36 views

Efficient way to convert d-ary to binary heap

Even though a general-purpose algorithm is desired, I'm specifically interested in the case that d is 4 (convert 4-ary to 2-ary).
0
votes
1answer
61 views

How can i solve a recursion equation with square root using recursion tree method?

$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$ I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn. I just don't want to ...
0
votes
0answers
21 views

How do I know which node to do rotation on?

I'm wondering which node do I perform a rotation for on an AVL tree? I think in a single rotation it is always the grandparent of the node causing the imbalance (which could either be the root node ...
0
votes
0answers
42 views

Binary Search Complexity

I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...

1
4
5
6 7 8