Questions tagged [data-structures]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
12 views

Applications of Complete Binary Tree?

Wondering what are the real word applications of the Complete binary trees or Almost complete binary trees where the the last level of the tree may not be complete and all nodes in the last level are ...
0
votes
0answers
6 views

Efficient algorithm for finding assignable zones

This is an actual logistics problem I'm facing at work and I'd like an advice on what algorithmic approach is suitable for solving this. I have two data structures: Container and Zone defined as ...
0
votes
0answers
12 views

What is the time complexity of comparing two Merkle trees?

I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would ...
3
votes
1answer
44 views

Observations about the structure of an optimal Binary Search Tree

My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees. I am confused about the following sentences: Consider any subtree of a binary search tree. It must contain ...
-1
votes
0answers
14 views

Tree data structure is for behavior modeling or optimizing operations?

Its little vague question. I am not able to visualize - Tree data structure is used to represent hierarchical entities in real world or is meant to organize data to optimize certain operations like ...
1
vote
1answer
88 views

Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
0
votes
0answers
28 views

Question about AVL properties

Assume that the oil company saves for each person that works in the company a record with its name, its salary, its age and its date of birth. You can assume that no two fields are identical for any ...
0
votes
0answers
8 views

Full analyses of the number of nodes/keys and height of B-Trees

If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases: $i$. The tree is ...
-3
votes
0answers
45 views

What is “the modifiers data structure” [closed]

One of my Client asking me, They need "the modifiers data structure". I need to provide this information to them. I am not sure what they are asking. Could anyone please help me out ...
0
votes
0answers
22 views

Deletion in B Trees

Given a B-Tree that contains the keys $k$ and $2k$, we know the height of the tree will be reduced if we delete the key $k$. Prove or disprove: The height of the tree will also reduce if we remove $2k$...
8
votes
2answers
858 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 ...
2
votes
2answers
2k views

Interval tree: find all intervals containing a given interval

Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...
0
votes
0answers
28 views

Self Organizing List vs Hash Table Preformance

I am wondering what the advantages and disadvantages of a self organizing list are over hash tables. Also, does a self organizing list run faster with a memory access pattern, but the memory access ...
1
vote
2answers
117 views

edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
3
votes
1answer
37 views

edge-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
0
votes
0answers
23 views

Amortized cost depending on the number of operations

Considering a dynamic array that grows by a constant factor $k$ (the new array has $k$ more cells than the last one) each time the array is full which initially has $n$ elements in it. Calculating the ...
0
votes
1answer
135 views

Product Sum of Special Arrays

Can someone please explain why this is correct: ...
3
votes
1answer
30 views

Sum of squares of length of longest common prefix for all pairs in given strings

Given a list of unique strings, how can I find the sum of squares of longest common prefixes length for all pairs? I think a trie will be useful but I'm not sure how to calculate the final result. For ...
0
votes
0answers
34 views

What is the name of this data structure?

I am trying to solve a problem efficiently. The problem is to recurse over a set $\{0,1,\dots,n-1\}$ (as array) in ascending or descending order, while removing or re-adding items in $O(1)$ time. A ...
0
votes
1answer
27 views

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

This seems to be my first ever question :) Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that. I don't ...
3
votes
1answer
18 views

What is the primary reference for the observation/discussion of how neural networks struggle with ambiguous training datasets?

It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same ...
0
votes
0answers
6 views

What algorithms can I use in developing a dental treatment recommendation system?

I'm currently working on my thesis proposal. The goal of the system is to basically recommend which treatment can be used for patients based on their x-ray. So it involves image processing. To be ...
9
votes
7answers
18k views

Why does the formula 2n + 1 find the child node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with $...
2
votes
1answer
153 views

Number of contiguous subsequences summing to a given target

I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$. For ...
1
vote
2answers
34 views

kdtree or balltree supporting insertion/deletion

I'm looking for a data structure to perform nearest-neighbor searches in 3D Euclidean space. I have used kd- and balltrees for this purpose before, but my problem is more sophisticated this time. I'd ...
0
votes
1answer
163 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 ...
-1
votes
1answer
32 views

how to optimise this

Say you are given a matrix $M (A \cdot B)$ when $A$ is the number of rows and $B$ is the number of columns. Now we are free to pick one element from each column. Lets say these elements are $E = \{ ...
0
votes
1answer
46 views

updating n elements in $O(\lg{n})$ time

I need to devise a data structure $S$ with the following functions: BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$ INSERT($S$, $k$) - insert a new element ...
4
votes
1answer
51 views

Can we find the largest intersecting subfamily of convex polygons in quadratic time?

Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
1
vote
0answers
37 views

Sort rows and columns of matrix by permuting

I am trying to sort square matrix of size $N$ by $\textbf{only permuting}$ rows and columns, such that row appear in increasing (left to right) while columns appear in decreasing order (top to bottom)....
6
votes
2answers
3k views

Can a Red Black tree be constructed of only black nodes using RB insert only?

I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I ...
4
votes
1answer
170 views

A formal definition for amortized time

Several (tutoring) students have asked me for a formal definition of amortized time and I've never been able to find one online. All the literature I've found usually outlines the three most common ...
1
vote
1answer
49 views

Running time of a function $P$ calling itself via $P(P(n/2))$

int P(int n) { if (n==1) return 1; else return P(P(n/2)); } How will this function P(P(n/2)) be executed and what ...
2
votes
1answer
3k views

Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
0
votes
2answers
329 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 ...
0
votes
1answer
72 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
0
votes
1answer
25 views

Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal

Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation. In particular, how do I re-triangulate my delaunay triangulations once I introduced holes? But I ...
1
vote
0answers
23 views

What is the relation between data-directed programming and dynamic dispatch?

I was reading SICP and it talks about Data-directed programming. To me is sounds like generating a vtable or a dispatch table explicitly, and then looking up to it explicitly too. The programmer ...
1
vote
1answer
83 views

In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?

See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
1
vote
1answer
31 views

Given an array A and a minimum heap H which of the following are true?

I got this series of questions, each needs to either be proved or disproved (w/ example). If $A$ is sorted in non-descending order, it is a valid minimum heap. If $H$ is represented by $A$, therefore ...
1
vote
1answer
30 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
1
vote
0answers
40 views

Find the median in a full min-heap with at most $\left \lfloor \frac{n}{2} \right \rfloor$ comparisons

I'm thinking to do this recursively using the fact the the left subheap is also a min-heap with its root being the minimum using some variation of Select$\left \lfloor \frac{n}{2} \right \rfloor$. ...
0
votes
1answer
74 views

Priority Queue - When Prioritizing Take Place?

In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first? Or both ways are acceptable?
0
votes
1answer
23 views

Converting Binary Search Tree into Decreasing Ordered Linked List

Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
0
votes
0answers
24 views

How to store large graphs, beyond adjacency lists/matrices?

If space is of primary concern, how could we improve on adjacency matrices and adjacency lists for representing a graph of nodes and undirected edges in memory? Throughout academia we learn adjacency ...
1
vote
1answer
25 views

Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes. As binary search trees have numbers greater than the root node on the ...
2
votes
1answer
132 views

Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
1
vote
1answer
2k views

Why does the formula floor((i-1)/2) find the parent node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with parent ...
2
votes
1answer
273 views

The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...

1
2 3 4 5
38