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.
(Read the article)

google wave lacks structure

Got an invitation to Google Wave today. The problem I find immediately is the lack of structure. Say what you will about the restrictions of email or IM, but the same restrictions of those ways of communication, namely time-flow or thread-flow, are also well enforced structures to keep things sane. Wave takes away these and substitutes “playback.” Unfortunately, playback is not natural. (The other way is to fall back on social convention to keep order, but that rarely works with more than 2 peers.)

I think there are two options here. Either structure needs to be explicitly enforced or presentation needs to be refined.

In the former, perhaps it is better to only allow replies in certain places. Perhaps it is better to only allow edits in certain places. Perhaps it is better to separate the two and keep the distinction between edit mode, thread mode, and conversation mode, and only allow mixing in very restricted settings (or require some extra steps to discourage its use). After all, in preparing a shared endeavor, the purpose should be defined and known ahead of time.

In the latter, perhaps a lot of hiding and collapsing should be used. Perhaps hyperlinks should be used for in-place edits that often hijack a topic. And now that subthreads can sprout like a tree, it makes little sense to retain the linear structure of conversations. Perhaps a topic based graph, or a conversation stack would be the more appropriate presentation metaphor.

Wave is a good idea, but not well thought out. In its attempt to differentiate, it has forsaken useability for chaotic flexibility, which would have had redeeming value, were it matched by equally ambitious presentation/visualization.

Wired on the Gaussian copula

Because this article is spamming the internet today, I decided to read Li’s paper and learn what the heck is this Gaussian copula.

For five years, Li’s formula, known as a Gaussian copula function, looked like an unambiguously positive breakthrough, a piece of financial technology that allowed hugely complex risks to be modeled with more ease and accuracy than ever before. With his brilliant spark of mathematical legerdemain, Li made it possible for traders to sell vast quantities of new securities, expanding financial markets to unimaginable levels.

And anyway, here is the paper referenced in the article.
(Read the article)

On Penmanship in Chinese

I suppose good penmanship is the basis of good calligraphy, since calligraphy is mainly the addition of (variable) brush width to the structure of the characters. This bulk structure is really the key and it is particularly difficult to get correctly without muscle memory. That’s why they tell you to trace character books over and over.

However, there is a way to figure this matter of structure from first principles (and perhaps generate a more unique style as a result), albeit with the tradeoff that you cannot be quick, you must be careful.
(Read the article)

Windows 7, again

Got it installed and seems like a clean update on Vista. Somebody must have cracked the whip on simplicity, since nearly everything involving user interaction got simpler. Since it is mostly feature extensions on Vista, it is quite stable.

Some less noticed changes:
* IE8 now runs all tabs and windows in separate processes, so there is no longer a distinction between tabs and windows. There is also (finally) a Mozilla style jump-highlight in-page search. There is a convenient “In Private” mode that leaves behind nothing, but it is kind of stupid in that it doesn’t sandbox in cookies to delete them afterwards but in fact doesn’t appear to store them at all, breaking some sites… or maybe it’s just a bug. There are also these “accelerators” to web services (like smart tags on crack), not that useful in my opinion.
* English ink input in continuous mode now displays recognitions in-place, rather than in typeface underneath.
* Services for Unix (the POSIX subsystem) is much much improved and is actually usable for compilation.
* Monad (or PowerShell), which got dropped from Vista, is in. Very nice.
* Desktop backgrounds now come in sets of images, rather than one image.
* Yet another new directory structure for user home directory. The “data” folders in the home directory like Pictures, Music, Movies, Documents are now symbolically separated into a “Libraries” indexing structure (kind of like in WMP), and apparently you can create multiple libraries. Not sure if this is implemented cleanly enough, but intersting.

That’s about it.