Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,851
questions
0
votes
1answer
19 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
13 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 ...
0
votes
1answer
18 views
1
vote
1answer
25 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
28 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
37 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$.
...
-3
votes
0answers
27 views
How can I calculate the time complexity of T(n) = 2T(n-1) - 1 using recursion tree?
I want to know the Time Complexity of this recurrence relation I saw the result is O(1) but I'm a bit confused.
1
vote
1answer
22 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 ...
0
votes
0answers
15 views
question about common prefix of Strings
we are given n Strings of total Length K and also we have m queries about these strings.
each query, contains 2 index ( for example a , b ) and then we should calculate the length of longest common ...
0
votes
1answer
44 views
M + N log N running time for Dijkstra
I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
0
votes
1answer
69 views
Modified Union Find Data Structure
The task is to make data structure with the following operations:
query: takes two arguments s and t and returns true if they are in the same set and false otherwise.
union: takes two arguments s and ...
3
votes
0answers
76 views
Remove a subsequence from a string and append it at the end
Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
0
votes
0answers
49 views
All strings in a range with a given prefix and suffix
Given a decimal number N (which has at most, 10^6 digits, actually we should look at it as a string!) and another decimal number M (which has K digits, 1 <= K <= 10^6 ), we are asked to find all ...
2
votes
1answer
42 views
Alphabetical order under which list of strings is lexicographically sorted
We are given an array of $n$ Strings with total Length $K$, and we are asked to find an alphabetical order (if one exists) with respect to which the array become lexicographically sorted. The time ...
1
vote
1answer
42 views
Splay Tree, repeatedly searching for the same key that´s not in the Tree
In a Splay Tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the Tree. Since the first search has a ...
0
votes
0answers
38 views
General Proof on Potential Method and Amortized Analysis
Let $T$ be an arbitrary data structure for a dynamic set. For every state T of $T$, let $d_t \in \mathbb{N}$. Observe two Operations $O_1, O_2$ on $T$ whose runtimes are proportional to $d_t$ and $...
0
votes
0answers
69 views
Suggest a Data Structure that support the following operations with time complexity O(log(n))
I’m looking for a data structure that supports that store the salaries of it’s employees.
Insert(e) – Insert employee e into the data structure.
AvgDecile(k) – Returns the average salary of the k’th ...
3
votes
1answer
31 views
Algorithm to Compute High Water Mark
I saw this algorithm question which is as below.
There is a server that receives request Ids that are positive integers.
The High Water Mark (HWM) for the server at any instant of time is defined as ...
1
vote
0answers
30 views
A beginner's question on programs that can search and calculate in very large sets
I am not in the computer science field and was looking for some guidance on books/papers/programs that allow me to learn how to design algorithms for problems that involve very large number of ...
0
votes
0answers
17 views
How to efficiently search a list of data structures with filtering support
I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like:
...
0
votes
2answers
58 views
What is a good path for self-study of CS foundations/fundamentals?
I’m a self-taught software engineer who’s been working in industry for 12 years. I don’t have any formal education in CS and math was never my strong suit (although I’m willing to do the work to make ...
1
vote
1answer
43 views
Accounting method - dynamic array
I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1).
I need to compute the time ...
0
votes
1answer
21 views
Can preorder and postorder traversals be used on any type of trees?
I could not find an answer to the question directly by google.
I think this question is rather simple but I am not really sure about it.
Any advice is welcomed.
Thanks
-2
votes
0answers
25 views
Can array list act like tree?
I'm talking about data structures tree, we know that there's parent and children which branching each other.
I feel if we save data to tree is same like multidimensional array.
What am i talking about ...
0
votes
1answer
15 views
Formal Description Of Data Structure For Infinite Sets Of Reals
The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it ...
2
votes
2answers
47 views
What kind of data structure should be used for working with dynamic sets where elements follow “normal distribution” and why?
I am wondering if Hash tables would be a good choice as it mentions dynamic sets to store data which follows normal distribution.
I have doubt in this because normal distribution has bell shaped curve ...
4
votes
1answer
174 views
Randomly selecting element from data structure, probability based on weight
I have a list of elements, each with an id and a weight.
A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as ...
0
votes
1answer
28 views
Sort an array in specific bounds [duplicate]
Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
I will need ...
1
vote
1answer
48 views
Meaning of “number of keys in the range $a$ to $b$” [closed]
Regarding this question:
You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$.
Suggest a data structure that allows to answer in $O(1)$ steps the number of ...
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
2answers
64 views
Find distinict elements in an array in $O(n)$ time
Given this pseudo-code that finds the number of distinct elements in the given array:
...
0
votes
2answers
29 views
Will random function ever hit a hard coded decimal number?
I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages.
But I am curious, will random function ever hits a hard coded decimal number?
I ...
2
votes
0answers
27 views
Finding the longest power subsequence
A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
0
votes
1answer
20 views
Amortized analysis - adding operations to a data structure
One of the finer points of amortized analysis about which I have been able to find relatively little information is the broad question of what happens to the amortized cost of a structure's existing ...
1
vote
1answer
50 views
If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:
Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.
My attempt:
Disproof.
We will exhibit a counterexample:
...
0
votes
1answer
54 views
Translating the in-order index of a node in a complete, balanced binary tree into the level-order index
Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not ...
1
vote
0answers
27 views
Sparse tables as prefix sum data structure
I am trying to understand how a sparse table can be used as a prefix sum data structure for a bit vector. In the screendump below 1 the article [2] very vaguely describes how to use a sparse table ...
0
votes
1answer
28 views
What is the right data structure for MST in a stream
In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:
...
0
votes
0answers
15 views
Propose a family of hash functions with $mod p^2$ for some prime number $p$
I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$.
Now based on a similar example I was thinking of something like:
Given some $a= (a1, a2, ..., ak)∈\{0, ......
0
votes
1answer
46 views
Constructing a crown graph given an independent set
A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:
(a) The set of neighbors of vertices in $C$ is ...
0
votes
0answers
40 views
Multiplication of Upper triangular matrix and Lower triangular matrix
If I have an Upper triangular matrix A and Lower triangular matrix B, what could be the most efficient algorithm to get AxB and BxA.
Also what would be the formula for total number of multiplication ...
0
votes
1answer
27 views
mapping function to map the index of Lower triangular matrix
If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the ...
2
votes
1answer
41 views
How do we pick and switch hash functions from a universal family?
When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like ...
0
votes
0answers
18 views
Time analysis of $m$ search operation in a Splay tree of nodes who have subtrees of size at least $\frac{n}{\log n}$
I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$
The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes.
...
0
votes
0answers
17 views
Hash tables for storing data in an application that supports partial search
Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is?
I would have thought ...
2
votes
1answer
37 views
Proving Quicksort is $O(n^2)$
So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.
I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
1
vote
2answers
89 views
Finding an algorithm to return the $\log n$ largest element in an array
I have just proved that for every $\alpha, \beta>0 : (\log n)^\alpha=O(n^\beta)$.
Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$...
0
votes
1answer
15 views
Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times
I need to find a sorting algorithm to sort an array where the the $k$-th element appears $2^{k-1}$ times in $O(2^k)$.
It also given there are $k$ distinct elements in the array, hence there are $1 + 2 ...
-1
votes
1answer
49 views
Solve the following recurrence
I'm trying to solve this the recurrence :
$$
T(n)=\begin{cases}
1, & \text{ if } n = 1 \\
T(n-1) +n(n-1), & \text{ if } n \geq 2
\end{cases}
$$
1
vote
1answer
53 views
Time complexity of algorithms
I have some questions that I don't understand about time complexity.
Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case
complexity of $A$ is $Ω(g(n))$. It ...
