Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,776
questions
0
votes
0answers
27 views
Finding name of a specific problem
Input : $x \in \mathbb Z$ and $a_1,a_2,\dots,a_n \in \mathbb N$.
Output : $b_1,b_2,\dots,b_n \in \mathbb Z$ such that $\sum_{i} a_i b_i=x$ and $\sum_{i}|b_i|$ is minimized.
What's the name of the ...
1
vote
1answer
23 views
A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea: i think because of for any $f:N\rightarrow N$, and $g:...
-1
votes
0answers
13 views
How do I solve the full counting sort problem in HackerRank? [closed]
I tried to look up in the internet and it seems to be hard to understand what's the concept of it. Can someone show me how to do it in java?
0
votes
0answers
8 views
search + filter best data structure
What data structure is best to use to facilitate a text search and a filter (by tag, for example)
Lots of sites support something similar: on StackExchange you can write in the search box
...
1
vote
2answers
51 views
Data structure that allows accessing elements by index and delete them in O(logn)
I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would ...
0
votes
0answers
22 views
Asymptotic bounds of the following operations
I have a very simple question about the best possible big-O bounds for the following data structure:
It starts out empty When you add an element, it is inserted, and the index it was at is associated ...
-2
votes
0answers
18 views
Batch scripting [closed]
I was trying to make a batch script to remove "" from inputed string and provide the string without "" as output and also give the length of that string. This also works fine when ...
0
votes
0answers
49 views
Recommend comprehensive books on Data Structures and Algorithms [closed]
Can someone recommend any comprehensive texts (I welcome what each one of you considers the most useful) on Data Structures and Algorithms? Although Data Structures and Algorithms can generally be ...
1
vote
1answer
39 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 ...
1
vote
1answer
18 views
Is it possible to build regex-based-map with search asymptotically faster then hashmap?
From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to ...
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 ...
1
vote
2answers
145 views
Can someone tell a formal definition for this problem: k-disjoint triangle?
k-disjoint triangle
"We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. "
The above definition is the best ...
0
votes
1answer
20 views
What is the difference between a state machine and a database
I didn't study computer science as a degree, so whilst having studied computer science, there are still gaps in my knowledge. Everything I read about 'state' sounds like some form of 'data' but kept ...
0
votes
2answers
222 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
0answers
24 views
Can you delete-min from fibonacci heap in O(1) amortized?
I just had a data-structures exam. One of the questions asked us to create a data structure which allowed insert operations in O(logn) amortized and delete-max (or min, doesn't matter) in O(1) ...
0
votes
0answers
28 views
When do insertions and deletions get enacted in a buffer tree?
Buffer trees are $(a, b)$-trees in which each node in the tree gets an associated buffer for storing operations to be conducted on elements in the tree. While I appreciate the idea of amortizing the I/...
-1
votes
0answers
20 views
selection problem with a group of log(n)
the formula of selection problem if we divide to 5 elements in every group :
T(n)=T(n/5)+T(7n/10)+O(n)
with a group of 5 elements
if we divide to log(n) elements
I get
T(n)=T(n/log(n))+ ? + O(nlog(log(...
1
vote
2answers
108 views
Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$
I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
...
0
votes
1answer
65 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 ...
3
votes
1answer
8k views
Is a balanced binary tree a complete binary tree?
Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.
All I know is this:
...
3
votes
1answer
61 views
Justifying a claim in the proof of the master theorem
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.
My argument is as follows:
Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
1
vote
0answers
17 views
How to efficiently flatten a hierarchical state machine?
David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "...
1
vote
1answer
68 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 ...
0
votes
1answer
69 views
-1
votes
0answers
22 views
What are R trees? How it works?
I have just read about some data structure which are used rarely, one of them is R trees.
I searched a little about it and found that it is used for spatial search. The Wikipedia page says that it can ...
1
vote
1answer
76 views
What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any ...
4
votes
2answers
2k views
What's the difference between a stream and a queue?
What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'extract'...
2
votes
1answer
66 views
How can I implement a data structure which calculates the number of nested intervals in sub-linear time?
Is there a data structure which can maintain a list of intervals and the following operations?
...
0
votes
1answer
66 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?
1
vote
1answer
115 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
414 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 ...
0
votes
0answers
20 views
Resources on DS and algos
I am new to this forum as I want to explore data structures and algorithms in depth.
I want to know from experts here what books or other resources would be best for someone like me who can be ...
2
votes
1answer
257 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 ...
3
votes
3answers
4k views
Number of binary trees with given height
I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$).
Edit: I forgot to add the ...
4
votes
1answer
39 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
1answer
61 views
Which data structure can be used to determine most experienced person in a shift?
Problem Statement: There are $n$ hours in a day and you have $w$
workers. For each worker $i$ you will be given $x_i$ (work experience),
$s_i$ (shift start time) and $e_i$ (shift end time) on a ...
1
vote
1answer
21 views
Creation of skip list: Las Vegas or Monte Carlo?
I have come across this video on skip lists:
https://www.youtube.com/watch?v=UGaOXaXAM5M
Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm.
But I am ...
4
votes
1answer
64 views
How do 2-3 FingerTrees generalize to bigger branching factors?
FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
-4
votes
0answers
35 views
which algorithm has the worst time complexity in average
a) Shell Sort
b) Insertion Sort
c) Selection Sort
d) Bubble Sort
1
vote
1answer
56 views
facts on tree and MST
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following ...
1
vote
1answer
37 views
Relation between mathematical functions and trees?
I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.
Is there a good way to model a tree in terms of functions?
1
vote
2answers
31 views
Efficiently enumerating all “good” strings given the ability to say whether a partial specification can be good
Suppose that I want to enumerate all English language words of length 5.
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations.
...
1
vote
0answers
28 views
Multiple parameter predicates and the Relational Model
I've got a very general question about the relational model and it's relationship to 1st order predicate calculus. It will probably seem very basic to most, I'm afraid, a consequence of me grappling ...
8
votes
5answers
13k 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
$...
0
votes
0answers
21 views
Packing a sphere with cuboids
This question on the Mathematics SE addresses how to pack a sphere with unit cubes. This addresses how to pack a 2D grid with rectangles.
We can pack a sphere with the minimum number of unit cubes $m$ ...
3
votes
2answers
89 views
High dimensional Pareto dominance query data structure
I have a large (10 million+) set $X$ of data points in some high dimensional $\mathbb{R}^d$ ($d \geq 500$) space. Each data point is quite sparse, e.g. has around $10$ components. Every missing ...
22
votes
9answers
4k views
Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
2
votes
2answers
27 views
What data structure to use for large scale DHCP server
What data structure would one use to keep a large number of IP addresses (v4 and v6, but not at the same time if that makes a difference), and I'm talking about millions, preferably hundreds of ...
0
votes
1answer
185 views
number of ways evaluation of expression such that value not changed [closed]
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
1
vote
0answers
26 views
Binary ā Gray permutation matrix
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
...
