Cool talks to play in class

Last semester I decided (for the first time) to give up an entire lecture to playing a talk I thought was just too good to ignore. Since then I've realized that there are several "cool talks" out there that fit a variety of courses I teach, and so I plan to collect them. Maybe others will find them just as cool?

So for this first post in the series, the talk that started it all. I played this one in "Computer Systems Fundamentals" which is an introductory systems course at JHU that covers (among many other things) microprocessor design and assembly level programming. The talk covers the MOS 6502 in a variety of ways, but the real "cool-factor" comes from the reverse engineering efforts described and demonstrated toward the end. Kudos to Michael Steil!

Annoying Heisenbug: Wavemon breaks NetworkManager

I installed a new wireless router today, one of my Christmas presents finally put to use after sitting in the proverbial box for way too long. Being ever the diligent geek, of course I needed to measure how good the reception is around the house. I looked for a tool that would show me the signal strength of my wireless network on my netbook and found wavemon. The tool seemed to work rather well and allowed me to verify that even in the basement I still get 60% signal strength. Not to shabby for a router sitting on the second floor, is it now?

So I went back upstairs to configure more of the many confusing options dd-wrt provides only to notice that my netbook would intermittently drop its wireless connection. I'd open Chromium to look something up and things would just time out, then suddenly NetworkManager would pop up and request that I enter the admin password followed by the wireless key again, sometimes four times in a row. Then the connection would work for a few minutes before falling to pieces again, yada yada.

I was starting to get rather annoyed by this. Another laptop in the house was having similar problems with the previous wireless router, the very reason I got a new one. Of course that laptop now connected fine with no more problems, but for some reason my netbook which had always worked perfectly on the old router had "caught the bug" and would now not stay connected for more than a few minutes at a time. I kept double-checking what the router said about the connection to my netbook and what wavemon said (running in my netbook) about the connection to the router. Things were just messed up, and all kinds of theories started developing in my head about what could be wrong with Lubuntu 12.10 and NetworkManager and wpa_supplicant and the driver for my strange wireless card, etc. etc. etc.

What never occurred to me was that by desperately looking at the connections using wavemon, a tool used to measure stuff, I was actually causing all this trouble! When I shut down wavemon the network become wonderfully stable. When I started wavemon again, after a minute or two, it started misbehaving. The very definition of a Heisenbug (well, in this case an inverse Heisenbug I guess): It's there when you look for it and gone when you don't. Apparently wavemon was overloading wpa_supplicant with requests for SSID scans (the logs seem to indicate something to that effect) but I didn't verify that in detail.

Now of course there could still be something else wrong, but I've repeated the experiment several times and over and over again wavemon will mess up the connection after a few minutes. My advice: Use that tool only to measure signal strength for a few minutes, then get rid of it and never try to debug your wireless network with it. Never!

Bottom line: About 2 hours wasted. Sigh.

Edit: Some helpful hints for debugging NetworkManager stuff:  https://wiki.ubuntu.com/DebuggingNetworkManager

Quick Note on Multiple Linux Installs

Never mind the details, but I had reason to look into how to put a bunch of different Linux distributions on a single machine without virtualization. In my case I wanted Lubuntu, Arch, and Gentoo on my netbook, with room for more if needed. The things I learned:

