Wednesday, March 14, 2007

Help me figure out an algorithm?

CNN Money has a neat page that lets you "rank your goals" (up to 15 of them) by pairing them up and asking you to choose between them.*

I was surprised that the option of having a family someday (not like I'm, y'know, dying to marry and settle down, but that I want to have that option if the right person comes around) ranked so highly, and that graduate school ranked so low. I suppose if I'd put "become a professor" instead it would have pulled it up some, but there are many things I value more than formal academic credentials. (Sherra Kerns tells me that I've got to at some point "pay my dues" if I want to be an engineering prof at a top-notch school. I told her yes, but that I wasn't ready to pay them right now.)

Anyhow, my randomly generated list, which is a rather poor approximation of what I'd actually like to do with my life... but makes for an interesting set of information anyhow.

Rank/Item Score
1. teaching others without financial compensation
2. starting the yellow house
3. perhaps having a family someday
4. being able to donate my time to nonprofits
5. the ability to schedule my own day
6. being able to write books
7. traveling around the world
8. starting my own company
9. going to graduate school
10. guaranteed income stream
11. a comfortable retirement
12. having cool computer and music stuff

*yes, I did go back and try to figure out what sorting algorithm they're using in the 5 minutes before my next meeting. My first thought was quicksort, but the big-Oh is less than n^2 log n and more than n log n. I've got to run now but I'd like to puzzle this through - I don't think it should be this hard but my brain's fried from not sleeping for two weeks... any suggestions?

Big-O table, for reference
# of items : # of questions
2 items = 1 question
3 items = 3 questions
4 items = 6 questions
5 items = 10 questions
6 items = 15 questions
7 items = 21 questions
8 items = 28 questions
12 items = 66 questions


David Klempner said...

Spoiler: (you're not going to like this)

Fvkgl-fvk vf gjryir pubbfr gjb

On the other hand, this poses an interesting question: what sort of efficient algorithms could one build for this sort of question? (Conversely, what restrictions do you need to make an efficient algorithm?)

Remember that this really is not transitive, so a naive sort will not give you the results you expect.

Mel said...

Argh, I should have thought of that first. Occam's razor! Thanks, David.

Played around with messing up the transitivity; it looks like every "vote" you give a choice adds weight to it (with each choice coming up for an equal number of votes) and the choices are sorted by number of votes in the end (in other words, you have ties).

This would make a neat problem for an intro CS class. Or an interesting psychological probe; ask people to write down life goals #1-10 on separate index cards, then to sort them, and watch what algorithm they use (me: quicksort for n > 20, insertion for anything below that).