Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [selection-problem]

The tag has no usage guidance.

4
votes
2answers
48 views

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question: Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and let $ M = \max\{a_0, a_1, .... a_n\} $ and $ m = \min\{a_0, a_1, .... a_n\} $....
0
votes
0answers
22 views

Using Turán's theorem to select two pairs [duplicate]

I have 30 objects , 15 have the color red and 15 have the color blue and function that maps two objects to 1 if the two objects red ,0 other wise. $$f:\{o_1,o_2\dots o_n\} \times \{o_1,o_2\dots o_n\...
1
vote
1answer
20 views

Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold

I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and ...
1
vote
0answers
40 views

Linear Time Selection Algorithm

In the linear time selection algorithm which finds the ith smallest element in O(n) time our first step is to divide our unordered set into subsets of 5. Why is the size of the subsets chosen to be 5 ...
3
votes
1answer
105 views

Median of medians: bound on pivot position

If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at ...
0
votes
2answers
352 views

How is Rank Selection better than Random selection and RWS?

I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does: Tour1's Fitness: 0.87 Tour2's Fitness: 1.22 Tour3's Fitness: 1.03 Tour4's ...
2
votes
1answer
136 views

Median of Medians Recurrence Relation for 3-grouping

So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like $$ T(n) = T(\...
1
vote
1answer
371 views

How to find kth largest element in (max) priority queue in O(k) time

I know there is an a scientific article out there which describes some complicated way of finding the kth smallest element in a min-heap in O(k), but this is for an introductory course on algorithms. ...
1
vote
0answers
96 views

Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
1answer
248 views

Finding median from given range

What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$. The input consists of $L$ lines. Each line consists either of: a) <...
2
votes
2answers
210 views

Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array ...
1
vote
1answer
310 views

Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?...
0
votes
4answers
678 views

Finding the $k$th largest element in an unsorted array

What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of ...
0
votes
2answers
62 views

Finding the half with greatest elements in a set

Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this ...
2
votes
0answers
77 views

Missing assumptions in selection algorithm proof of correctness by contradiction? [duplicate]

Yes, this is homework. I need help knowing how to begin this problem: Let A be an algorithm that finds the kth largest of n elements by a sequence of comparisons. Prove by contradiction that A ...
1
vote
1answer
51 views

Select largest subset, subject to a separate weighting constraint

Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that: $$ maximize\sum_{i=1}^k c_i \\ \sum_{i=1}^k w_i \ge W $$ It seems pretty simple at first. ...
-1
votes
2answers
387 views

How to find the median of 5 elements by rote and its time complexity is O(n)

In the first step, I agree that divide n elements into groups take one pass so the time complexity is $$O(n)$$. But if we need to find the median of each 5 elements, we may have to sort them. I ...
0
votes
0answers
239 views

proof of selection in worst-case linear time

Introduction to Algorithm,3rd 9.3 Selection in worst-case linear time I have a question about its proof. I have selected that sentence. I agree that the number of elements larger than x is $$ ...
6
votes
1answer
823 views

(Nontrivial) Algorithms for finding the third largest element of a set

According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
5
votes
2answers
173 views

Time complexity of a precedence constrained selection problem

I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem) [Assuming operations on integers take O(1) time] We ...
0
votes
1answer
56 views

How to design a top-1 select algorithm to maximize a variable and minimize other variable?

I want to implement an algorithm thats select the best group, which maximize the variable A and minimize the variable B. For instance, I have the following groups: G1 - A = 10 B = 2 G2 - A = 10 B = ...
1
vote
0answers
41 views

Deterministic Selection Median of Medians [duplicate]

As I understand, a quick-select algorithm could use median of medians to find best suited pivot to yield the i-th item in the array, say A. I have referred to Median of Medians algorithm and steps ...
3
votes
1answer
104 views

Deamortizing a Las-Vegas randomized algorithm

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. For example, assuming you need to find the median of an array once every $n$ ...
0
votes
1answer
80 views

Selection algorithm variant for an array

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with. Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys. ...
4
votes
5answers
3k views

Algorithm for finding two smallest numbers in an array

I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like ...
3
votes
1answer
82 views

$k$th Largest Algorithm in a range $[k, k+c]$

The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time. How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $...
0
votes
2answers
2k views

prove that minimal number of comparisons to find median among five elements is 5 [closed]

I would like to prove that we need at least five comparisons to find median amoung five numbers. And my proposition: Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$ ...
2
votes
3answers
577 views

If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]

Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements ...
1
vote
0answers
212 views

Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

There is popular problem: Given that integers are read from a data stream, find the median of elements read so far in an efficient way. One of possible solutions: Use max-heap for left heap (i....
2
votes
2answers
4k views

Finding the median in a heap

Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?
2
votes
0answers
347 views

How to understand the formal analysis of quickselect? [closed]

According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof ...
1
vote
2answers
338 views

Selecting k-1 items that divide a sorted array to k equal parts

Given an unsorted array of $n$ integers, I need to find an $O(n \log k)$ algorithm that finds the $k-1$ items that divide the sorted array to $k$ equal (up to $\pm 1$ items) parts. For example, if $k=...
8
votes
2answers
3k views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
1
vote
0answers
92 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
1
vote
0answers
656 views

Finding the $k$th smallest element in union of two sorted arrays

I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm. What I came up is that, if a[k] < b[k] then the $k$th ...
8
votes
4answers
570 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...
3
votes
1answer
81 views

Returning m greatest elements from k sorted array

We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$. How can we get the $m$ greatest elements in running time $O(k + m\lg k)$? I have tried to use MIN-HEAP size of $...
0
votes
1answer
20 views
0
votes
1answer
943 views

Selection problem on the union of two ordered dictionaries

Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the ...
3
votes
1answer
558 views

Best sort method for median: median heap or insertion sort on a vector

I'm trying to decide between two methods of calculating a median, that will optimize the following operations: Add integer to data structure (insert) Get the median of all integer (getMedian) The ...