SELECT with groups of 3

Exercise 9.3-1 asks you to show that the $SELECT$ algorithm still runs in linear time if the elements are divided into groups of 7. This problem asks about dividing into groups of 3.

  • Show that $SELECT$ runs in linear time if you divide the elements into groups whose size is any odd constant greater than 3.
  • Show that $SELECT$ runs in $O(n\; lg\; n)$ time if you divide the elements into groups of size 3

Because the bound in part (b) is just an upper bound, we do not know whether the groups-of-3 strategy actually runs in $O(n)$ time. But by repeating the groups-of-3 idea on the middle groups of medians, we can pick a pivot that guarantees $O(n)$ time. The $SELECT3$ algorithm on the next page determines the $i^{\;th}$ smallest of an input array of $n \gt 1$ distinct elements.

  • Describe in English how the $SELECT3$ algorithm works.Include in your description one or more suitable diagrams.
  • Show that $SELECT3$ runs in $O(n)$ time in the worst case. [1]

 

The worst-case linear-time median-finding algorithm was devised by Blum, Floyd, Pratt, Rivest and Tarjan [2]. This exercise improves the original algorithm [2] to use groups of 3 without deteriorating its performance. The constant factors of this new algorithm $SELECT3$ outperforms that of its counterpart $SELECT$. Therefore, it pays to understand the relative merits of $SELECT3$. What follows is the $SELECT3$ algorithm.

$SELECT3(A, p, r, i)$  
    $\phantom{{}++{}}$ `while` $(r - p + 1)\; mod\; 9 \neq 0$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$  `for` $j = p + 1$ to $r$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $A[p] \gt A[j]$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ exchange $A[p]$ with $A[j]$  

    $\phantom{{}++{}}$ `if` $i == 1$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `return` $A[p]$  
    $\phantom{{}++{}}$ $p = p + 1$  
    $\phantom{{}++{}}$ $i = i - 1$  
    $\phantom{{}++{}}$ $g = \frac{(r - p + 1)}{3}$  
    $\phantom{{}++{}}$  `for` $j = p$ to $p + g - 1$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ sort $\langle A[j],\; A[j + g],\; A[j + 2g]\rangle$  in place  
    $\phantom{{}++{}}$ $g^\prime = \frac{g}{3}$  
    $\phantom{{}++{}}$ `for` $j = p + g$ to $p + g + g^\prime - 1$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ sort $\langle A[j],\; A[j + g^\prime],\; A[j + 2g^\prime]\rangle$  in place  
    $\phantom{{}++{}}$ $x = SELECT3(A, p + 4g^\prime, p + 5g^\prime - 1, \lceil \frac{g^\prime}{2} \rceil)$  
    $\phantom{{}++{}}$ $q = PARTITION-AROUND(A, p, r, x)$  
    $\phantom{{}++{}}$ $k = q - p + 1$    
    $\phantom{{}++{}}$ `if` $i == k$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `return` $A[q]$  
    $\phantom{{}++{}}$ `elseif` $i < k$  
    $\phantom{{}++{}}$ $\phantom{{}++{}}$  `return` $SELECT3(A, p, q - 1, i)$  
    $\phantom{{}++{}}$ `else` `return` $SELECT3(A, q + 1, r, i - k)$   

