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
42 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
31 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
639 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
74 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
40 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 "...
2
votes
1answer
87 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
27 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
62 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
46 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 ...
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
43 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
34 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
27 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$ ...
1
vote
1answer
53 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
102 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
88 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
41 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
44 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
55 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
40 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
94 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
171 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
46 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 (...
1
vote
1answer
72 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
102 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
1answer
43 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 ...
2
votes
1answer
91 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
74 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
88 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
29 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 ...
1
vote
1answer
192 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
88 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
2answers
180 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?
3
votes
3answers
394 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
43 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
279 views

Algorithm to compare two data sets

I have two data sets of a particular structure: ...
1
vote
0answers
78 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 ...
1
vote
1answer
92 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
154 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)$, ...
1
vote
1answer
155 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
17 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
vote
1answer
383 views

prove that in binary heap buildheap function does at most 2N-2 comparison

prove that in binary heap buildheap function does at most 2N-2 comparison I don't know how should I prove it I need some hint thanks. buildheap procedure: we have n element and we build a heap at ...
1
vote
1answer
66 views

Using hashing to solve 4-sum problem

The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found: ...
2
votes
1answer
115 views

Matrix chain multiplication recurrence and its solution

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
2
votes
1answer
297 views

Bellman Ford facts and specific question

The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
0
votes
1answer
54 views

MST and some facts via an example

$M$ is an MST of the Weighted Graph - $GR$. Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}. Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}. If $e$ is a edge ...
0
votes
3answers
833 views

What is the difference between directed graph and bidirectional graph?

Is the graph above bidirectional? The image in wikipedia confused me a lot, before I heard about something called as bidirectional graph, I would say the above one a directed graph, but I am not sure ...
0
votes
1answer
115 views

design a strange data structure, is it possible?

I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible? When just find min is important (not removing) there is lots of $O(1)$ ...
1
vote
1answer
24 views

write adt for stack operations

Ok, I dont understand whats the difference between: write code for stack operations and write adt for stack operations? lets say the operation is push() and pop(). So what different code is to be ...
5
votes
1answer
64 views

Mergesort and some claims on comparison

suppose for $n$ elements we using mergesort. each number compared at most $O(\log n)$ = False in average each element compared with $O(\log n)$ elements = True there exist an element compared with $\...

1
3 4
5
6 7
39