Jan VarhoJust uploading this short note/paper here in case anyone ever finds it useful and so I won't lose it again. I wrote this last year, during the summer as I worked on networks.
I implemented a fast - O(lg^3(n)n), almost linear - modularity
optimization (community detection) algorithm based on the extremal
optimization
algorithm of Duch and Arenas (in turn based on Boettcher and Percus on
other problems). The pdf details the algorithm and also has notes on the
dataset I downloaded from arXiv to run the algorithm on.
I've glossed over a lot of details, but on the off chance it's useful, feel free to contact me for more information.
Download: Efficient Implementation of Community Detection Using Extremal Optimization (pdf, 112KB)
One of the changes in the recent Ubuntu 10.10 (Maverick) is the upgrade of Linux kernel from version 2.6.32 (in Lucid) to 2.6.35. The change introduces several new features of which I especially like Radeon power management (for use with open drivers).
Unfortunately the default power profile only saves power when the screen is off (or on battery I think). I also know of no GUI tools to manipulate the power profile. Here is the command I found to change the profile using sysfs:
sudo -i 'echo low > /sys/class/drm/card0/device/power_profile'
The change is not persistent, but the quoted part can be added to e.g.
/etc/rc.local to get it every boot. (I'm unsure about suspend, which I
don't use.)
My Radeon HD 4850 has enough power for desktop effects at the lowest power level, lower end cards may work better with the mid level profile.
To see current power and voltage info, here's another command:
cat /sys/kernel/debug/dri/0/radeon_pm_info
In looking for a data structure for a memory management problem I tried to find a self-balancing tree that would use as little space as possible. The only one I found from Wikipedia that didn't require any additional information at nodes was the scapegoat tree.
Unfortunately, it's not as easy to implement as the intro suggests. As a further complication, a scapegoat tree has some additional information at the root, which means one cannot use a subtree node as a tree for certain operations. Similar reasons made rb-trees unattractive.
Since I had already used treaps before, I thought I could create one without storing the priority, by basing it on a hash of the key. Since the data I will use it on is fairly nonuniform and I don't need any kind of security guarantees, I used a very simple hash function by taking essentially a single round of MurmurHash on an integer key.
The result is a fairly fast self-balancing tree that is very easy to implement without storing any additional information anywhere.
Due to the space constraints I mentioned above, I left out parent pointers by trading for O(log(n)*log(n)) expected insert performance with (tail) recursive bubble up. In practice it's not very noticeable, since the data is in caches after the first descent and the number of hashes does not increase. I was going to work around that by using a stack, but didn't see a need to.
By tagging pointers I can further drop child pointers where not needed to get a total space use of n*(sizeof(key)+sizeof(void*)) for the whole tree. That's still TODO, though.
To make the wireless of my 1001PX work in Ubuntu Lucid I had to install the 2.6.35 kernel from Kernel team PPA. The package name is linux-meta-lts-backport-maverick and it should eventually become available in the Lucid package archives.
Unfortunately, the touchpad didn't support multi-touch OOTB and the option in Mouse Settings was disabled. Here are the xinput commands I put in /etc/rc.local to get multi-touch scrolling and click emulation. They should work in other Linux OSes too:
TOUCHPAD="SynPS/2 Synaptics TouchPad" xinput set-prop "$TOUCHPAD" "Synaptics Two-Finger Pressure" 4 xinput set-prop "$TOUCHPAD" "Synaptics Two-Finger Scrolling" 1 1 xinput set-prop "$TOUCHPAD" "Synaptics Tap Action" 0 3 0 2 1 3 2
The three-finger-click doesn't work very well, so I have the bottom corners also emulating different clicks.
Now the only problem is getting the fan under control. It almost never spins up in Windows, but is constantly on in Ubuntu.
I finally have Ubuntu Lucid looking like I want it to. First a couple of screenshots and then some linking to the relevant packages etc. Here's the desktop with Firefox open.
{.alignnone
.size-medium .wp-image-174 width="300"
height="187"}
And here I've marked some customizations in the image. (Apologies for
ugly text.)
{.alignnone
.size-medium .wp-image-173 width="300"
height="187"}
Firstly, I want my panel (singular) vertically. That is unfortunately buggy with the Ambiance theme (Bug #534582) and indicators (Bug #533439). The latter does not look too bad, but the former had to be fixed with the instructions from Bug #160311: Remove the image from the theme gtkrc, set the scaling properties in gconf-editor and set the background image manually.
Instead of the menu bar, which does not like a vertical panel, I use Cardapio from the PPA. It has lots of great plugins for e.g. Google and Wikipedia searches, though I haven't really used them.
Replacing both the window list applet and launchers I have DockbarX from the PPA. The theme is Minimalistic and I have enabled Compiz previews and Opacify.
In the lower right corner I have Conky (from Universe), which I use to monitor the computer.
Firefox is still 3.6 (the default), since I'm refraining from Firefox 4 beta testing until they get their Linux version up to speed. Addons I use include at least:
I look forward to trying Lucid out on the laptop I just ordered.