What follows are our answers to the problem.

  • Let $k$ be the group size and $n$ be the number of elements. 
    Number of groups $g = \frac{n}{k}$ for some odd constant $k$
    Number of elements $\lt$ pivot (or $\gt$ pivot) $\ge \lceil \frac{g}{2}\rceil \times \lceil \frac{k}{2}\rceil = \lceil\frac{\frac{n}{k}}{2}\rceil \times \lceil \frac{k}{2}\rceil$
    Number of elements in low or high side of the partition around x $\ge \frac{n}{2k} \times \frac{k}{2} = \frac{n}{4}$
    Number of elements in play after partition around x $\le n - \frac{n}{4} = \frac{3n}{4}$
    $T(n) \le T(\frac{n}{k}) + T(\frac{3n}{4}) + \Theta(n)$.
    This runs in $\Theta(n)$ time if and only if: $\frac{n}{k} + \frac{3n}{4} \lt n$.
    And this holds for any odd constant $k \gt 4$, thus, proving our claim.

  • For groups of size $3$,
    number of 3 element groups $ = g = \frac{n}{3}$, where n denotes the total number of elements in the input array.
    Number of group medians in the blue region $ = \lceil \frac{g}{2} \rceil$
    For each group median, one additional element is less than it.
    So, the number of elements in the blue region $ \ge \lceil \frac{g}{2} \rceil \times 2 \ge \frac{g}{2} \times 2 = g$
    Thus, total number of elements in play after partition around $x \le n - g = n - \frac{n}{3} = \frac{2n}{3}$   
    What follows is our recurrence for groups of size 3 elements:  $T(n) \le T(\frac{n}{3})\; +\; T(\frac{2n}{3}) + \Theta(n)$
    We will show that, $T(n) = O(n\; log\;n)$ by substitution.
    We'll prove that  $T(n) \le c \cdot n\; \cdot log\;n$ for suitably large constant $c \gt 0$ and all $n \gt 0$
    $T(n) \le c \cdot \frac{n}{3} \cdot log(\frac{n}{3}) + c \cdot \frac{2n}{3} \cdot log(\frac{2n}{3}) + \Theta(n)$
    $T(n) \lt c \cdot \frac{n}{3} \cdot log(n) + c \cdot \frac{2n}{3} \cdot log(n) + \Theta(n)$   
    $T(n) \lt c \cdot n \cdot log(n) + \Theta(n)$
    $T(n) = O(n \; log\; n).$
    Thus, running time of $SELECT$ for groups of 3 elements is: $O(n \cdot log\; n)$

  • In the while loop, from lines 1 to 10, in each iteration we keep the smallest element in A[p], and then find the (i - 1)st smallest element in the subarray A[p + 1: r]. We do it < 9 iterations. The while loop terminates when we have the remaining number of elements which is divisible by 9. Then, we divide these remaining elements into groups of 3 elements each, and sort them in place. Now, all group medians lie in the middle third of A[p:r]. Then, we take the group medians (middle third), and further divide them into 3 element subgroups, sorting them in place as before. All subgroup medians now lie in the middle 9th of A[p:r]. Then we find the pivot x as the median of subgroup medians recursively. The rest is trivial, thus it is not described here. Please see the figure for more details.


  • Number of elements $\lt x$ (or $\gt x$) $ = \lceil \frac{g}{2} \rceil \times 2 \ge g = \frac{n}{3}$
    Number of elements in the blue region $ \ge \frac{n}{3}$
    Thus, total number of elements in play after partition around $x \le n - \frac{n}{3} = \frac{2n}{3}$ 
    The recurrence is therefore given by $T(n) \le T(\frac{n}{9})\; +\; T(\frac{2n}{3})\; +\; \Theta(n)$ 
    Our inductive hypothesis is: $T(n) \le cn$ for some suitably large constant $c \gt 0$ and for all $n \gt 0$ 
    Substituting this in to the right hand side of the recurrence, we then obtain: $T(n) \le \frac{cn}{9} \; +\; \frac{2cn}{3}\; + \Theta(n)$ 
    $T(n) \le \frac{7cn}{9} \;+\; \Theta(n)$ 
    $T(n) \le cn - \frac{2cn}{9} \;+\; \Theta(n)$ 
    $T(n) \le cn$ 
    and this holds if c is chosen large enough that $\frac{2c}{9}$ constant dominates the upper bound constant hidden by the term $\Theta(n)$, thus proving our claim. 
    Thus $SELECT3$ runs in $O(n)$ time in the worst case. 

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour
Read more