Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take 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
0 votes
1 answer
17 views

Is there an algorithm for mapping two ambiguous and unrelated data sets?

I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets. So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
user avatar
  • 1
2 votes
1 answer
30 views

The universal relation problem in communication complexity

In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the ...
user avatar
1 vote
2 answers
73 views

Are there any freely available resources to study randomized algorithms?

I am a student want to study randomized algorithm. Someone recommend cs271 to me, but it's restricted now. Can someone recomend a good resource to study randomized algorithm, thank you a lot.
user avatar
  • 153
1 vote
0 answers
32 views

Bloom filter creating different arrays from two input sets

Assume a bloom filter that is composed of $H = \{H_1, ..., H_k\}$ hash functions, and uniformly maps elements from an input set $X$ to an array $A$ of size $n$. Let $X_1, X_2$ (not same) be two input ...
user avatar
1 vote
1 answer
50 views

Randomized Algorithm Lemma

Hello I am struggling with proving a lemma, it goes as follows: Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose ...
user avatar
  • 37
2 votes
1 answer
34 views

Question about what exponentially small probability of success means in randomized algorithms

I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and ...
user avatar
1 vote
0 answers
20 views

Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
user avatar
3 votes
1 answer
59 views

How can we prove QuickShuffle uniformly permutes it input array?

I'm studying Algorithms by Jeff Erickson. Consider this exercise from that textbook: Prove that the following algorithm, modeled after quicksort, uniformly permutes its input array, meaning each of ...
user avatar
  • 1
0 votes
0 answers
24 views

Graph with constant edge connectivity that remains connected after edge removals

I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
user avatar
  • 149
1 vote
0 answers
20 views

Counting number of copies of a given tree T in a graph G. Looking for a randomised algorithm which is an FPRAS

I'm looking for a randomised algorithm (specifically an epsilon-delta approximation) which takes as input a graph G, a subgraph T (which is a tree), and outputs an approximation to the total number of ...
user avatar
0 votes
1 answer
19 views

Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?

On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
user avatar
0 votes
1 answer
42 views

Are turing machines & equivalents with infinite sized random programs still turing machines?

Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
user avatar
0 votes
1 answer
54 views

Randomized Algorithm Log-Space Exp-Time

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the ...
user avatar
1 vote
1 answer
107 views

Check Welzl's algorithm time complexity

From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem : ...
user avatar
0 votes
1 answer
54 views

Proving there exists no algorithm that can solve a basic problem

Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof. Problem: Let $S$ be a set of $n$ elements, where $n\geq 2$ is ...
user avatar
  • 105
2 votes
0 answers
36 views

Size of the maximum matching in arbitrary graph

I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $ G $. My claim is that, it is equivalent to find a global min cut on ...
user avatar
  • 149
2 votes
0 answers
38 views

Fastest randomized algorithm for trace distance

Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$. That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a ...
user avatar
  • 227
2 votes
0 answers
52 views

Decision problem solution monte carlo

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
user avatar
0 votes
1 answer
75 views

Bounding this probability in this Monte Carlo algorithm

Let $P$ be a YES-NO decision problem. Let $A$ be an algorithm for deciding on it such that it is correct with probability $4/5$, in both cases (YES an NO). Design an algorithm that is correct with ...
user avatar
1 vote
1 answer
20 views

Modifying the probability of sucess of an algorithm

This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability ...
user avatar
0 votes
0 answers
26 views

Treap use cases

I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct. Some use cases, or small problems showing ...
user avatar
2 votes
0 answers
50 views

Independent Feedback Vertex Set

In Independent Feedback Vertex Set, we are given an undirected graph $G$, and an integer $k \in \mathbb{N}$. The objective is to decide whether there exists a feedback vertex set S of G of size at ...
user avatar
  • 100
0 votes
0 answers
13 views

Is it possible to use a random seed in the form of an integer to uniformly sample items from an array in sublinear time?

For example, given an array of reservation IDs: ...
user avatar
  • 101
4 votes
1 answer
377 views

Is there some kind of expected error margin for my Monte Carlo algorithm?

My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
user avatar
1 vote
1 answer
73 views

Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2

