Questions tagged [selection-problem]
The selection-problem tag has no summary.
69 questions
0
votes
1
answer
72
views
You are given two unsorted lists $R$ and $C$ of possibly different sizes containing elements from the same universe. Find a Balancing Split
For any value $v$, the list $L$ is split into two sublists $L_{low}$ and $L_{high}$.
$L_{low}$ has all values in $L$ which are less than or equal to $v$.
$L_{high}=L-L_{low}$.
The balancing split is ...
- 118
1
vote
0
answers
40
views
Leader Election: A question about Peterson's Improved Algorithm for Unidirectional Ring
This question refers to Peterson’s improved election algorithm for unidirectional ring:
...
1
vote
0
answers
91
views
merge three ordered sequences with compare-exchange elements
I have been revisiting selection networks with compare-exchange elements (CEs), in particular with K. Cong et al.: "Revisiting Oblivious Top-𝑘 Selection with Applications to Secure 𝑘-NN ...
- 1,194
-1
votes
1
answer
82
views
How is the time complexity of a selection algorithm calculated?
For a selection problem, for example select $k$ smallest items from a list of unsorted array of real numbers, to assess the performance of a algorithm how is the time complexity calculated? Is it ...
- 127
-1
votes
2
answers
125
views
Complexity of a naive implementation for selecting top largest $k$ values from an array
I came up with the following algorithm to select top (largest) $k$ values in an array arr containing $n$ comparable values ($k \le n$):
Initialize an empty array <...
- 127
1
vote
1
answer
247
views
Quick sort with $K-1$ pivots
I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
- 13
2
votes
1
answer
209
views
Faster selection algorithm for small order statistics
SELECT(A,p,r,i) is an algorithm that
partitions $A[p:r]$ around the $i$ th order statistic ie. in the output, we have $l\in A[p:p+i-2]<A[p+i-1]< h\in A[p+i:...
- 225
1
vote
2
answers
292
views
Designing an algorithm to choose the minimum number of sets containing line segments
Let's say we have some distinct sets each containing a number of line segments.
I want to choose the minimum number of sets such that I will obtain a line from 0 to L with the largest gap being X long....
- 111
0
votes
2
answers
358
views
Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity
An accountant in a big firm would like to find the median of the
salaries of all employees. The data they received is a list of size n
containing the tuples $\left\{s_{i\ },f_{i\ }\right\}_{i=1}^{n}$,
...
- 231
2
votes
1
answer
139
views
Find two very frequent items in a given array of comparable items
I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem?
I want to emphasize also that the algorithm must ...
- 285
1
vote
1
answer
90
views
Choose combinations of similar value, without repeating first or second coordinate
Motivation
In a particular board game, players start the game with a country and a special ability. Two players cannot have the same country or the same special ability. Analysis has shown that ...
- 123
0
votes
0
answers
60
views
How to eliminate « a priori » all vectors in a list of vectors whose scalar product with a given vector is zero without calculating the product
How to eliminate « a priori » all vectors in a list of vectors, whose scalar product with a given vector is zero, without actually calculating the product ?
One solution would be to store the ...
- 165
0
votes
1
answer
273
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
...
- 29
1
vote
1
answer
481
views
Find minimum number of points which intersect overlapping arcs
Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving ...
1
vote
2
answers
113
views
Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time
I am looking for a solution for the following problem:
Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.
Consider the following sequence:
$$
3,...
- 113