{"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=\u201dbanner\u201d]\n

    c Programming<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20C%2B%2B%20program%20to%20find%20Approximate%20Median%20using%0A%20%20%201%2F2%20Approximate%20Algorithm%20*%2F%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20This%20function%20returns%20the%20Approximate%20Median%0Aint%20randApproxMedian(int%20arr%5B%5D%2Cint%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Declaration%20for%20the%20random%20number%20generator%0A%20%20%20%20random_device%20rand_dev%3B%0A%20%20%20%20mt19937%20generator(rand_dev())%3B%0A%20%0A%20%20%20%20%2F%2F%20Random%20number%20generated%20will%20be%20in%20the%20range%20%5B0%2Cn-1%5D%0A%20%20%20%20uniform_int_distribution%3Cint%3E%20distribution(0%2C%20n-1)%3B%0A%20%0A%20%20%20%20if%20(n%3D%3D0)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20int%20k%20%3D%2010*log2(n)%3B%20%2F%2F%20Taking%20c%20as%2010%0A%20%0A%20%20%20%20%2F%2F%20A%20set%20stores%20unique%20elements%20in%20sorted%20order%0A%20%20%20%20set%3Cint%3E%20s%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ck%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Generating%20a%20random%20index%0A%20%20%20%20%20%20%20%20int%20index%20%3D%20distribution(generator)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FInserting%20into%20the%20set%0A%20%20%20%20%20%20%20%20s.insert(arr%5Bindex%5D)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20set%3Cint%3E%20%3A%3Aiterator%20itr%20%3D%20s.begin()%3B%0A%20%0A%20%20%20%20%2F%2F%20Report%20the%20median%20of%20the%20set%20at%20k%2F2%20position%0A%20%20%20%20%2F%2F%20Move%20the%20itr%20to%20k%2F2th%20position%0A%20%20%20%20advance(itr%2C%20(s.size()%2F2)%20-%201)%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20median%0A%20%20%20%20return%20*itr%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20method%20to%20test%20above%20method%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%203%2C%202%2C%204%2C%205%2C%206%2C%208%2C%207%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(int)%3B%0A%20%20%20%20printf(%22Approximate%20Median%20is%20%25d%5Cn%22%2CrandApproxMedian(arr%2Cn))%3B%0A%20%20%20%20return%200%0A%7D%0A%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

    \u00a0<\/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=\u201dbanner\u201d]\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=\u201dbanner\u201d]\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}]}}