<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Uttkarshpatel on Medium]]></title>
        <description><![CDATA[Stories by Uttkarshpatel on Medium]]></description>
        <link>https://medium.com/@uttkarshpatel9?source=rss-e33422dfc565------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*xRRjthfQCP4VVDeL</url>
            <title>Stories by Uttkarshpatel on Medium</title>
            <link>https://medium.com/@uttkarshpatel9?source=rss-e33422dfc565------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 23:36:48 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@uttkarshpatel9/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Randomized Algorithms]]></title>
            <link>https://medium.com/@uttkarshpatel9/randomized-algorithms-d9175c6a330a?source=rss-e33422dfc565------2</link>
            <guid isPermaLink="false">https://medium.com/p/d9175c6a330a</guid>
            <dc:creator><![CDATA[Uttkarshpatel]]></dc:creator>
            <pubDate>Sun, 30 Apr 2023 19:00:18 GMT</pubDate>
            <atom:updated>2023-05-02T20:04:17.285Z</atom:updated>
            <content:encoded><![CDATA[<p>Randomized algorithms are a class of algorithms that make use of randomization to achieve desired outcome. They rely on random inputs or choices during execution to produce a result. Since the execution path cannot be predicted in the beginning, randomization provides an element of unpredictability. This can help algorithms avoid worst case scenarios or find solutions to problems that would be difficult to solve using traditional deterministic algorithms.</p><p>How is randomization better over a deterministic algorithm?</p><p>Let’s look at an example of quick sort. It being a divide and conquer based sorting algorithm ,the idea is that we pick an element as a pivot and put it at its correct position by partitioning the array into two parts, based on the elements lesser or greater than the pivot element and then recursively perform the same steps for each of the partitions until no more can be made.</p><p>The problem with this is that the time complexity of the algorithm is highly dependent on the pivot element we choose. Let’s consider a few cases:</p><p>1.<strong> Choosing the first element as pivot</strong> — There is a serious problem with this. If we pass an already sorted array to a quick sort that chooses the first element as the pivot then it takes n2 time, which is a lot. It is almost equivalent to selection sort.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UoBiVmcK6L6HdLY9fLfkdw.png" /></figure><p>2. <strong>Choosing the last element as pivot</strong> — Performs same as when picking the first element discussed above.</p><p>3. <strong>Choosing the middle element as the pivot</strong> — The worst case of quick sort as we saw above was choosing the first/last element and getting an already sorted array as an input. Choosing the middle element is a bit better in this case, because now the time complexity reduces down to O(n.logn).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/710/1*qTc5kl6A6w3RkwbgGeN6Xg.png" /></figure><p>One thing to note is that choosing a middle element only performs better when the input is sorted. There can be cases where a deliberately created input array can cause it to perform poorly. Choosing a random element in these cases ensures that we will get the output in less time.</p><p>In the randomized version where the pivot is chosen randomly, on a given array, this pivot will split the array randomly, most probably in the middle. Hence we get a near O(n.logn) time complexity. The difference is that with deterministic algorithms, we know and can construct some input that can give the worst case behavior. On the other hand with truly randomized algorithms, no input can always determine whether it will give a worst case behavior. Hence choosing pivots at random gives you a near O(n.logn) time regardless of the characteristics of your input.</p><p>This was one of the areas where randomized algorithms performed better than the existing ones. There are many other areas where they are helpful.</p><p>Randomized algorithms can be divided into two categories: Monte Carlo algorithms and Las Vegas algorithms.</p><h3><strong>Las Vegas Algorithms</strong></h3><p>Las Vegas algorithm is a kind of randomized algorithm which is guaranteed to produce a correct answer when it terminates, but which is not guaranteed to terminate in any fixed time span. The algorithm may use the randomness to speed up the computation. A Las Vegas algorithm always terminates, and may output a symbol that is not a part of the solution, to indicate that it could not find an answer. Las Vegas algorithms are useful in situations where the number of possible solutions is limited, and verifying the correctness of a possible solution is relatively easy while finding a solution is complex.</p><p>To get an intuitive understanding of the algorithm lets see an example of a random point in a circle.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/584/1*y6tLDrSVVPM4UzpmtFFjsA.png" /></figure><p>It’s easy and efficient to compute whether a random point is in a circle or not with the Las Vegas algorithm. Idea is to generate a point (x, y) with <br><em>-1&lt;x&lt;1 </em>and<em> -1&lt;y&lt;1</em>.</p><p>If this point is in the circle we keep it otherwise we discard it. The algorithm does give the correct result but it gambles with the number of calls to the random number generator.</p><p>Example of a Las Vegas algorithms:</p><ul><li>Randomized quick sort</li><li>Randomized greedy eight queens problem</li></ul><h3><strong>Monte Carlo Algorithms</strong></h3><p>Monte Carlo algorithms use randomization to generate an approximate solution that may be incorrect with some probability. They rely on repeated random sampling to compute their results. They are fast but might be wrong in some cases and the output is a random variable.</p><p>To get an intuitive understanding of Monte Carlo algorithms, we can consider a program that approximates the value of π by randomly choosing points within a square.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*XE40BNxr6qXsjWGmhWXXDQ.png" /></figure><p>If the points (x, y) with <em>-1&lt;x&lt;1 </em>and<em> -1&lt;y&lt;1</em> are randomly placed in a square then the ratio of points that lie inside the circle will be close to π/4. Monte Carlo Simulation would randomly place points and use the ratio of the points to approximate the value of π.</p><p>A real life usage of Monte Carlo algorithms is to perform something called Monte Carlo Simulation. It is a technique for estimating a variable which depends on one or more random factors (as opposed to a deterministic variable, which depends only on fixed inputs, from which a fixed value can be calculated). People use Monte Carlo simulations on problems where the answer is either impossible or extremely difficult to obtain, unlike rolling a dice.</p><h4><strong>Applications of Randomized Algorithms</strong></h4><p>Even though randomized algorithms do not provide a complete guarantee of the solution to the problem they are solving when compared to deterministic algorithms, they do ensure that the given solution is correct with a very high probability.</p><p>Few of the applications of randomized algorithms are-</p><ol><li>Equality of strings</li><li>Random Walk</li><li>Matrix Multiplication</li></ol><h4><strong>Equality of strings</strong></h4><p>To understand this problem let’s assume a scenario, Alice maintains a large database of information w. We can assume the database to be a long string. Bob maintains a second copy of the database w’. Periodically they must compare the databases for consistency. Because transmission between Alice and Bob is expensive, they would like to discover the presence of an inconsistency without transmitting the entire database between them. The size of w is typically thousands of terabytes.</p><p>They want to communicate over a secure channel and check if w=w’. How bits do they need to communicate?</p><p>The goal is to minimize the no. of bits communicated. One obvious deterministic strategy is Bob sends the entire database to Alice and Alice checks if it matches The no. of bits communicated are O(n).</p><p>Randomization can help do better and reduce the bits transmitted over the network to O(log n).</p><h4><strong>Random Walks</strong></h4><p>In mathematics, a random walk is a series of steps in a random direction that describe a path. A basic example of this can be the random walk on the integer number line which starts at 0, and at each step it moves +1 or -1 with equal probability. Other examples of random walks include the path traced by a molecule as it travels in a liquid or a gas, Google’s Page ranking algorithm, to simulate the price of fluctuating stock or the financial status of a gambler.</p><p>Page rank algorithm determines how important or useful a website is on the internet for users. This is done by having a surfer that jumps randomly from a website to website. While doing this it maintains a record of how many jumps are made from that page and to that page. Using this it can establish a certain probability of how useful that page is among all the visited pages. One thing to keep in mind is that this is one of the many different parameters that are used to estimate the usefulness of a website for a user.</p><h4><strong>Verifying Matrix Multiplication</strong></h4><p>Freivalds’ algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n✕n matrices A, B and C, the problem is to verify whether A ✕ B = C. A naive algorithm takes O(n3) time to multiply A, B and compare them term by term with C to verify their equality. Freivalds’ algorithm utilizes randomness in order to reduce this time bound to O(k.n2) with a high probability.</p><p><strong>References</strong></p><ol><li><a href="https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/lecture-6-randomization-matrix-multiply-quicksort/">https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/lecture-6-randomization-matrix-multiply-quicksort/</a></li><li><a href="https://brilliant.org/wiki/randomized-algorithms-overview/">https://brilliant.org/wiki/randomized-algorithms-overview/</a></li><li><a href="https://theory.stanford.edu/people/pragh/amstalk.pdf">https://theory.stanford.edu/people/pragh/amstalk.pdf</a></li><li><a href="https://en.wikipedia.org/wiki/Randomized_algorithm">https://en.wikipedia.org/wiki/Randomized_algorithm</a></li><li><a href="https://www.geeksforgeeks.org/implement-quicksort-with-first-element-as-pivot/">https://www.geeksforgeeks.org/implement-quicksort-with-first-element-as-pivot/</a></li><li><a href="https://www.quora.com/How-does-randomized-quick-sort-perform-better-than-the-standard-quick-sort-algorithm-Why-should-anybody-care-about-a-sorting-method-that-is-not-optimal">https://www.quora.com/How-does-randomized-quick-sort-perform-better-than-the-standard-quick-sort-algorithm-Why-should-anybody-care-about-a-sorting-method-that-is-not-optimal</a></li><li><a href="https://en.wikipedia.org/wiki/Las_Vegas_algorithm#:~:text=A%20simple%20example%20is%20randomized,sorted%20array%20as%20an%20output">https://en.wikipedia.org/wiki/Las_Vegas_algorithm#:~:text=A%20simple%20example%20is%20randomized,sorted%20array%20as%20an%20output</a>.</li><li><a href="https://stackoverflow.com/questions/52458876/what-is-a-real-life-example-of-the-las-vegas-algorithm">https://stackoverflow.com/questions/52458876/what-is-a-real-life-example-of-the-las-vegas-algorithm</a></li><li><a href="https://www.geeksforgeeks.org/randomized-algorithms-set-2-classification-and-applications/">https://www.geeksforgeeks.org/randomized-algorithms-set-2-classification-and-applications/</a></li><li><a href="https://yourbasic.org/algorithms/las-vegas/">https://yourbasic.org/algorithms/las-vegas/</a></li><li><a href="https://www.quora.com/What-is-the-Monte-Carlo-Simulation-What-are-some-real-life-examples">https://www.quora.com/What-is-the-Monte-Carlo-Simulation-What-are-some-real-life-examples</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d9175c6a330a" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>