# Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

361 questions
Filter by
Sorted by
Tagged with
0answers
156 views

### Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
0answers
258 views

### Is important for Fisher–Yates shuffle algorithm to generate random numbers in the sequential increment

This is a follow-up question to the Why shuffling by picking random position in all array instead of a part is not correct. I understand if I pick random numbers from all the range for 4 numbers every ...
0answers
28 views

### Collecting the most Fruit on a Grid

There is a grid of size WIDTH * HEIGHT. X fruits are randomly distributed on the grid. ...
0answers
285 views

### What are randomized algorithms and what are they used for?

I wanted to know what are randomized algorithms and what are some of their uses? When do you think they outperform "standard" algorithms?
0answers
181 views

### Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such ...
1answer
746 views

### Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
1answer
42 views

### Algorithm for random generation of two connected partitions of a finite set [closed]

Given the set $X=\{1,2,\ldots,n\}$; $\,\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers. Please help me to programme an algorithm that realizes random generation of the following two partitions of ...
1answer
142 views

### checking if there're equal bits in binary string [closed]

We have two binary strings, $X$ and $Y$, in two different computers. Both of them in length $n$. The computers can communicate by sending bits to each other. We have to build randomized algorithm to ...
1answer
632 views

### Applying a Chernoff bound with Only an Upper Bound of the Expectation

First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The ...
1answer
1k views

### Can someone explain LazySelect?

The LazySelect algorithm is given in these slides as follows. We have a set $S$ of $n = 2k$ distinct numbers and want to find the $k$th smallest element. Let $R$ be a set of $n^{3/4}$ elements ...
1answer
885 views

### m-element random sample being equally likely …(CLRS 5.3-7)? [closed]

I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed ...