gorithm

my very educated mother just served us noodles

I'm a little sad to see Pluto demoted as a planet.  The key question is how we update:

my very educated mother just served us nine pickles

The Economist, always on the forefront of important issues, suggests:

my very educated mother just served us noodles

Kottke had a contest for a planet mnemonics, with this excellent winner (using nine planets as a protest):

My! Very educated morons just screwed up numerous planetariums.

Amazon's EC2 is pretty cheap

Amazon announced a limited beta test of a new on line utility computing service.  For $0.10/CPU hour, you can setup and run any number of virtual servers.  That works out at $876 per CPU year.  That's a bit more than you'd pay for a dedicated server, but the cool thing is that you can (at least in theory) have 1000 servers one day when you need them, and none the next. I wonder how many real servers they have at their disposal.

Kevin Werbach has an article about it here.

Tim Bray likes Ruby

I'm intrigued by the programming language Ruby.  I'm on the cusp of breaking down to start using it.  Tim Bray (of Sun) has some interesting posts on his blog, as he starts to learn the language.

While on the subject of Ruby, the Ruby Weekly News website is a good summary of the relevant mail lists, for the interested lurker.

Google's MapReduce algorithm

The New York Times had a good article a while back about Google's hardware and software infrastructure.  It said that one of their big innovations was an algorithm called MapReduce:

One such program, called MapReduce, is based on ideas discussed in computer science literature for decades, according to Urs Hölzle, Google's senior vice president for operations. "What surprised us was how useful it turned out to be in our environment," he said.

MapReduce, he said, "allows Joe Schmo software engineer to process large amounts of data and take advantage of our infrastructure."

Mr. Arnold, the consultant, said these tools created a significant cost advantage. "If you talk to guys who work in massively parallel computing operations, as much as 30 percent of their coding time is spent trying to figure out how to get the thing to run," he said. Google "has figured out how they can reduce a lot of the hassle and work of creating parallel applications."

Mr. Gates acknowledged that MapReduce was a significant technology, but he asserted that Microsoft was building its own parallel processing software, opening another front in the technological war between the two companies.

"They did MapReduce; we have this thing called Dryad that's better," Mr. Gates said. "But they'll do one that's better."

Anything with such a snarky quote from Bill Gates has got to be interesting.  So here's the paper that describes it.  It is an interesting approach to parallel computing, well worth a read.

Polynomial time simplex algorithm for linear programming

Our office is just a block away from MIT. That's nice, because I can go to the library and seminars.  The most interesting seminar I went to at MIT this year was probably one on a polynomial time simplex algorithm for linear programming:

Algorithms and Complexity Spring 2006
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Speaker: Jonathan A. Kelner

In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope. Our analysis rests on a geometric statement of independent interest: given a polytope $A x leq b$ in isotropic position, if one makes a polynomially small perturbation to $b$ then the number of
edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.  This is joint work with Daniel Spielman.

If time permits, I will also discuss recent extensions of this result with Evdokia Nikolova.  Using tools from random matrix theory, we extend the technical tools from the above work to provide a smoothed analysis of an algorithm to solve a wide class of non-convex optimization problems.

There have been polynomial time interior point algorithms for solving LP's, but variants of the simplex algorithm have always had exponential time in the worst case.  (Those damn Klee-Minty Cubes...) It has been an open problem for decades.  Now he just needs to make it strongly polynomial.

It was one of those seminars that you don't really follow, but it sure seems important.  He defended this thesis this week, so contratulations to Jon.  I'm sure he'll get a nice academic post. 

His website, with papers and such is here.

Good language shootout article

As someone who writes in C++ because it is fast, and Mathematica because my brain likes it, I'm always on the lookout for good langauge comparision articles.  I really liked this one, by Steve Yegge of  Amazon.

It comments on C, C++, Lisp, Java, Perl, Ruby, and Python.  I love this quote on C++:

