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
403 views

Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
8
votes
0answers
88 views

Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
1
vote
1answer
162 views

Error lower-bound for an algorithm for vertex cover

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \...
3
votes
1answer
25 views

Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
1
vote
0answers
28 views

Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ ...
2
votes
1answer
32 views

Imperfection in randomness in VLC shuffle playlist - why?

Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs). I know ...
9
votes
4answers
383 views

How to devise an algorithm to generate a random but valid train track layout?

I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those ...
1
vote
1answer
38 views

Doubt on Karger's Algorithm for Min-Cuts

I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My ...
1
vote
0answers
24 views

Randomized version of the class $APX$?

Is there a class which is to APX what BPP is to P? I'm looking for a definition that is like the following: "For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
0
votes
0answers
21 views

Bayes theorem and randomized algorithms

Are there any randomized algorithms that make use of Bayes theorem? where are they used and why?
2
votes
1answer
75 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: ...
3
votes
0answers
90 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 $...
4
votes
0answers
34 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
33 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
609 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
9 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
28 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 ...
1
vote
1answer
51 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
14 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 ...
0
votes
0answers
28 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
46 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 ...
3
votes
0answers
53 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
93 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
87 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
27 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
69 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 ...
1
vote
1answer
63 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
19 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
26 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 ...
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: ...
4
votes
0answers
55 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 ...
4
votes
1answer
43 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.
4
votes
1answer
58 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
68 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
73 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 \...
0
votes
1answer
58 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 ...
21
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
78 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
31 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
83 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
55 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
3answers
340 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 ...
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
43 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
0answers
14 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
38 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 ...
3
votes
1answer
85 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 ...
1
vote
1answer
23 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$-...