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
3
votes
1answer
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 ...
0
votes
0answers
20 views

Bayes theorem and randomized algorithms

Are there any randomized algorithms that make use of Bayes theorem? where are they used and why?
3
votes
0answers
75 views

What is the exact time complexity of randomized Kuhn's algorithm?

Please, read the whole question before answering, the exact details of the implementation are important. Suppose that you want to find largest cardinality bipartite matching in bipartite graph with $...
1
vote
1answer
47 views

Finding efficient randomized algorithm

I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve. Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ ...
0
votes
0answers
17 views

How to generate “Random Rotation Matrix”? [closed]

Are there library or open source software which I can use to generate “Random Rotation Matrix”? If not, what's the best algorithm, theory or method which i can implement by myself? Actually, I don't ...
2
votes
1answer
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: ...
-1
votes
0answers
47 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 ...
0
votes
1answer
283 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 ...
4
votes
0answers
30 views

Karger's min-cut (contraction): Combinatorial argument for success probability?

The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
0
votes
1answer
29 views

What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this ...
7
votes
1answer
599 views

Random restarts for unsatisfiable instances

In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice. ...
0
votes
0answers
7 views

Algorithm for Autonomously Culling Swarm

I'm trying to find an algorithm that would be able to cull a swarm of unknown size to around a known number with no overarching controller or dynamic registry (Each node should be able to decide ...
0
votes
0answers
25 views

Random Teams based on Positions in Sports

I have tried to find an answer to this but haven't found exactly what I'm looking for. I am trying to develop a way in which I can have a random team selected based on skill set (1-5 with 5 being ...
2
votes
2answers
82 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. ...
1
vote
1answer
43 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
64 views

Pseudo-random role assignment

I have a number of players, ranging from [0..N]. Each round every player is assigned a specific role, either 1, 2 or 3. ...
0
votes
0answers
12 views

Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls

I have an algorithmic problem that requires some lengthy explanation, which follows below. tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
3
votes
2answers
259 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
19 views

CNN Predicting One Class and Accuracy Getting Stuck

My model is a binary classifier. With the same exact architecture, the model sometimes gets high accuracy (90% etc), other times it predicts only one class (so accuracy is stuck at one number the ...
1
vote
1answer
40 views

Why is $ZPP \geq BPP$ not true?

This seems like a silly question, but I couldn't find a conclusive answer for it. As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or ...
1
vote
1answer
44 views

Can BPP be bounded around any constant other than 1/2?

A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
3
votes
0answers
41 views

Alternative criterion for approximate maximum-weight perfect matching algorithms [closed]

Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but ...
2
votes
1answer
75 views

Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
2
votes
1answer
54 views

Introduction to Algorithms (CLRS) Ex 5.2-5 solution

The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition. Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an ...
1
vote
1answer
22 views

Questions about Randomized Median algorithm?

In textbook by Mitzenmacher and Upfal here, they write in page 62, the following: By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never ...
2
votes
2answers
43 views

How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he ...
2
votes
2answers
539 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?
3
votes
0answers
17 views

Random paths from one point to another going through all the cells of a square grid

I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it. My problem is about a square grid of size <...
2
votes
0answers
20 views

Correctness of Karger's min-cut Algorithm

tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
4
votes
0answers
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 ...
3
votes
1answer
31 views

Non-existence of approximation algorithm for the knapsack problem

I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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.
3
votes
1answer
52 views

Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise. Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
0
votes
0answers
18 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
4
votes
1answer
62 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
65 views

Constructing hitting sets for randomized algorithms

Suppose A($\cdot$,$\cdot$) is an efficient randomized algorithm and L is a language such that $\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$ and if $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \...
20
votes
6answers
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 ...
1
vote
0answers
49 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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
43 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 ...
2
votes
0answers
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 ...
2
votes
2answers
154 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 ...
1
vote
1answer
57 views

Given a simple graph G, what's the quickest known way to sample one of its 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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
8
votes
1answer
515 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 ...