{"id":26442,"date":"2017-12-20T21:10:24","date_gmt":"2017-12-20T15:40:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26442"},"modified":"2017-12-20T21:10:24","modified_gmt":"2017-12-20T15:40:24","slug":"randomized-algorithms-set-3-12-approximate-median","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/randomized-algorithms-set-3-12-approximate-median\/","title":{"rendered":"Randomized Algorithms | Set 3 (1\/2 Approximate Median)"},"content":{"rendered":"

In this post, a Monte Carlo algorithm is discussed.<\/p>\n

Problem Statement : <\/strong>Given an unsorted array A[] of n numbers and \u03b5 > 0, compute an element whose rank (position in sorted A[]) is in the range [(1 \u2013 \u03b5)n\/2, (1 + \u03b5)n\/2].
\nFor \u00bd Approximate Median Algorithm &epsilom; is 1\/2 => rank should be in the range [n\/4, 3n\/4]\n

We can find k\u2019th smallest element in O(n) expected time<\/a> and O(n) worst case<\/a> time.<\/p>\n

What if we want in less than O(n) time with low probable error allowed?<\/strong>
\nFollowing steps represent an algorithm that is O((Log n) x (Log Log n)) time and produces incorrect result with probability less than or equal to 2\/n2<\/sup>.<\/p>\n

    \n
  1. Randomly choose k elements from the array where k=c log n (c is some constant)<\/li>\n
  2. Insert then into a set.<\/li>\n
  3. Sort elements of the set.<\/li>\n
  4. Return median of the set i.e. (k\/2)th element from the set<\/li>\n<\/ol>\n[ad type=”banner”]\n

    c Programming<\/p>\n

    <\/div> 
    \/* C++ program to find Approximate Median using   1\/2 Approximate Algorithm *\/#include<bits\/stdc++.h>using namespace std; \/\/ This function returns the Approximate Medianint randApproxMedian(int arr[],int n){    \/\/ Declaration for the random number generator    random_device rand_dev;    mt19937 generator(rand_dev());     \/\/ Random number generated will be in the range [0,n-1]    uniform_int_distribution<int> distribution(0, n-1);     if (n==0)        return 0;     int k = 10*log2(n); \/\/ Taking c as 10     \/\/ A set stores unique elements in sorted order    set<int> s;    for (int i=0; i<k; i++)    {        \/\/ Generating a random index        int index = distribution(generator);         \/\/Inserting into the set        s.insert(arr[index]);    }     set<int> ::iterator itr = s.begin();     \/\/ Report the median of the set at k\/2 position    \/\/ Move the itr to k\/2th position    advance(itr, (s.size()\/2) - 1);     \/\/ Return the median    return *itr;} \/\/ Driver method to test above methodint main(){    int arr[] = {1, 3, 2, 4, 5, 6, 8, 7};    int n = sizeof(arr)\/sizeof(int);    printf("Approximate Median is %d\\n",randApproxMedian(arr,n));    return 0}<\/code><\/pre> <\/div>\n
     <\/p>\n
    Time Complexity:<\/strong>
    \nWe use a set provided by the STL in C++. In STL Set, insertion for each element takes O(log k). So for k insertions, time taken is O (k log k).
    \nNow replacing k with c log n
    \n=>O(c log n (log (clog n))) =>O (log n (log log n))<\/p>\n
    How is probability of error less than 2\/n2<\/sup>?<\/strong>
    \nAlgorithm makes an error if the set S has at least k\/2 elements are from the Left Quarter or Right Quarter.<\/p>\n
    \"Randomized<\/p>\n
    It is quite easy to visualize this statement since the median which we report will be (k\/2)th element and if we take k\/2 elements from the left quarter(or right quarter) the median will be from the left quarter (or the right quarter).<\/p>\n[ad type=”banner”]\n
    An array can be divided into 4 quarters each of size n\/4. So P(selecting left quarter) is 1\/4. So what is the probability that at least k\/2 elements are from the Left Quarter or Right Quarter? This probability problem is same as below :<\/p>\n
    Given a coin which gives HEADS with probability 1\/4 and TAILS with 3\/4. The coin is tossed k times. What is the probability that we get at least k\/2 HEADS is less than or equal to?<\/p>\n
    Explanation:<\/b><\/p>\n
    \"Randomized<\/p>\n
    If we put k = c log n for c = 10, we get \r\nP <= (1\/2)2log n<\/sup>\r\nP <= (1\/2)log n2<\/sup>\r\nP <= n-2<\/sup>\r\n<\/pre>\n
    Probability of selecting at least k\/2 elements from the left quarter) <= 1\/n2<\/sup>
    \nProbability of selecting at least k\/2 elements from the left or right quarter) <= 2\/n2<\/sup><\/p>\n
    Therefore algorithm produces incorrect result with probability less that or equal to 2\/n2<\/sup>.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
    Randomized Algorithms | Set 3 (1\/2 Approximate Median)-Randomized Algorithms
    \nRandomly choose k elements from the array where k=c log n (c is some constant)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[78696,78806,78685,78681,78679,78807,78680,78683],"class_list":["post-26442","post","type-post","status-publish","format-standard","hentry","category-coding","tag-application-of-randomized-algorithm","tag-approximate-median-formula","tag-las-vegas-randomized-algorithm","tag-randomized-algorithm-example","tag-randomized-algorithm-in-daa","tag-randomized-algorithms-tutorial","tag-randomized-quicksort-algorithm","tag-types-of-randomized-algorithms"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26442"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26442\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}