Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [randomized-algorithms]

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

0
votes
0answers
24 views

Randomly choose matrices $A_{j}B = C_{j}$ with elements between 0 and 1

Problem I have $J$ matrices $C_{j}$, which are $K \times M$. Elements of each matrix $C_{j}$ are between 0 and 1. I want to randomly choose $J$ matrices $A_{j}$ and one matrix $B$ such that: ...
1
vote
1answer
19 views

Concentration bound for sum of dependent geometric random variable?

consider following persudocode: i=0 while(i< k): uniformly pick u,v in V if(uv in E): remove uv form E; i++; let $T$ be the number of ...
3
votes
1answer
90 views

expected pairwise square euclidean distance between points

How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$? Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-...
1
vote
1answer
32 views

Amplification for Randomized Algorithms

I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms. Amplification for randomized algorithms: Given a randomized algorithm with time ...
0
votes
0answers
20 views

Is it possible to build an algorithm that can 'web crawl' to build questions and produce answers?

I'm building a revision based app and one of the ideas that occured to me was a section that tested knowledge of a given subject (let's say data mining) by using the web to create questions the user ...
3
votes
2answers
96 views

Efficiently shuffling items in $N$ buckets using $O(N)$ space

I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows: We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a ...
0
votes
0answers
11 views

Hit-and-run stucks near edge/corner of polytope

I try to generate random points within a convex polytope. Hit-and-run sampling can get stuck near the edge and corner of a polytope if I use a moderate number of steps. A point at the corner has ...
2
votes
2answers
51 views

Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?

Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. ...
0
votes
0answers
50 views

Is there a name for this sorting mechanism? [duplicate]

The sorting algorithm gets an object out of a list of total objects, and then removes that object from the list, by moving the object at the end to the position where the object was, and creates the ...
2
votes
1answer
55 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\...
0
votes
1answer
56 views

Hiring problem from CLRS

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions. However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
0
votes
0answers
13 views

Question about RANSAC required numer of trials

The number of trials $T$ that will guarantee a probability $p$ of having at least 1 trial wherein our sample of size $s$ contains only inliers is given by $$ T = \frac{\text{log}(1-p)}{\text{log}(1-\...
0
votes
1answer
28 views

Monte-Carlo Algorithm for counting 'on' bits in a binary array

Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2: $\frac b 3 \leq a \leq 3b$ How can I use A to build an ...
1
vote
0answers
54 views

Finding subset of integer summing up above threshold

Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
0
votes
0answers
8 views

What would be a typical BPP algorithm to solve transportation problem?

I'm wondering if there are simple examples of algorithm which could solve transportation problems? I would like to use derandomization methods to solve real life problems, such as optimizing a ...
1
vote
0answers
12 views

Given a simple graph G, what's the quickest known way to sample one of it's 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 ...
2
votes
1answer
52 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 ...
5
votes
1answer
104 views

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results ...
0
votes
0answers
26 views

Polynomial Identity Testing (PIT) and the underlying field

It is well-known that PIT can be done in co-$\mathrm{RP}$ using Schwartz–Zippel lemma. Depending on the underlying field $\mathbb{k}$, $\mathrm{PIT}_\mathbb{k}$ may be in $\mathrm{NP}$ or not. My ...
5
votes
1answer
204 views

Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...
1
vote
1answer
42 views

number of random sets needed to generate subset

Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$. How many $...
2
votes
1answer
201 views

Average case of simple algorithm like binary search

These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me. I have a special search algorithm which the explanation here will take a lot of ...
1
vote
0answers
25 views

Generate a random tree population

Given a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees ...
1
vote
0answers
66 views

Generate higher dimensional pink noise

1D Pink noise, is easy enough to generate. See https://www.dsprelated.com/showarticle/908.php for example. What about higher-dimensional pink noise, such as 2D or 3D pink noise? Is there an algorithm ...
2
votes
2answers
56 views

Question about Morris' algorithm

I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows. Problem: Given an input stream $\sigma$, compute (or approximate) its ...
0
votes
2answers
65 views

Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
2
votes
0answers
19 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 < ...
0
votes
0answers
46 views

$SAT$ and $BPP=P$ conjecture?

$BPP$ is the complexity class that accepts all languages for which there is Poly time TM with at least $1/3$ of their computation paths accept and rejects all languages for which there is Poly time TM ...
2
votes
1answer
69 views

Can an algorithm be truly non-deterministic?

I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
2
votes
1answer
71 views

Weighted probability using Huffman Tree

I want to produce a value from a set, where each value has an associated weight. Eg: [(1, 4), (2, 3), (3, 3)] should give me a 40% chance of picking 1, and a 30%...
0
votes
0answers
10 views

What is the complexity of this Randomized Minimal Suppport Algorithm

I need to calculate the worst case complexity of the next algorithm --solve_random_undetermined_system_and_verify. This algorithm calculates under certain conditions $x\_sols$ solutions of a random ...
4
votes
1answer
32 views

Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays ...
2
votes
0answers
128 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
2answers
50 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
171 views

Generating uniformly random bits from a stream of arbitrarily biased bits

Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I ...
7
votes
3answers
2k views

Problem with the pseudo random number generator One-Time-Pad

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
3
votes
1answer
57 views

How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

I'm considering the following definition of one-way functions: Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is ...
-1
votes
1answer
100 views

Applying a Chernoff bound with Only an Upper Bound of the Expectation

First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The ...
4
votes
1answer
33 views

Is there a name for “yield first result parallel map”?

Context In randomized algorithms two schemes of computation are common: Las Vegas algorithms with random running time Randomized algorithms that have a probability of success, and have to be ...
1
vote
1answer
167 views

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?
0
votes
1answer
37 views

Probability that a leaf with 1 will be selected in game tree evaluation

I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar). ...
2
votes
2answers
158 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
0
votes
0answers
121 views

Randomized Merge Sort Comparisons

While learning about Randomized Algorithms, I've encountered the following problem: I've changed Merge Sort like this: For each recursion, instead of splitting in the middle - I "flip a coin" for ...
1
vote
1answer
27 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, ...
3
votes
1answer
97 views

non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to ...
3
votes
2answers
276 views

how to bound the probability that quicksort takes greater than n lg n time?

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed) Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
2
votes
1answer
64 views

Why doesn't this put $BPP$ in $NP$?

From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$ From Adleman we know $x\in L(M)...
1
vote
0answers
56 views

Randomized Algorithm for determining items with rank $\geq n/16$

Problem: We say that an item $x$ is of rank $m$ if there are $m$ items in the set less than $x$. Design a randomized algorithm to find all of the items in a set of size $n$ with rank greater than $\...
2
votes
0answers
133 views

How do I do a biased shuffling of a deck of cards?

I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want ...
2
votes
1answer
179 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 ...