Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,809
questions
0
votes
0answers
11 views
How to Plot Logistic Regression using Seaborn? [closed]
I am trying to plot logistic regression model but seaborn regplot does not worked. What should I do?
1
vote
1answer
27 views
Sort a $d$-sorted array
An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array.
I need to write an algorithm that get a $d$-sorted array of length $n$ and ...
0
votes
0answers
9 views
Using bloom filters for high speed pattern matching in combination with Aho Corasick
I am implementing a new system for pattern matching in Intrusion Detection Systems for streaming data (network packets). I understand that bloom filters also produce false positives. Is there anyway ...
0
votes
0answers
27 views
Spliting in AVL tree in $O(\log n)$ times
Suppose we are given a balanced binary search tree $T$, AVL tree, now
we want split $T$ at a arbitrary node. Can it be done in $O(\log n)$?
First i read following links:
Split in AVL tree with ...
2
votes
1answer
141 views
Weighted binary search tree
Suppose we have binary search tree with $n$ nodes. For each node $u$
we define weight of $u$ is number of nodes in sub tree of $u$ with
$u$. if ratio of weight of each internal node $u$ of right sub ...
-1
votes
0answers
20 views
So just fresh installed windows needing help debloating [closed]
So I’m a noob and have a ? Why does https://www.startpage.com/q=%s return a error on all devices but https://www.startpage.com/q=%20 or 25
0
votes
1answer
28 views
Stack without duplicates
I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during ...
2
votes
1answer
21 views
find the strong component containing the vertex v
I'm trying to solve this question for practising purposes:
"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, ...
2
votes
1answer
36 views
Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?
Given a self-balancing binary search tree of size $n$, I want to perform the following operations:
InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
0
votes
1answer
17 views
Memory allocation of priority queues
So, i faced this question during a pratice quiz
i have no idea why " all of the elements are located contiguously in memory " wrong!!
My logic is that priority queues are made of binary ...
2
votes
1answer
14 views
Structuring a Regression Model for NCAA Basketball Spreads/Totals
I have a basic linear regression model that predicts the spread and total points of NCAA college basketball games. My inputs include various efficiency metrics about each team playing each other. A ...
1
vote
1answer
37 views
For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication
I've recently stumbled upon a problem that I struggle realy hard with ever since.
There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary ...
1
vote
2answers
43 views
Which goes first stl or data structures and algorithms?
So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions.
Is it possible to ...
0
votes
0answers
19 views
What will be the frequency count of this code snippet?
int i=0,j;
while(i<=n)
{
while(j<=(i+1)){
a=a*a;
j++;
}
i++;
This question was in my homework and we have to calculate the frequency count of the ...
2
votes
2answers
54 views
Data structure for interval subset queries
I have a set $S$ of intervals. I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ ...
5
votes
1answer
167 views
Does this data structure already exist?
I was working on a problem for some time now, and I made a data structure to solve it. To my surprise, I could not find any instance of this data structure on the internet (though I am certain someone ...
0
votes
0answers
33 views
Why is LRU cache not implemented using doubly linked list with just two nodes? Do we even need double linked list?
I don't understand why do we need to have more than two nodes in doubly linked list when all we need to maintain is the most recent and least recently accessed nodes.
I was going through solutions for ...
1
vote
0answers
46 views
0/1 Knapsack problem with minimal cost
so i have this problem where:
I have to accomplish a challenge A with n quests. Each quest gives me:
p points and
needs t time to be done.
The object is to complete the challenge A that needs M ...
2
votes
1answer
35 views
Fast algorithm for finding the size of each connected component in a graph of 2D points
I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all ...
2
votes
1answer
18 views
Unification with a list of terms
The problem: we have a list of terms $[t_1, ..., t_n]$ , and a term $t$, and we want to find which of the terms in the list can be unified with $t$. Obviously we can iterate through the list and check ...
0
votes
0answers
13 views
If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?
I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
2
votes
1answer
50 views
A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?
I'm looking for a data structure that supports efficient:
Insertion of arbitrary integers.
Value lookup (given a particular value needle, return true if it's ...
1
vote
1answer
39 views
Finding closest line segment intersecting rays
Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint.
A query would look like this; given a query point $q$ shoot 4 rays from $q$ (...
-1
votes
1answer
42 views
Time complexity of insertion in binary search tree
Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$...
1
vote
0answers
47 views
Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?
Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent ...
0
votes
2answers
42 views
Special case of subset sum in $O(n)$
A sorted array $A[1..n]$ is given. Each element of $A[i]\in \mathbb{N}$, and for each $A[i],A[j]$ we have $A[i]+A[j]\leq n$. Find two elements $A[i], A[j]$ such that $(A[i]-i)+(A[j]-j)=0$. Give a ...
-1
votes
1answer
24 views
Find best value for size of the table in hashing
Given a set of keys $\{i^2|0\leq i\leq 100\}$, and a hash table such that
collision resolve by chaining. Our hash function is $ k \mod m$ .
What is option is best for $m$ to decrease our search for ...
0
votes
0answers
39 views
Finding height of binary search tree
Suppose given a binary search tree $T$ with $n$ nodes with depth $h$.
We did $n$ times search with cost $c_i$ for search $i^{th}$ search on
$T$ ,and $\sum_{i=1}^{n}c_i=O(n\log n)$. what we can say ...
0
votes
1answer
25 views
Search for specific element in sorted array
Given sorted array $A[1..n]$. We want to find an element such that
$A[i]=3i+2$ in $O(\log n)$(binary search).
I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, ...
0
votes
0answers
38 views
A problem in proving with induction
According to
asked question in this post.
Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let $C(n,k)=T(n,k)+1$.
As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$.
I want to prove
$C(n,k)=2\binom{n}{k}$, now on ...
-1
votes
0answers
35 views
Minimally changing string to make it palindromic
Given a string STR of size $N$ and some queries $Q$, find for each query the minimal number of characters which when changed makes that substring a palindrome.
For example: $\mathrm{STR} = aabbdca$.
...
1
vote
1answer
59 views
Solving recurrence relation for running time of combination formula
I'm trying to solve the following Time complexity recurrence relation:
$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$
that come from following code:
...
0
votes
1answer
41 views
Check two balanced binary search trees that sub set of each other
Given two balanced binary search trees $T_1,T_2$. We want to check,
are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have
$n_2$ nodes.
Instructor say it can be done in $O(n_1+n_2)$ ...
1
vote
2answers
101 views
Sort an array that contain two sorted array in $O(n)$
Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and
$C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in
the descending order.
Consider the following example: $B=[...
3
votes
0answers
45 views
How to find the Expected height of a randomly built binary tree
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
1
vote
1answer
96 views
Single-source shortest path problem with diameter
Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and ...
-1
votes
1answer
17 views
largest gcd of an array after a few operations
consider we have n bags of random amounts of coins. given k extra coins, the question is to find the largest gcd that can be ...
1
vote
1answer
40 views
Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$
Given a circle with $n$ equal segments. On each segment there is an
integer. We want select segments at equal distance, maximizing the sum of integers on selected segments.
I have an algorithm with ...
0
votes
0answers
43 views
Counting number of sequences summing to target
This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading:
We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
0answers
19 views
Reordering similar elements together within an array
I have a requirement where I need to group similar elements together within an original list.
For example:
I/P array:
...
0
votes
0answers
89 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.
Main question is, can we ...
1
vote
1answer
36 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:...
0
votes
0answers
12 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
46 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 ...
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 ...
0
votes
1answer
28 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 ...
1
vote
2answers
150 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
0answers
28 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
vote
2answers
183 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)$
...
