One might think it cruel to boil and eat those crabs taken from the sea that had been alive but a moment ago, roe and all, but they do not give up so easily even in perfect death, tearing your meat up with sharp spines just as you try to tear them up, prying your teeth back just as you try to pry them open with teeth. Furiously you ponder the caloric implications of this meal, but you push on, till they are a broken bony pile of discarded refuse, and you have asserted the order of nature, with bloody fingers and injured tongue.

The travails of defending carnivorism against unrelenting crabs is crueler than the ease of aborting a family tree of them.

Comments(0)

Another problem by fakalin.

A data structure has the entropy bound if all queries have amortized time \(O(\sum_k p_k \log 1/p_k)\), where \(p_k\) is the fraction of the time that key \(k\) is queried. It has the working-set property if the time to search for an element \(x_i\) is \(O(\log t_i)\), where \(t_i\) is the number of elements queried since the last access to \(x_i\). Prove that the working-set property implies the entropy bound.

This isn’t really a data structure problem, per se.
(Read the article)

Comments(0)

This is a problem via fakalin.

You have 10 pieces of string, each with two ends. You randomly pick two ends of string (possibly from the same string, possibly from different ones) and tie them together, creating either a longer piece of string or a loop. You keep doing this until you run out of free ends.

What is the expected number of loops you end up with?

(Read the article)

Comments(0)