The authors defined $i^{th}$ order statistic of a set of $n$ elements as the $ i^{th} $ smallest element. The $ \lfloor\frac{n+1}{2}\rfloor $ is called lower median and $ \lceil\frac{n+1}{2}\rceil $ is called upper median. The authors then define selection problem as follows:
A set $A$ of $n$ (distinct) numbers and a number $i$, with $ 1 <= i <= n $. The element $ x \in A $ that is larger than exactly $ i-1 $ other elements of $A$. The authors discuss that finding minimum and maximum from a set of $n$ element requires $n-1$ comparisons. The authors also prove that simultaneous finding of maximum and minimum can be done in at most $ 3 \times \lfloor \frac{n}{2} \rfloor $ comparisons. The authors then provide a randomized algorithm
to find $ i^{th} $ order statistic using the quick-sort randomized
partition algorithm. The authors also prove that the algorithm's average running time is $ O(n) $. The authors defined dynamic sets as the sets which change when they are manipulated by algorithms
. The authors then define two kinds of operations on dynamic sets, queries that return information about the set and modifications which change the set as follows:
A set $A$ of $n$ (distinct) numbers and a number $i$, with $ 1 <= i <= n $. The element $ x \in A $ that is larger than exactly $ i-1 $ other elements of $A$. The authors discuss that finding minimum and maximum from a set of $n$ element requires $n-1$ comparisons. The authors also prove that simultaneous finding of maximum and minimum can be done in at most $ 3 \times \lfloor \frac{n}{2} \rfloor $ comparisons. The authors then provide a randomized algorithm
- SEARCH
- INSERT
- DELETE
- MINIMUM
- MAXIMUM
- SUCCESSOR
- PREDECESSOR
No comments:
Post a Comment