Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,768
questions
0
votes
0answers
34 views
Recommend great books on Data Structures and Algorithms [closed]
Can someone recommend the best books on Data Structures and Algorithms
preferably using C or Python?
0
votes
0answers
27 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
18 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
99 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)$
...
3
votes
1answer
58 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
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 ...
2
votes
1answer
65 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
0answers
19 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 ...
1
vote
1answer
60 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
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
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 ...
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
0answers
74 views
Please help me answer and exaplin this question. A data structure and algorithm question
Imagine $n$ points are distributed independently and uniformly at random on the circumference of a circle that has circumference of length 1. Let the distance between a pair of points on the ...
1
vote
1answer
30 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 ...
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 ...
2
votes
2answers
26 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 ...
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.
...
0
votes
1answer
35 views
Algorithm chalenge: find minimum range to cover all houses with light
N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?
N is an array containing location of each house.
K is ...
2
votes
1answer
51 views
Optimization problem over bidirectional connected graph
A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
1
vote
1answer
33 views
Resources about implementing a database table
I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how ...
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
161 views
Is there another type of list than arraylist and linked-list?
My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.
From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to ...
1
vote
2answers
37 views
Compute average case with best case
is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (...
0
votes
0answers
28 views
Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?
Given a binary search tree(can have any height) .Some nodes its value
changed and violate bst property how we can recover binary search
tree property in-place by just swapping a node with its ...
1
vote
1answer
41 views
Lexicographically Smallest String
Problem Statement: Given a string/pattern only consisting of '<' and '>' symbol, find the lexicographically smallest string that satisfies the pattern(made up of only lowercase english alphabets)...
4
votes
3answers
74 views
Integer set disjointness query on sketches with something like homomorphic hashing
Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
0
votes
0answers
15 views
Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions?
I am trying to find an online/offline tool that can compute the following:
Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation
R = {(a1, a2),(...
0
votes
1answer
34 views
The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?
To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
0
votes
0answers
44 views
Find largest $k$ numbers in Max Heap in $O(n\log k)$
I have a data stream with $n$ numbers and I want to find the largest $k$ of them ($k \ll n$). I want to use a priority queue with max heap of size $k$, so I will have space complexity $O(k)$, which is ...
2
votes
1answer
53 views
Question on an Algorithm for Longest Increasing Subsequence
I have been reading this paper: https://arxiv.org/abs/2011.10874
This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
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 ...
0
votes
1answer
84 views
the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs
Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair.
My attempt
...
1
vote
1answer
24 views
Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?
I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me ...
0
votes
0answers
20 views
What is the state of the art of full text searching across languages?
I have looked at a few papers on this such as this, and it basically says that full text search is all about English with few resources for languages without spaces between words (like Chinese or ...
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 ...
0
votes
1answer
36 views
LinkedList: Remove the kth node form the end
Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
0
votes
1answer
37 views
How to prove that insert complexity in binary search tree is minimum O(log n)?
Is it connected to BST search O(log n) or height log n?
How to prove that insert will give give you correct BST in minimum O(log n) time?
2
votes
3answers
235 views
For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
1
vote
0answers
30 views
efficient DELETE in proto-Van Emde Boas Tree?
TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know ...
0
votes
1answer
43 views
1
vote
0answers
71 views
Trapezoidal Map and Search Tree
i am studying on trapezoidal maps. In the last section, "Analysis" of this paper, it says "The expected query time is indeed O(log n). Again the search structure size can be quadratic ...
0
votes
1answer
31 views
minimum number of points a convex hull must have
Quick question:
Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the ...
2
votes
1answer
105 views
Comparing two algorithms for all-pairs shortest paths
I read in my notes:
If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
0
votes
0answers
35 views
How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)?
How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)
this is part of answer:
my problem is that how do we say the last line?
how do we know ${...
2
votes
1answer
96 views
Number of nodes at given depth in binary tree
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
1
vote
0answers
16 views
Why divide a stack into two parts and store them separately in main-memory and hard-drive a bad idea?
I'm learning data structure and trying to solve problem related to Computer Game like Chess/Go. There is a line in my book on the section of DFS algorithm, which is implemented by two stacks: one for ...
