# Tag Info

Accepted

### "Almost all objects have property P" vs. "It is easy to test whether an object has property P"

They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance ...
• 10.4k

### Throwing Balls into Bins, estimate a lowerbound of its probability

The answer is $\Theta(\sqrt{n})$. First, let's compute $E_{n-1}$. Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability ...
• 23.5k
Accepted

### Calculate Huffman code length having probability?

The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length ...
• 23.5k
Accepted

### What is the expected depth of a randomly generated tree?

I think there is a concentration result about $e \log n$, but I haven't filled in the details yet. We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For ...
• 316
Accepted