Register

GO Classes DPP | GATE CS, DA | Algorithms | Selection Algorithms

92 views
2 2 votes

Let, $L=\langle r_1,r_2,\ldots,r_n\rangle$ be an arbitrary list of integers, not necessarily distinct.

Which of the following statements is incorrect?

  1. There exists an optimal deterministic $\Theta(n)$ algorithm for finding the largest element of $L$.
     
  2. The $i$th smallest element can be found using a deterministic $O(n\log n)$ algorithm.
     
  3. If there exists a linear-time algorithm for selecting the $i$th smallest element, then that algorithm can be used to sort the entire list in linear time.
     
  4. The third-largest element can be determined in linear time.
     
  5. The minimum and maximum can both be found during a single traversal of the list.

1 Answer

0 0 votes

A is true. Finding the maximum requires examining the elements, so it can be done in $\Theta(n)$

B is true. One simple method is:

  1. Sort the array in $O(n\log n)$.
     
  2. Return the element at position $i$.

So $O(n\log n)$ is certainly possible.

C is false.

Even if one call to selection takes $O(n)$ that does not mean the whole array can be sorted in $O(n)$.

To obtain all order statistics independently would require many selection operations.

Also, comparison-based sorting has a lower bound of $\Omega(n\log n)$ so a general linear-time comparison sort would contradict that lower bound.

D is true. The three largest elements can be maintained during one scan $O(n)$

E is also true. Minimum and maximum can be tracked simultaneously during one traversal.

 

Answer: C

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
144
144 views
GO Classes asked Aug 24
144 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Consider the following code executed while processing vertex $v$:for each edge e in G.adj(v): w = e.to() if dist[w] dist[v] + e.weight(): dist[w] = dist[v] + e.weight() ...
4 4 votes
1 1 answer
94
94 views
GO Classes asked Aug 24
94 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Trees
Consider the statement:The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.True False
1 1 vote
1 1 answer
116
116 views
GO Classes asked Aug 24
116 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...
2 2 votes
1 1 answer
88
88 views
GO Classes asked Aug 24
88 views
GO Classes DPP | GATE CS, DA | Algorithms | Complexity Analysis
Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...