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
4
votes
1answer
323 views

Comparing A* search to Simulated Annealing

Good Afternoon, I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my ...
2
votes
1answer
59 views

Choosing $n$ points to get the closest sum

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, ...
0
votes
0answers
260 views

How to prove the correctness of inside-out shuffle algorithm

I've read this similar question How to prove correctness of a shuffle algorithm? and I understand the answer. However I still couldn't figure out how to apply that inductive proof to a similar shuffle ...
1
vote
1answer
121 views

General approach to randomized algorithm for equality problem

Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication). With other definitions of of equality (not strictly equal), is there a general approach to ...
1
vote
1answer
43 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 $...
8
votes
1answer
630 views

Randomized algorithm for 3SAT

There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment ...
0
votes
1answer
262 views

Randomized linear search — Why does reducing the sample size make the running time constant?

I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$): (1) Pick a random index $i$ from $L = [1, \ldots n]$. If $A[i] = x$, terminate. Otherwise, pick a new ...
1
vote
1answer
487 views

Algorithm to distribute elements evenly among a population

Algorithm to distribute elements evenly among a population In the software I am doing I have three different categories: ...
2
votes
1answer
254 views

Alternative definitions of ZPP and probabilistic Turing Machines

There are two ways to define a probabilistic Turing Machine: A Turing Machine that can toss coins during its computation. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is ...
0
votes
0answers
127 views

Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
5
votes
1answer
82 views

Uniformly Random Nested Subset Pairs

Main Question We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example ...
1
vote
1answer
44 views

Randomized algorithm for 2kCNF satisfiability problem

The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a ...
1
vote
0answers
120 views

prove that $BPP(\alpha(n), \beta(n)) = BPP$

prove that for every $0 \le \alpha(n), \beta(n) \le1 \; s.t.$ there exists $c \in \Bbb{N} \;s.t \;\alpha(n)+\beta(n) \le 1- \frac{1}{n^c}$ then $BPP(\alpha(n), \beta(n)) = BPP$. I tried to show that ...
2
votes
1answer
228 views

detecting a cycle in an undirected graph problem is in $RL$ complexity class

I need come up with an algorithm for detecting a cycle in an undirected graph where the algorithm is in $RL$. That is, the algorithm detects a cycle with a probability greater-equal to $\frac{1}{2}$ ...
0
votes
0answers
209 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 ...
1
vote
0answers
79 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 ...
3
votes
1answer
199 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 ...
4
votes
3answers
494 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 ...
3
votes
2answers
124 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 ...
4
votes
1answer
169 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 ...
1
vote
1answer
60 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: ...
3
votes
1answer
890 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 ...
1
vote
0answers
81 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 ...
3
votes
1answer
70 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 ...
1
vote
1answer
146 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$ ...
2
votes
1answer
107 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: ...
2
votes
2answers
367 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, ...
0
votes
0answers
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. ...
0
votes
0answers
74 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 ...
1
vote
1answer
88 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, ...
7
votes
2answers
207 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 ...
2
votes
1answer
419 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 ...
1
vote
1answer
198 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 ...
0
votes
0answers
259 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?
0
votes
2answers
697 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]$. ...
4
votes
1answer
40 views

Logarithmic guarantees for randomized search trees

In this paper [1], "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 ...
1
vote
1answer
77 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 ...
0
votes
1answer
123 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 ...
2
votes
1answer
332 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)$ , ...
0
votes
1answer
50 views

Expected versus Randomized

Is there any difference between expected polynomial time and randomized polynomial time algorithm?
1
vote
0answers
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 ...
0
votes
1answer
164 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 ...
1
vote
0answers
87 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 ...
3
votes
1answer
230 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 ...
2
votes
1answer
204 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
111 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
57 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 ...
12
votes
2answers
417 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,...
2
votes
2answers
978 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 ...
1
vote
1answer
74 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 ...