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
1 vote
1 answer
28 views

Expected runtime of recursive algorithm with optional part

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
1 vote
1 answer
46 views

About quicksort analysis

We know that the expected running time $T(n)$ of quick sort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$ and from ...
  • 245
0 votes
0 answers
35 views

Runtime Analysis of Uniform Sampling via exact degree computation

Let $\mathcal{A} \subseteq \mathcal{B}$ given as a collection of arrays. The degree of an element $a \in \cup \mathcal{A}$, is the number of sets of $\mathcal{A}$ that it contains - that is, $d_{\...
  • 11
0 votes
0 answers
23 views

How to apply Hyperloglog to count distinct elements but with condition

I'm going to adapt the Hyperloglog algorithm to count distinct numbers from a stream. But now, it is more challenging; say, there is a condition: the number needs to exist in the database so that it ...
  • 1
1 vote
0 answers
24 views

Communication complexity of index problem with large domains

In the standard definition of the Index problem in one-way 2-party communication complexity, there are two players, Alice and Bob. Alice gets a binary input vector $x$ of length $n$ and Bob gets an ...
0 votes
0 answers
22 views

In each level of a skip list, the expected number of scan-forward steps is 2, but how?

We know that the expected number of coin tosses required in order to get tails is 2. How can this be related to the expected number of scan-forward steps in a level of a skip list?
0 votes
1 answer
25 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 ...
  • 1
2 votes
1 answer
43 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 ...
1 vote
2 answers
78 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.
  • 153
1 vote
0 answers
41 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 ...
1 vote
1 answer
54 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 ...
  • 37
2 votes
1 answer
44 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 ...
1 vote
0 answers
21 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 ...
4 votes
2 answers
70 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 ...
  • 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 ...
  • 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 ...
0 votes
1 answer
20 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 ...
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 ...
0 votes
1 answer
61 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 ...
1 vote
1 answer
122 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 : ...
0 votes
1 answer
59 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 ...
2 votes
0 answers
41 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 ...
  • 149
2 votes
0 answers
40 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 ...
  • 227
2 votes
0 answers
53 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 ...
0 votes
1 answer
78 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 ...
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 ...
0 votes
0 answers
27 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 ...
2 votes
0 answers
56 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 ...
  • 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: ...
  • 101
4 votes
1 answer
381 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 ...
1 vote
1 answer
81 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, ...
  • 143
1 vote
1 answer
36 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 ...
  • 13
2 votes
1 answer
81 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 ...
1 vote
0 answers
72 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 ...
  • 61
1 vote
1 answer
30 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 ...
2 votes
1 answer
38 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 ...
0 votes
2 answers
54 views

A so-called random variable not being well-defined

Consider this algorithm: ...
  • 377
2 votes
1 answer
121 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$ ...
  • 377
1 vote
1 answer
99 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 (...
2 votes
2 answers
98 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 ...
  • 23
4 votes
0 answers
318 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....
  • 103
2 votes
1 answer
122 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 ...
1 vote
1 answer
35 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 ...
1 vote
2 answers
56 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 ...
  • 190
2 votes
1 answer
91 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?
  • 121
0 votes
2 answers
206 views

How to get the expected time complexity of while loop?

How to get the expected time complexity of while loop below? ...
  • 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 ...
  • 157
4 votes
1 answer
171 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 ...
2 votes
2 answers
90 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, ...
0 votes
1 answer
59 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 ...

1
2 3 4 5
9