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
2
votes
1answer
69 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
171 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
27 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
50 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
59 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 ...
0
votes
1answer
87 views

Find the minimum sum of distances between sets of points to a straight line in a plane

Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$) I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal ...
2
votes
1answer
61 views

Given a binary min-heap, find the $k$-th element

I'm given a binary min-heap (implemented with an array) and need to come up with a (simple) efficient (no more than $k$ comparisons) to find the $k$-th minimal element. My attempt was as follows: ...
1
vote
1answer
34 views
1
vote
1answer
70 views

Is there a relationship between visitor pattern and DeMorgan's Law?

Visitor Pattern enables mimicking sum types with product types. Where does the "sum"-iness come from? For example, in OCaml one could define ...
1
vote
1answer
121 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
15 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
1answer
129 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
24 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
2answers
59 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
76 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
20 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 ...
2
votes
1answer
333 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
414 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 ...
-1
votes
1answer
183 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
100 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
262 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
63 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
88 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
222 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
25 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
31 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
78 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
51 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$ (...
0
votes
1answer
91 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
62 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
72 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
41 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
45 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
28 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
39 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
vote
1answer
72 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
58 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
134 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
147 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
142 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
41 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
53 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
28 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
39 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
35 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
50 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
22 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
86 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 2 3
4
5
39