Questions tagged [selection-problem]

The tag has no usage guidance.

41 questions
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\}$....
22 views

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. ...
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 ...
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) <...
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 ...
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?...
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 ...
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 ...
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 ...
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. ...
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 ...
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  ...
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 ...
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 ...
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 = ...
157 views

Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

Here is pseudocode for the algorithm: ...
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 ...
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$ ...
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. ...
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 ...
82 views

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 ...
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 ...
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 ...
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 ...
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 \$...
20 views

Selection type generated by nested loops where initial value is current value of parent loop

Consider the generator of the selections: ...