Macs and Romanian keyboards

As I found out the other night, the effects of beer on laptops are not nearly as positive as on researchers.

Having to get a new laptop, I decided to bring a Mac "into the family." Everything seems great so far --- it didn't take more than a day to figure out the basics and install several Gb of software essentials (starting with MacTex and Aqumacs Emacs, on to Unison, and recovering all my files from the MIT servers).

Of course, the transition is helped by my insistence on pretending that my Windows was actually Unix (via Cygwin). It feels good to return to a true Unix (after 6 years or so) and stop the pretending. The Mac's superiority seems undeniable (it is Unix, and therefore strictly better than Windows, and it has a wonderful graphical interface, significantly better than X).

Keyboard layouts. The one thing that MacOS did lack was an ergonomic Romanian keyboard layout. As I mentioned before, I find the standard Romanian keyboard horrible, since it banishes some of the most useful Romanian characters (ășțîâ) to the end of keyboard, where they replace other useful characters ([, ], :, etc). The solution is to put the useful Romanian keys on the Latin letters that are not normally used in Romanian (q->ă, w->ș, x->â, k->î, y->ț). To get the original Latin key, press Alt+key. The mapping may seem ad hoc at first, but my experience is that you learn in within minutes, because ț is right next to t, ă right next to a, ș right next to s, and î right next to i. The credit for the original idea goes to ErgoRomanian, a keyboard layout for Windows.

Download. To get what I wanted, I hacked the standard US layout on the Mac. Here is the resulting Romanian Ergo keyboard layout. For the Romanian flag in the menu bar, also download this icon.

Installation:

1. Download the files and move them to ~/Library/Keyboard Layouts/
2. Log out and back in
3. Go to System Preferences > International > Input Menu. Look for Romanian Ergonomic, and check it.
4. [optional] Click on Keyboard Shortcuts, disable the Spotlight check buttons, and enable the Input Methods ones. This allows you to switch keyboard layouts by pressing Command-Space.
   

Alternative spelling. Admittedly, the one slightly annoying feature of this layout is the x->â replacement, since x does sometimes get used in Romanian. But if you did not adopt the spelling recommendations of the Romanian Academy (i.e., if you spell pîine instead of pâine), you shouldn't have a problem, since â is a very uncommon letter for you. I made an alternative Ergo-X layout, in which x remains the default, and Alt-x gives you â.

Download: the Romanian Ergo-X keyboard layout, and its icon. Follow the same instructions as above.

As always, please report any bugs or suggestions.

Tango trees

At the request of Sanjeev Arora, I prepared the following lecture notes about O(lglg n)-competitive binary search trees (our Tango trees).

The main innovation is the proof of the Wilber-1 bound. As opposed to the somewhat hairy proof in Wilber's paper and in our paper's appendix, I show Wilber-1 by arguing about the problem geometry and maintaining partial sums (forget trees!). Hopefully this gives a more intuitive proof. In any case, it shows the students something very important in its own right.

If you read these notes, I am interested in anything you have to say, including things you didn't understand, or suggestions for clarifications. 

SODA (II)

The SODA accepted papers, with abstracts, can be found in this text file, or as a PDF file (curtesy of Suresh). 

Each year, looking at the SODA list of papers makes me depressed. It is hard to see --- among all the quantum dogs and ponies exhibiting Braess's paradox in stochastic networks with piecewise linear costs --- how we are working to understand the fundamental questions about computation.

What we're missing badly is innovation in solution space, not innovation in problem space. Remember this when you sit down to work on your next paper.