# Questions tagged [randomized-algorithms]

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

284 questions
Filter by
Sorted by
Tagged with
161 views

### Is important for Fisher–Yates shuffle algorithm to generate random numbers in the sequential increment

This is a follow-up question to the Why shuffling by picking random position in all array instead of a part is not correct. I understand if I pick random numbers from all the range for 4 numbers every ...
76 views

### Is L/Poly practical?

Cryptographic security is usually proven against P/Poly adversaries as this encapsulates the possibility for someone to do heavy precomputation to be used later, eg. rainbow tables. However actually ...
192 views

### Reducing randomness needed by turing machine

I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff, At some point they have a ...
347 views

### Why shuffling by picking random position in all array instead of a part is not correct

There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a ...
112 views

### Why 0-BPP equals P

Sorry if it is an obvious question, since all my searches lead to "clearly 0-BPP=P" (like Papadimitriou text book or Complexity Zoo). I understand that any P machine can be seen as a 0-BPP machine ...
152 views

### Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
55 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: ...
765 views

### Generating a random path in a grid without deadlock

I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice. One simple solution would be ...
80 views

### Creating Random Number Generator with range

I've been trying to create my own random number library(in java). I've searched for randomization and Blum Blum Shub algorithm looks good. It needs a start value, it is not actually random. So i get ...
65 views

### Sampling from a set of numbers with a fixed sum

Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen ...
138 views

### Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

Let me define the problems first Polynomial Identity Testing $(\mathsf{PIT\text{}})$ Given : A polynomial $p$ over some field $\mathbb{F}$. Decide : Are all coefficients of the monomials of $p$ ...
96 views

### What is the Expected run time of an algorithm that randomly generates N unique strings of length D?

I was trying to rigorously/mathematically analyze the runtime of the following algorithm: ...
338 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, ...
28 views

### Collecting the most Fruit on a Grid

There is a grid of size WIDTH * HEIGHT. X fruits are randomly distributed on the grid. ...
63 views

### Improving success probability for one sided error algorithms

Suppose I have a probabilistic Turing machine for a language such that $$x \in A \implies \Pr(M \text{ accepts } x) \ge \frac{1}{n}$$ $$x \notin A \implies \Pr(M \text{ accepts } x) = 0$$ I want to ...
84 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, ...
196 views

### Why is randomness a problem? (i.e. why do we care about derandomization?)

I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with ...
395 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 ...
162 views

### Shuffle an array based on some rules

I have a set of images. The length is variable. It could be anything up to about 30 images. Each image can have up to 10 tags. Images may share some, all or none of their tags. I need to select a ...
236 views

### What are randomized algorithms and what are they used for?

I wanted to know what are randomized algorithms and what are some of their uses? When do you think they outperform "standard" algorithms?
617 views

### What is the time complexity of this randomized algorithm? [closed]

Let's start with a problem statement: given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps: Select a random number $k$ in range $[1, n]$. ...
40 views

### Logarithmic guarantees for randomized search trees

In this paper , "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being ...
76 views

### Help with a difficult expected runtime recurrence

I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$. At each iteration $i$, I have a random variable $k_i$ that is equal to the number ...
117 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 ...
315 views

### Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?

I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something. The analysis goes as follows: Fix a min cut $(A,B)$. Let $k$ = # of edges crossing $(A,B)$ , ...
50 views

### Expected versus Randomized

Is there any difference between expected polynomial time and randomized polynomial time algorithm?
44 views

### What resources are there for students to compute on a data stream?

I teach a randomized algorithms course, and many of the cool applications are to streaming computation. I can have students implement these algorithms in Python or C++, but I feel it would be much ...
157 views

### How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
57 views

### Motwani-Raghavan 4.10 Ideas

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the ...
197 views

### Derandomization of an approximation algorithm for solving a linear system

I was given a HW assignment that asks me the following: Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment ...
195 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. ...
104 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 ...
55 views

### Perturbing trees

I have a collection of labelled directed trees, and from these input trees I would like to generate permuted trees that have the same node set but whose edges and labels have been permuted with some ...
398 views

### Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
878 views

### TSP problem with a benchmark data

I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here. I'd started a ...
73 views

### How can simulated annealing be related to the vehicle routing problem?

I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers ...