{"id":26628,"date":"2017-12-21T21:02:10","date_gmt":"2017-12-21T15:32:10","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26628"},"modified":"2017-12-21T21:02:10","modified_gmt":"2017-12-21T15:32:10","slug":"java-programming-randomized-algorithms","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-randomized-algorithms\/","title":{"rendered":"Java Programming – Randomized Algorithms (1\/2) Approximate Median"},"content":{"rendered":"

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>.
\nRandomly choose k elements from the array where k=c log n (c is some constant)
\nInsert then into a set.
\nSort elements of the set.
\nReturn median of the set i.e. (k\/2)th element from the set.<\/p>\n

Java Program<\/span> <\/div> 
\/* Java program to find Approximate Median using   1\/2 Approximate Algorithm *\/import java.util.Iterator;import java.util.Random;import java.util.TreeSet;  class Test{    static int arr[] = new int[]{1, 3, 2, 4, 5, 6, 8, 7} ;         \/\/ This function returns the Approximate Median    static int randApproxMedian(int n)    {        \/\/ Declaration for the random number         Random r = new Random();                 if (n==0)            return 0;                 double k1 = 10*Math.log(n); \/\/ Taking c as 10              int k = (int)k1;                 \/\/ A treeset stores unique elements in sorted order        TreeSet s = new TreeSet<Integer>();        for (int i=0; i<k; i++)        {            \/\/ Generating a random index            \/\/ Random number generated will be in the range [0,n-1]            int index = r.nextInt(n);                  \/\/Inserting into the set            s.add(arr[index]);        }              Iterator<Integer> itr = s.iterator();                 int temp = s.size()\/2 - 1;                 for (int i = 0; i < temp; i++) {            itr.next();        }              \/\/ Return the median        return itr.next();    }      \/\/ Driver method to test the above function    public static void main(String[] args) {             System.out.println("Approximate Median is " + randApproxMedian(arr.length));         }}<\/code><\/pre> <\/div>\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[ad type=”banner”]\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
\"median\"<\/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
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
\"probability\"<\/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":"
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.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,2139,77748],"tags":[70150,70246,79462,77863,78792,78781,70326,79473,79472,79464,79466,74263,73371,70026,79465,79463,79468],"class_list":["post-26628","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-java","category-randomized-algorithms","tag-cormen-solutions","tag-design-analysis-and-algorithm","tag-how-to-write-an-algorithm","tag-java-algorithm-interview-questions","tag-java-programming-exercises-with-solutions-pdf","tag-logical-programming-questions","tag-permutation-and-combination-pdf","tag-permutation-and-combination-problems-with-solutions-pdf","tag-probability-problems-pdf","tag-programming-logic-questions","tag-quicksort-algorithm-in-data-structure-pdf","tag-software-engineer-interview-questions-and-answers","tag-the-worst-case-occur-in-linear-search-algorithm-when","tag-time-complexity-of-binary-search","tag-what-is-an-algorithm","tag-write-an-algorithm","tag-writing-algorithms"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26628","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26628"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26628\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26628"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26628"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26628"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}