The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [randomized-algorithms]

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

288 questions
Filter by
Sorted by
Tagged with
20 views

Bayes theorem and randomized algorithms

Are there any randomized algorithms that make use of Bayes theorem? where are they used and why?
71 views

Does this shuffle have non-zero probability for all permutations?

I was trying to do some code golf, when I created the following algorithm to shuffle a string: ...
48 views

intervals in geometrical points in 2D space

Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
78 views

54 views

Randomized algorithm to compute cover radius?

I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it. Let $C$ and $P$ be two sets of point in the plane , such ...
42 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
12 views

Randomized response vs Output Perturbation

what are the difference between Randomized response and output perturbation? The only one I can think of is that Randomized Response's output is not always perturbated while in the other case it is.
52 views

55 views

What properties does a co-RP problem need to be in P?

Given an arbitrary language $L$ with an algorithm $A$ that places $L$ in $co-RP$ what other properties does the Algorithm $A$ need to have to so that $L$ is in $P$? For example: Considering $L$ is ...
8k views

Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
51 views

How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...
29 views

Difference of simulated annealing and random search for generating crossword puzzles?

I heard that when one wants to write a program to make a crossword puzzle, he can use for example simulated annealing as in the thesis Crossword Construction using Constraint Satisfaction and ...
74 views

Network throughput with random delay selected from uniform distribution

Background: I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the ...
44 views

Measuring the Probability of Error for a Potential BPP Algorithm

Problem Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space ...
163 views

Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
50 views

Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
39 views

Using exponential penalty functions in constrained nonlinear optimization

Background: penalty functions Penalty functions convert a constrained optimization problem \begin{equation}\begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 ...
13 views

Best asymptotic randomized multidimensional index?

What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
36 views

Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
74 views

Split a list of elements into sub lists, each with different criteria

I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same ...
22 views

Expectation of $\langle s,x \rangle^2$

I'm studying dimensionality reduction (SVD in particular), and I saw the following question: Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ , where $s$ is a $d$-...
36 views

Sublinear Homomorphism Property Testing Counter Example

This is a homework question, so I'm not looking for answers, just general guidance. I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of ...
32 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: ...
44 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 ...
253 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-...
66 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 ...
129 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 ...
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. ...
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\...