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.

Filter by
Sorted by
Tagged with
2
votes
1answer
159 views

Using Yao's principle to find a lower bound

This is a HW question, so I'm not expecting any answers, just a general guidance/help. Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
2
votes
1answer
193 views

Show that RP is closed under concatenation

I'm trying to prove the following problem: Show that $RP$ is closed under concatenation Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
2
votes
2answers
55 views

Limit repetitions in randomized list with each unique element occurring n times

I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row. So with elements [0,1,2] n = ...
2
votes
1answer
504 views

Randomized vs deterministic approach for multiset equality

Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$? Algo 1: Sort $S_1$ and $S_2$ and then check $S_1 = S_2$ Running time : $O(n \log {n})$, where $n$ is the size of the multi ...
2
votes
1answer
47 views

Algorithm to estimate the probability that a “0 and 1 matrix” fills up following the bootstrap percolation rules

Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice). At $t=0$, each site is said "active" independently with a probability $...
2
votes
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, ...
2
votes
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. ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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)$ ...
2
votes
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. ...
2
votes
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 ...
2
votes
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 ...
2
votes
0answers
67 views

Sorting Algorithm: Probability Bound For Randomized Inversion Swapping

Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm. Let $m := 0$. Select a pair $(i, j)$ with $1 \le i < ...
2
votes
0answers
550 views

How much better are conservative updates for count-min sketch?

I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...
2
votes
0answers
149 views

min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
2
votes
0answers
74 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
2
votes
0answers
278 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,...
2
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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.
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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}$ ...
1
vote
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 ...
1
vote
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 ...
1
vote
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, ...
1
vote
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: ...
1
vote
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, ...
1
vote
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 ...
1
vote
1answer
206 views

FFT for expanded form of equation multiplication

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 $...
1
vote
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 ...
1
vote
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 ...
1
vote
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$ ...
1
vote
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,...
1
vote
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)$...
1
vote
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 ...
1
vote
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....
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...

1
4
5
6 7 8