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.

Filter by
Sorted by
Tagged with
6
votes
1answer
357 views

What is the approximation ratio of this randomized algorithm for finding matchings?

I would like to analyze the following algorithm in terms of its approximation ratio. Here is the algorithm: ...
5
votes
1answer
1k views

What does the “principle of deferred decisions” formally mean

I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ...
2
votes
0answers
101 views

min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
3
votes
1answer
489 views

Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 ...
0
votes
1answer
96 views

On deterministic weighted graph isomorphism from randomized

Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism. Basically take an real edge weight set $\{w_1,\dots,...
1
vote
1answer
481 views

How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (...
2
votes
2answers
177 views

Are Random Forests Turing-Complete?

Is the random forests algorithm Turing-complete? As in, can any algorithm be represented by a given "tree" in the forest?
2
votes
1answer
1k views

What is a stateful computation?

I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means. See: http://projects.csail.mit.edu/church/wiki/...
1
vote
0answers
16 views

What use does the predictor stage in a particle filter have?

Im a bit confused about the particle filter. I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic ...
8
votes
3answers
411 views

Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
2
votes
1answer
345 views

Methods for proving upper bound on a-approximiation algorithms? [closed]

I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance. For example, there's a simple randomized algorithm for the ...
5
votes
3answers
251 views

Is there a random shuffle algorithm using only true /false?

Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals. For this question, I'm ...
3
votes
2answers
225 views

Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
2
votes
2answers
107 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
1
vote
2answers
77 views

Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned". Is shuffling the "free" set after assigning an employee meaningfully more random ...
8
votes
2answers
178 views

Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
4
votes
2answers
2k views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
2
votes
1answer
125 views

Deamortizing a Las-Vegas randomized algorithm

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. For example, assuming you need to find the median of an array once every $n$ ...
4
votes
0answers
187 views

Data structures for ordering noisy data

In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
6
votes
2answers
746 views

Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability. The algorithm choose a random $r$ n-...
1
vote
1answer
400 views

How does one compute the probability of a false-based Monte Carlo algorithm being correct rigorously?

Recall that a false-biased Monte Carlo (MC) algorithm is always correct when it returns false for some decision problem i.e. it has a one sided error and its always correct on NO instances. Assume ...
4
votes
1answer
273 views

Choosing a random bit from a bitmap

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so. I have quite a large bitmap (~100 Million bits) (e.g. ...
7
votes
1answer
166 views

Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
0
votes
1answer
1k views

Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum

I'm stuck with one of my homework exercises: Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t: ...
2
votes
0answers
66 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
1
vote
1answer
46 views

Proving simple bound on coupon collector

I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the ...
6
votes
1answer
185 views

Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In its definition it states: If the correct answer is NO then it always ...
1
vote
1answer
505 views

Finding the kth smallest element of an array using DAC [closed]

I'm trying to find the $k^{th}$ smallest element of an array by using Randomized Quicksort, But below code giving erroneous result can anybody help. ...
0
votes
1answer
49 views

How to “properly” handle incorrect values in a random walk?

I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple "...
1
vote
1answer
66 views

How to simulate this randomized “finite” sum? [closed]

Consider the the Geometric Brownian motion $\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$. for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final ...
1
vote
1answer
494 views

How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
4
votes
2answers
246 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
0
votes
1answer
164 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
4
votes
1answer
93 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
2
votes
1answer
84 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
2
votes
1answer
439 views

How does derandomization of 3SAT work via conditional expectations?

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8 But I do not understand how from ...
3
votes
1answer
161 views

What is the rigorous definition of an efficient algorithm that $\epsilon-refutes$ random 3CNF formulas

I recently asked a similar What does "refuting random 3CNF" formulas mean?, however, I'd like to address it in a more mathematically precise setting. In that paper, on page 5, it talks ...
6
votes
1answer
774 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
2
votes
1answer
56 views

How does one change the probability bounds in probabilistic complexity classes without changing the class?

I see this theorem whose proof is not clear to me : "Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ M(...
2
votes
1answer
44 views

Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
3
votes
1answer
141 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
1
vote
1answer
62 views

Approximating the set of witnesses of a BPP algorithm

Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = \{r\in\{0,1\}^n:\...
4
votes
1answer
243 views

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
1
vote
2answers
159 views

About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...
0
votes
1answer
75 views

Complexity bound on $RP^{RP}$

This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in $RP$...
8
votes
1answer
163 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
2
votes
0answers
235 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,...
2
votes
1answer
80 views

Does randomness make exponential difference?

Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the ...
-1
votes
1answer
571 views

Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
16
votes
1answer
326 views

Lost in a “one directional” concert

You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate ...