# Questions tagged [probabilistic-algorithms]

Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.

157 questions
Filter by
Sorted by
Tagged with
25 views

### Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208: My question is about this part. [Convolutional codes have been popular in ...
96 views

### What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the ...
44 views

### Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
14 views

### Reference on PCP theorem

Can someone recommend a reference on the PCP theorem that explains how it works via examples rather than formal CS language? Specifically, I'm looking for the example on how graph colouring can be ...
229 views

### Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...