People who code: we want your input. Take the Survey

# 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
1answer
159 views

2answers
460 views

### Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?

I have got some difficulties to solve this algorithm problem. I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, ...
1answer
231 views

### Clock solitaire game and principle of deferred decision

I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. ...
1answer
116 views

### 2D random walk. Should both dimensions be independent?

My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive. What is the correct approach in ...
1answer
41 views

### Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
1answer
21 views

### On efficiency analysis of randomized divide-and-conquer median find

I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort. Here as per book terminology $S$ denotes array of ...
1answer
64 views

### Question on an Algorithm for Longest Increasing Subsequence

I have been reading this paper: https://arxiv.org/abs/2011.10874 This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
0answers
42 views

### Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
1answer
86 views

### Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)

Focusing on the 2D plane: Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. ...
0answers
77 views

### Correctness of Karger's min-cut Algorithm

tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
0answers
15 views

### Best asymptotic randomized multidimensional index?

What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
0answers
67 views

0answers
71 views

### Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
0answers
127 views

### Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect sets ...
2answers
77 views

### Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned". Is shuffling the "free" set after assigning an employee meaningfully more random ...
2answers
2k views

### Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
2answers
913 views

### Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
3answers
124 views

### Finding one of 2/3 of all array elements in constant expected time

How do I go about designing a constant time algorithm which satisfies the following I/O requirements: Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the ...
1answer
1k views

### How to compute Jacobi symbol efficiently?

How do I compute the Jacobi symbol $(N|A)$ efficiently? In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not ...
2answers
169 views

### About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...
1answer
397 views

### Significance of parameters in Tiny Mersenne Twister algorithm

I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ...
1answer
76 views

### derandomize a BPP algorithm

Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running ...
1answer
70 views

### Finding efficient randomized algorithm

I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve. Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ ...
1answer
41 views

### Questions about Randomized Median algorithm?

In textbook by Mitzenmacher and Upfal here, they write in page 62, the following: By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never ...
1answer
66 views

### Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
1answer
67 views

### Coloring a cubic-graph with 2 colors

Given a cubic graph, I want to color its vertices in 2 colors (Say A & B). A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, ...
1answer
82 views

### Most probable value of randomized procedure output

Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure: ...
1answer
94 views

### Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are

I have an array of elements $A = [x_0, x_1, \ldots, x_n]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, ...
1answer
125 views

### Is following observation on Ladner's theorem correct?

Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds? Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is ...
1answer
206 views

I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying? For example, if you are multiplying $... 2answers 2k views ### Seeding the Mersenne Twister Random Number Generator I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I ... 2answers 36 views ### Probability that two specific elements are in uniformly random sample Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4. Essentially we are given a stream of$N$elements and wish to maintain a uniformly random sample,$S$, of size ... 1answer 77 views ### k disjoint triangles with graph splitting to two distinct groups Please note that this question is different than this question. The$k$-disjoint triangles problem is as follows: Input: A graph$G=(V,E)$and an integer$k\in \mathbb{N}$Output: Are there$k$... 1answer 79 views ### can a machine generate truly random numbers? I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However,... 1answer 33 views ### Question in coreset construction fro K-median clustering I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that$A$is an$[α, β]$-bicriteria approximation for K-median clustering for some$α, β=O(1)$... 1answer 186 views ### Efficiently selecting a random subset of size$m$from a set of size$n$This is a cross post of my question here on math.se. I have a list of$n$items and would like to randomly select an$m$set from it efficiently (in terms of time complexity). Also, I want all ... 1answer 154 views ### Randomized Algorithms: High-Probability vs. Expectation Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation.... 1answer 35 views ### Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT In Sections 5.1 of The Design of Approximation Algorithms by Williamson and Shmoys, they describe a basic randomized algorithm for MAX SAT and how to derandomize it. The algorithm is just to assign ... 1answer 38 views ### When does a Monte Carlo algorithm solve a problem? When can we say that a Monte Carlo algorithm solves a problem? To quote from Wikipedia on Monte Carlo algorithms For instance, the Solovay–Strassen primality test is used to determine whether a ... 1answer 35 views ### Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set? Given a set of 10 integers$A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between$1$and$10^{10}$is NOT divisible ... 1answer 93 views ### Color coding to get an FPT algoirthm for$k$disjoint triangles Consider the following problem: Input: A graph$G=(V,E)$and an integer$k \in \mathbb{N}$Output: Are there$k$vertex-disjoint triangles in$G$? Assume we want to use color coding to develop an FPT ... 1answer 132 views ### Why is$ZPP \geq BPP\$ not true?

This seems like a silly question, but I couldn't find a conclusive answer for it. As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or ...