1. Do not share /boot across distributions, each distro you install should have it's own /boot for improved sanity.
2. Do not share /home across distributions, each distro you install should have it's own /home for improved sanity.
3. Pick one distro as the "safe and sound" one and install it first; you'll let this distro install GRUB2 and you'll use it to manage GRUB2 as you add more distros. So whatever you pick, make sure you know how to update GRUB2 correctly using that distro's configuration files and commands.
4. Have a partition for shared data. Think of this as what you were trying to accomplish when you thought sharing /home was a good idea. When each distro boots, have the shared disk mounted at a fixed place like /share or maybe /home/user/share or something (this assumes that you're the only user, very true on my netbook).
5. If you can avoid RAID, do so. If you can avoid LVM, do so. In fact, if you can avoid anything, avoid it. Try to keep things as simple as possible, but not simpler.
6. Make sure that in each distro you know how to create a user account with the very same user and group id (this once again assumes that you're the only user).

If you were expecting detailed instructions on how to proceed: sorry! But it's really not too hard to figure out. I just wish someone had this list of high-level hints posted somewhere before I started trying to make this work. Now you don't have that excuse anymore. :-) The one thing I will share though is my decidedly non-GPT partitioning scheme. It's not perfect, but it's what works for me so far:

• /dev/sda1 is the / for the "safe and sound" distro, Lubuntu in my case
• /dev/sda2 is the swap partition that all installed distros will share
• /dev/sda3 is the shared data partition that gets mounted under /home/user/share
• /dev/sda5 is the / for Arch
• /dev/sda6 is the / for Gentoo
• ...

LVM would allow you to grow/shrink things later, but I didn't want to bother with the trouble. I have a 160GB disk in my netbook and it was easy to decide that 32GB for each distro would be okay, which leaves 64GB. Take away another 2GB of swap and 16GB of shared data and I have 40+GB left to grow. Not much, but not likely that I'll really need it either.

EDIT: In retrospect I think it would be a good idea to use a rolling release distro for the "safe and sound" one, so I'll probably switch to Arch for that eventually.

Why Geeks Don't Like You: A Hint for United Way of Central Maryland

Like many others around here, I am fairly used to getting spammed about this that or the other United Way campaign at my JHU work email. I've made my peace with it, after all configuring a spam filter isn't all that complicated. Of course a more appropriate solution would be for the spam to stop, but I decided a while ago that it's not worth picking a fight over.

In any case, every now and then something from United Way gets through. Tonight I received an email from

Nicole Lipinski <nicole.lipinski@uwcm.org>

 

asking me to please donate money like I had in previous years. Now I have actually never donated to United Way, ever. It's not like I don't believe in charities, I just prefer to donate to other charities, maybe even some that don't spam me. 

 

But what the heck, I thought I'd take the time to point out to someone at United Way how I feel about the spam I get: I hit reply and explained briefly and politely that I am not donating and that it would probably help them with the geekier population around JHU if they stopped spamming us. I was a little surprised when I got back the following:

550 No Such User Here

Huh? You can probably guess what happened next. In a slightly less friendly tone I contacted

postmaster@uwcm.org
abuse@uwcm.org

to complain about them sending me email from a completely fictional email address, one of the hallmarks of any self-respecting spammer. Then what happened?

550 No Such User Here
550 No Such User Here

You better believe it. Never mind that RFC 2142 clearly states that both of these addresses have to exist if you run SMTP on your host. So the next thing I do is check their whois record where I find two more email addresses:

webmaster@uwcm.org

dataprise@uwcm.org

Of course I had little hope by now that they would follow RFC 1834 any better than they had followed RFC 2142, and predictably I got back two more of these:

550 No Such User Here
550 No Such User Here

I don't know what the IT people over there are thinking. Maybe something like "Those rules only apply to old-fashioned business organizations, but we're a lean-and-mean donation-gathering-machine so we don't have to follow those weird RFCs!" Whatever it is, I can pretty much guarantee that this kind of ignorance in setting up their email infrastructure does not reflect very kindly on them. At least not from where I sit: deep geekland. Now excuse me while I tighten up that spam filter a bit more.

Those Curious Python Operators

Alright, so Python still surprises me every now and then. Here's a fun one that I stumbled across by accident today:

>>> 0 == 0 == 0
True
>>> 0 == 0 == 1
False
>>> 0 == 1 == 0
False
>>> 0 == 1 == 1
False
>>> 1 == 0 == 0
False
>>> 1 == 0 == 1
False
>>> 1 == 1 == 0
False
>>> 1 == 1 == 1
True

Did you expect that? I sure didn't. But I guess Python is famous for "special casing" its operators to avoid confusing beginners in several places. So they end up confusing people who know lots of other languages instead. Here's what I would have expected to happen (but Python only does this with explicit parenthesis):

>>> (0 == 0) == 1
True

Good times! :-D BTW, in case you were wondering, another place where Python does the "right thing" despite what you may expect coming from C and similar languages: 14 < i < 99 actually does the proper range check, and not by accident either.

AVL Trees Turn 50

I am teaching 600.226: Data Structures as a summer session course right now, and we covered AVL Trees yesterday. As I was ranting about them I suddenly realized that they were first published in 1962, and here I am in 2012 still teaching them to my eager (and somewhat perplexed) students.

So blame my brain: I have never been able to develop a good intuition about red-black trees (which I gather is what "respectable" schools are supposed to teach). My favorite balanced trees are treaps anyway, because they take so little code yet perform so well. But I feel that I "owe" my students at least one deterministic balanced search tree, and 2-3(-4) trees are just so messy to implement. Hence AVL!

I started to wonder: Since AVL trees were published in 1962, were they the first efficient data structure for ordered sets or maps? So I did some checking, and here is what I found:

AVL Trees 1962
B-Trees 1970
Symmetric Binary B-Trees 1972
Finger Trees 1977
Red-Black Trees 1978
Splay Trees 1985
Treaps 1989

If we losen things up a bit and include things that either demand more of the data or provide fewer general operations, we could consider these as well:

Tries 1960
Heaps 1964

So as far as I can tell after a quick search, AVL Trees are indeed the oldest efficient way to maintain a dynamic ordered set or map. And since students still have some trouble implementing them today, I guess that means we either haven't made a lot of progress, or we should take our proverbial hats off and nod a quiet "Thanks!" to Adelson-Velskii and Landis for figuring out how balanced search trees should work before most of us were even born.

One or two rolls in D&D-variants?

Let's look at how (simple) combat works in (classic) D&D variants. There's an attacker of a certain level and a defender with a certain armor class. The attacker makes a roll, modified to take into account the attacker's physical capabilities as well as the situation the attack is made in. If the attacker hits, the attacker rolls damage which the defender subtracts from hit points. Not very complicated, is it?

Note that there's one roll for the attack and one roll for damage if the attack succeeds, that's it. Specifically, the defender does not make a roll to see if the successful attack can be evaded somehow. (And neither is there a roll to avoid some of the damage.)

Now let's look at how (simple) spells work in (classic) D&D variants. There's a caster of a certain level and a target of a certain level. (There are spells in which one or the other level doesn't matter, but that's besides the point.) Provided the caster doesn't get distracted while casting, the spell will be cast successfully. Now the target gets to make a saving throw against the spell. If the saving throw fails, the full spell effect applies to the target; if the saving throw succeeds, only some or none of the effects apply to the target.

Note that there's again one roll, but this time the roll tells us whether the defense was successful. (There may also be a roll for damage made by the caster, ignore that.) Specifically, the caster does not make a roll to see if the spell worked or fizzled somehow.

But now look at surprise. Surprise! There is both a chance to be surprised and a chance to surprise someone else. Details vary by which version of D&D you're looking at, but they all seem to maintain that both sides get to roll for both things. Having both sides roll dice in this situation but not in the other two situations seems rather odd. (I have no problem with the fact that the first two use a d20 and the third uses a d6, that's not the point.)

There are other places where a "let's use two rolls" mechanic has crept into D&D, for example when trying to disarm someone: You have to hit, but then the defender gets a saving throw to avoid dropping their weapon. There are also places where two rolls actually make sense in a way, for example for spells that require touching the target with a successful attack.

Now some people may just not care and some may say "different mechanism for different tasks are a-okay" or something close to that. But for myself, I would prefer a clear line throughout the whole system: Either use two rolls consistently, or use a single roll consistently, but don't jump back and forth. Opinions?