## Archive for March, 2012

### on eating crabs

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.

### data structure problem

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.