I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, ...
user avatar
  • 143
1 vote
1 answer
29 views

Las Vegas vs Deterministic in one-way communication complexity

I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte ...
user avatar
  • 13
2 votes
1 answer
80 views

Not understanding step in Karger Algorithm: How to simplify a long product

I'm reading a book on Randomized Algorithms by Raghawan and Motwani and I don't understand the algebra/calculus of a step in the analysis of Karger's algorithm(Randomized min-cut). They have the ...
user avatar
1 vote
0 answers
71 views

Finding optimal path for a reproduction problem

Given a finite set of lists with elements ($e_1, e_2,..., e_7$) and $e_i = True, False$. It is possible to create a new list by taking two lists and apply the $\land$ operator on both lists ($e_i$ in ...
user avatar
  • 61
1 vote
1 answer
27 views

Why does random noise in recurring task periods result in uniform period offsets?

I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
user avatar
2 votes
1 answer
31 views

Random splitting with fixed size range

I ran into this problem while trying to create a procedural texture algorithm. I ended up using a greedy approximation and shuffling it to hide the bias, but I was wondering if there was a way to find ...
user avatar
0 votes
2 answers
53 views

A so-called random variable not being well-defined

Consider this algorithm: ...
user avatar
  • 377
2 votes
1 answer
115 views

Some questions about `RANDOM(a, b)`

This is a question from CLRS: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ ...
user avatar
  • 377
1 vote
1 answer
88 views

Yao's min-max theorem: how can the set of deterministic algorithms be finite?

I'm read Randomized Algorithms book by Motwani, the part about Yao's min-max technique: Consider a problem where the number of distinct inputs of a fixed size is finite, as is the number of distinct (...
user avatar
2 votes
2 answers
83 views

Approximate duplicate sampling from a stream

The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal. Design an algorithm that takes in ...
user avatar
  • 23
4 votes
0 answers
316 views

FPT algorithm for a variant of Feedback Vertex Set

I am interested in a variant of the Feedback Vertex Set (FVS) problem. For an undirected graph $G$ and $k\in \mathbb{N}$ we need to decide if there is a subset $S \subseteq V(G)$ of size at most $k$ s....
user avatar
  • 103
2 votes
1 answer
99 views

Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
user avatar
1 vote
1 answer
30 views

Number of unique values in array in $\theta(n)$ average expected time

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...
user avatar
1 vote
2 answers
49 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 ...
user avatar
  • 69
2 votes
1 answer
72 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?
user avatar
  • 121
0 votes
2 answers
143 views

How to get the expected time complexity of while loop?

How to get the expected time complexity of while loop below? ...
user avatar
  • 157
12 votes
3 answers
2k views

How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B? This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution ...
user avatar
  • 157
4 votes
1 answer
164 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
user avatar
2 votes
2 answers
54 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, ...
user avatar
0 votes
1 answer
48 views

Finding lowest point in circles

Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm. There are some circles in the plane, these circles ...
user avatar
0 votes
2 answers
38 views

Will random function ever hit a hard coded decimal number?

I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages. But I am curious, will random function ever hits a hard coded decimal number? I ...
user avatar
  • 103
2 votes
2 answers
181 views

Describe a Monte Carlo algorithm for the Triangle Packing problem

Book: Parameterized Algorithms by Marek Cygan (free to download legally) Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19: Describe a Monte Carlo $2^{3k}n^{O(...
user avatar
  • 73
1 vote
0 answers
72 views

Concentration inequality of sum of geometric random variables taken to a power

Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=...
user avatar
  • 433
1 vote
1 answer
121 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$ ...
user avatar
  • 103
1 vote
0 answers
19 views

Representation of connected components in the $O(|E|)$ time/space variant of Karger's algorithm

I'm trying to understand the various optimizations given in the original 1992 paper on Karger's algorithm. Specifically, looking at section "3.1 Unweighted Graphs", I don't understand what ...
user avatar
  • 111
5 votes
1 answer
212 views

Why does a polytime hitting set generator derandomize RP?

I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not ...
user avatar

1
2 3 4 5
8