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.
MarkCC May 28, 2008 Data Structures
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.
MarkCC May 27, 2008 Uncategorized
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…
MarkCC May 20, 2008 Bad Math Education
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.
MarkCC May 13, 2008 Bad Physics
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.
MarkCC May 7, 2008 Graph Theory
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.
MarkCC May 6, 2008 Bad Statistics
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.
MarkCC May 5, 2008 Game Theory
The games that we’ve looked at so far are the simplest case of
basic games. In these games, we’ve got a payoff matrix, and both players
can see the whole matrix – the players have equal information,
and nothing is secret. The players move simultaneously – so neither player can wait to see what his opponent does before making his own decision. Finally, the game is played exactly once – there are no repetitions.
The first complication we can add is to make it an iterative game – that is, instead of each player going once, they’ll repeat the game 10 times in sequence. Everything else stays the same: perfect, equal information, simultaneous moves, etc.
This creates an interesting added dimension. Now, we’ve got two layers
of strategy: each iteration, each player selects a strategy; and then there’s an over-arching strategy that they use to select their strategy each iteration. That over-arching strategy is called a grand strategy
In an iterated game, the optimal solution for players can be different than in the single iteration. The goal is to maximize your total utility at the end of a series of iterations. It’s OK if some iterations result in a loss of utility, so long as by the end of the series of iterations, the final
sum of the utility of the series is maximal.
Pardon me, while I go off on a rant. Since I came to work for Google, I have a pretty long commute. Most of the time, I don't really mind…