{"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[pastacode lang=\u201djava\u201d manual=\u201d%2F*%20Java%20program%20to%20find%20Approximate%20Median%20using%0A%20%20%201%2F2%20Approximate%20Algorithm%20*%2F%0Aimport%20java.util.Iterator%3B%0Aimport%20java.util.Random%3B%0Aimport%20java.util.TreeSet%3B%0A%20%0A%20%0Aclass%20Test%0A%7B%0A%20%20%20%20static%20int%20arr%5B%5D%20%3D%20new%20int%5B%5D%7B1%2C%203%2C%202%2C%204%2C%205%2C%206%2C%208%2C%207%7D%20%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20This%20function%20returns%20the%20Approximate%20Median%0A%20%20%20%20static%20int%20randApproxMedian(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Declaration%20for%20the%20random%20number%20%0A%20%20%20%20%20%20%20%20Random%20r%20%3D%20new%20Random()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(n%3D%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20double%20k1%20%3D%2010*Math.log(n)%3B%20%2F%2F%20Taking%20c%20as%2010%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20int%20k%20%3D%20(int)k1%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20A%20treeset%20stores%20unique%20elements%20in%20sorted%20order%0A%20%20%20%20%20%20%20%20TreeSet%20s%20%3D%20new%20TreeSet%3CInteger%3E()%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ck%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Generating%20a%20random%20index%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Random%20number%20generated%20will%20be%20in%20the%20range%20%5B0%2Cn-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20index%20%3D%20r.nextInt(n)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2FInserting%20into%20the%20set%0A%20%20%20%20%20%20%20%20%20%20%20%20s.add(arr%5Bindex%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20itr%20%3D%20s.iterator()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20s.size()%2F2%20-%201%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20temp%3B%20i%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20itr.next()%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Return%20the%20median%0A%20%20%20%20%20%20%20%20return%20itr.next()%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F%2F%20Driver%20method%20to%20test%20the%20above%20function%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Approximate%20Median%20is%20%22%20%2B%20randApproxMedian(arr.length))%3B%0A%20%20%20%20%20%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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=\u201dbanner\u201d]\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=\u201dbanner\u201d]\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}]}}