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
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

Algorithm to compare two data sets

I have two data sets of a particular structure: ...
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 ...

1
2 3 4 5
36