# Questions tagged [randomized-algorithms]

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

362 questions
Filter by
Sorted by
Tagged with
1answer
508 views

### How can Karger's algorithm (and other randomized algorithms) be used in practice?

Suppose I am given the following problem (the source is here): Disconnect two nodes in a graph by removing minimum number of edges. I would apply Karger's min-cut algorithm. But how can I ...
2answers
147 views

2answers
256 views

### Guessing the best choice to maximize returns

There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the ...
1answer
45 views

### What is the advantage of probability algorithm?

What is the advantage of probability algorithm? e.g. Las Vegas. I would also like to know some applications of the randomized algorithms. Are there any recommendable courses or books?
2answers
36 views

### Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
1answer
50 views

1answer
57 views

### Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
2answers
741 views

### Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) However, there are different kind of algorithms, such as deterministic, non-...
1answer
173 views

### Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like (1) The algorithm has an expected $O(f(n))$ cost. and (2) With constant probability, the cost is bounded by $O(f(n))$....
1answer
55 views

### 2-Approximation algorithm for for messages across a cyclic network

Question There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
1answer
45 views

### Confusion about the Hiring Problem

I'm confused about where the probability from the hiring problem comes from. For background: We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). ...
1answer
40 views

### If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
1answer
91 views

### Network throughput with random delay selected from uniform distribution

Background: I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the ...
1answer
42 views

### Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...