One thing that I’ve been getting a lot of requests about is the ongoing

mortgage mess in the US. I wrote a bit about it a while ago, explaining

what was going on. But since then, I’ve gotten a lot of people asking

me to explain various things about how mortgages work, and what kinds

of trouble people have gotten into.

# Monthly Archives: May 2008

# The Basic Balanced Search Tree: Red-Black trees.

During my Haskell tutorial, I used balanced binary search trees as an example. I’ve had people write to me asking me to write about that in a non-functional

programming post, because the Haskell one got too tied up in how to do things

without assignments, and with tail recursion.

Binary search trees (BST) are another one of the really fundamental simple data

structures. They’re conceptually similar to heaps – they’re also a kind of size-ordered binary tree with O(lg n) performance – but they’ve got a different set of basic invariants to represent the different performance goals.

The goal of a structure like a BST is to have a variable-size stucture where

you can cheaply and easily increase or decrease the size of the structure,

and where insert, delete, and searching for values are all inexpensive. BSTs

are a good choice for implementing things like dictionaries, where you have a key associated with a value, or where you want to be able to search for an arbitrary member quickly.

BSTs are very widely used – for example, the default ordered collections, sets, and maps in the C++ standard libraries are all implemented as a kind

of BST (in fact, the very kind that I’m going to describe below.)

If you have a meaningful ordering operation, then a BST is a good choice: expanding and contracting the structure happen automatically every time you do an insert or remove; and insert, delete, and search are all bounded by lg(n), where N is the number of values in the tree.

Continue reading The Basic Balanced Search Tree: Red-Black trees.

# Mars Probe Parachuting Velocity

As you’ve hopefully all heard by now, the Mars Phoenix lander made a perfect

landing over the weekend, and is already returning images. NASA managed to not

only achieve a perfect landing, but to use Mars reconnaissance orbiter to catch a

picture of the Phoenix descending with parachutes deployed!

Alas, NASA’s Phoenix press people aren’t nearly as good as its technical people. As an alert reader pointed out, in their press release about capturing

the photo of the probe with parachute deployed, that they said the following:

Phoenix released its parachute at an altitude of about 12.6 kilometers (7.8 miles) and a velocity of 1.7 times the speed of sound.

That looks relative innocuous, right?

Wrong.

The statement about velocity is *meaningless*.

The speed of sound isn’t a constant. It varies, enormously, depending

on the medium. In air, its speed is dependent on the chemical makeup of

the air, and on its density, temperature, and pressure – among other factors. So what speed of sound are they talking about?

The speed of sound where the probe was entering the Martian atmosphere? That would make sense as a measurement, but be totally uninformative to us back on

earth, since we don’t know the speed of sound in the upper atmosphere of Mars.

The speed of sound on earth? That would be informative to us – since we

have an idea of the speed of sound here, but it wouldn’t make much sense as a measurement there – the point of using the speed of sound would seem to

be related to giving us a sense of the kind of forces acting on the Phoenix

as it decelerates. But the speed of sound on earth doesn’t tell us that – because the kind of shock waves we would expect is dependent on the speed of sound in the atmosphere it’s passing through.

You can talk about speeds compared to the speed of light – because there’s a meaningful upper bound – the speed of light in a vacuum. And that’s what we usually mean when we talk about the speed of light. But with sound, that’s not

true. The speed of sound can vary quite dramatically in different mediums. It’s a big enough difference that it’s part of a common experiment done by

elementary school students! (I can remember doing an experiment in fourth grade science with a wall, where we were measuring when you could hear a rock hit a wall; one person had their ear against the wall; the other was standing a couple of feet away from the wall, and the person with the rock was about 10 feet away. The time difference was noticeable. It was very small – but distinctly noticeable. The speed of sound in air is 1260 feet per second; so a sound takes roughly 1/10th of a second to move 100 feet. The speed of sound in stone is in the range of 21,000 feet per second – which is virtually instantaneous to a human being at a range of 100 feet. So you’re looking at a roughly 1/10th second difference.)

So how fast was the Phoenix moving when it deployed its parachute? I haven’t

a clue. My best guess would be around 580 meters per second – assuming that

they were using the speed of sound in earth atmosphere at standard temperature and pressure. The speed of sound in the Martian atmosphere – which is quite a lot thinner than earth’s – would be slower, so 580 m/s is a decent upper-bound estimate.

# Stupid Grading Tricks

A bunch of people have been mailing me links to an article from USA today

about schools and grading systems. I think that most of the people who’ve

been sending it to me want me to flame it as a silly idea; but I’m not going to do that. Instead, I’m going to focus on an issue of presentation. What they’re talking about could be a good idea, or it could be a bad idea – but because the

way that they present it leaves out crucial information, it’s not possible to meaningfully judge the soundness of the concept.

# Bad Gas Math

This has been mentioned elsewhere – like on the Machinist blog on Salon (where I first saw it) – but I can’t resist saying something about it myself. And I’ll also chip in a little bit of originality, by also criticizing some of the people that I’ve seen criticizing it.

The story is, there’s a scammy company that sells a rather expensive device that allegedly increases your gas mileage. The way that it (supposedly) works

is that it uses electricity from the alternator to get hydrogen by splitting

water, and then adding that hydrogen to the air that gets mixed in the engine. The argument is that the hydrogen causes the gasoline to burn more completely and more cleanly, thus increasing the efficiently of the engine, which allows it to go further on a gallon of gasoline.

A local TV station in Florida claims to have tested the device. They tested the mileage of their news van using a dynamometer; then they mounted the device on the engine of their news van, and after giving it time to break in, put the

van back on the dynamometer, and tested its mileage again.

Here’s where the pathetic part comes in. They reported that before mounting the hydrogen generator on their van, they got an average mileage of 9.4 miles per gallon. After mounting it, they claim that they got 23.2 miles per gallon. Ok so far? Now, they go on to say that increasing their mileage from 9.4 to 23.2 mpg is a 61% improvement in mileage.

# Linear Programming

In my last post on game theory, I said that you could find an optimal

probabilistic grand strategy for any two-player, simultaneous move, zero-sum game.

It’s done through something called linear programming. But linear programming

is useful for a whole lot more than just game theory.

Linear programming is a general technique for solving a huge family of

optimization problems. It’s incredibly useful for scheduling, resource

allocation, economic planning, financial portfolio management,

and a ton of of other, similar things.

The basic idea of it is that you have a linear function,

called an *objective function*, which describes what you’d like

to maximize. Then you have a collection of inequalities, describing

the constraints of the values in the objective function. The solution to

the problem is a set of assignments to the variables in the objective function

that provide a maximum.

# Selective Data and Global Warming

One of the most common sleazy tricks used by various sorts of denialists

comes back to statistics – invalid and deceptive sampling methods. In fact,

the very first real post on the original version of this blog was a shredding of

a paper by Mark and David Geier that did this.

Proper statistical analysis relies on a kind of blindness. Many of the things

that you look for, you need to look for in a way that doesn’t rely on any a priori

knowledge of the data. If you look at the data, and find what appears to be an

interesting property of it, you have to be very careful to show that it’s

a real phenomena – and you do that by performing blind analyses that demonstrate

its reality.

The reason that I bring this up is because one of my fellow SBers,

Tim Lambert, posted something about a particularly sleazy example of this

by Michael Duffy, a global warming denialist over at his blog, Deltoid.

The situation is that there’s a Duffy claims

that global warming stopped in 2002. It didn’t. But he makes it *look* like it did by using a deliberately dishonest way of sampling the data.