With that said, it is obviously possible to write nice C++ code, by which I mean, code that's mostly C, with some C++ features mixed in tastefully and minimally.  But it almost never happens.  C++ is a vast playground, and makes you feel smart when you know all of it, so you're always tempted to use all of it.  But that's really, really hard to do well, because it's such a crap language to begin with.  In the end, you just make a mess, even if you're good.

How a statistical formula won the war

Keeping with the topic of geekiness from my last post, here an excellent article for the statistics geeks out there.

The Guardian has a story about how statisticians used the serial numbers of captured tank in WWII to accurately estimate the number of tanks being produced by the Germans.

Our Geekiness makes us interesting

Maryam is confusing the two separate concepts of geeks and nerds in her post Girls and Geeks:

Geek to me stands for someone like my husband, addicted to his gadgets and his email and his Internet connection, very intelligent when it comes to machines, technology, and Internet and not so savvy when it comes to dealing with people, fashion and emotions.

I am lucky enough to know many smart and technologically advanced women, but I don't categorize them as geeks even though they are as good as if not better than any male geeks I know when it comes to dealing with computers. I guess what I want to say is that women as hard ass as they can be in the technical field still have some RAM left for the soft stuff. They are more than just geeks. Is my logic flawed? What do you all think?

People who have deep interests in a topic are geeks, those lacking in social skills are nerds. You can have one without the other. Geeks like to keep the distinction clear, in order to preserve our self-esteem.

You can be a geek either by the obscurity of the topic or by the depth of your interest. If you are into making miniature clay food for doll-houses like my friend Lexi, then you are probably a geek. You can also be a geek in more mainstream topics like computers and gadgets if you have a deep, almost obsessive interest. For that matter, if you care enough to take vacation time off to go to a conference (like say Blogher), then you are probably also a blogging geek.  I heard a guy on NPR who's hobby is studying transcripts of cockpit voice recorders of plane crashes, which is just spectacularly geeky.

There are many types of geeks. You can be a computer geek, gadget geek, knitting geek, wine geek,  or antiques geek.  If you run a single topic blog on _____, then you are almost certainly a _____ geek.

In contrast, there is really only a single type of nerd.  Nerds are lacking in social graces, have trouble communicating with people, dealing with emotions, and general human interaction.  Sometimes excessive geekiness can lead to nerdiness because you are so obsessed by your interests that things like human contact and personal hygiene fall by the wayside. 

I personally think that geekiness is what makes us all interesting.  It is certainly a good thing to be a geek, but not a nerd.  I've certainly known both men and women in each of the four categories: non-nerd geek, non-geek nerd, nerdy geek, and non-nerd non-geek (a.k.a. normal, boring person).  It is probably true that nerds are more likely to be men.  Men tend to be geeks in certain topics like computers, but if you account for the fact that you can be a geek in anything, I'd say men and women are equally geeky.

I think what Maryam was saying was that she knows many non-nerdy computer-geek women, while many of the nerdy computer and gadget geeks she knows are men. [Of course, just because most nerds are men, this does not mean that most men are nerds.  So Dave, a non-nerdy geek can rest easy.]

[Just to be confusing, some groups of people reverse the usage of these two terms.  The CS department at Carnegie Mellon reversed the terms when I was there (geek=bad, nerd=good), while my Chemical Engineering department used the terms properly (geek=good, nerd=bad).  Keep this in mind if you're discussing the geek/nerd difference.]

Tesla Motors: I want one

If you haven't read about Tesla Motors, you should. 

They're shipping $100k electric sports cars that go:

0-60 in 4 seconds.
Top speed of 135MPH. 
Top speed in reverse is 135 MPH. 
Built by Lotus in England. 
A 250 mile range between charges. 

Remind me again why the Big 3 can't build electric cars, or cars with decent mileage?

Even better, their next car will be a sporty four seater for under $50k. In 2008, long before GM will have anything.

Interesting functional programming article

Here's an interesting article I'm going to have to come back and digest when I have more time...

Everything Your Professor Failed to Tell You About Functional Programming