• Vanity of Vanities, all is Vanity » Blog Archive » The diameter of the bomb was thirty centimeters
• Cool Tool: Beyond Bullet Points
• Cool Tool: Behind Bars: Surviving Prison
• Cool Tool: Networking on the Network

• Advanced Energy: Comfort Capacity in a Tri-level Home
  (tags: tri-level heating)
• HVAC-Talk: Heating, Air & Refrigeration Discussion – Funny A/C behavior
  reference to temperature sensors and rrdtool
• Ask the Expert
  tips on insulating trilevel crawlspaces

• HD Sports Guide – College Basketball in HDTV
  Wish I had ESPN2HD…
  (tags: espnhd ncaa basketball hdtv)
• pcHDTV
  Source for OTA HD tuner card?
  (tags: hdtv pvr)

There are two maxims that I strongly believe will solve, or directly lead to solving, all of the world’s issues. Everything can be addressed after you take care of these two issues:

• Provide everyone with affordable (or free) health care.
• Provide education opportunities to everyone who wants them.

How you go about providing those issues is complicated, and involves a better understanding of politics, economics, and big business than I currently have. I don’t think that plan is Democratic or Republican — it’s just smart, and makes everything else petty. Everyone’s worrying about social security and retirement, when the main costs the elderly will have to face involves the super-inflating cost of medical care and prescription drugs. If you remove those costs, suddenly their monthly stipend doesn’t seem so bad.

As for education, I’m always enlightened when I hear about loan incentives or anything good to help people who want higher learning to get schooling. Kalamazoo High School grads will get free in-state tuition. For a pilot study, that’s pretty neat. I hope the school district can cope with the influx of students that’s going to create — it’ll be a shame if the post-high-school opportunities are so great but the primary and secondary schools suffer with too few teachers, resources, libraries, programs, etc.

(The third maxim I didn’t mention above, would greatly help our society, involves penalizing frivolous lawsuits. Hot coffee will be hot. Eating unhealthy food will make you unhealthy. Cigarette smoking will kill you. I don’t know a good defintion for frivolous that would hold up in court, but we need to define one, and then slap the people who cause all these nuisance suits with a you’re-wasting-resources countersuit. You better hope you win your original suit, otherwise there will be stiff penalties (money and/or jailtime) for being irresponsible. Maybe a few years of that program would move society away from its wasteful, litigious habits and let people focus on providing new goods and services without fear of being sued for every harmless stupid thing.)

I’m finally getting the desktop PC at home setup, and I want to make some backup copies of my personal files. I have a DVD burner, but I’ve never bought any media for it. Usually, with CDRs, I keep an eye out for the $1 after rebate spindle of 25 or 50. That might only happen a few times a year, but I don’t go through that many CDs that it’s okay, and the rebate bit doesn’t bother me. If anyone sees any good deals for DVDR (DVD+R or DVD-R) media, please let me know.

(Those not interested in puzzle solving or computer science might want to skip this one.)

Let’s say you’re trying to write an algorithm that generates a distinct 1:1 mapping between two sets of n numbers. This mapping is built dynamically, selected randomly, and stored between events.

One solution is to generate all the random mappings at one time, 1 to n. This is effective and easy, but wastes space, especially if few of these numbers are ever looked up.

Another solution is, when you first encounter an unmapped number, randomly select a number 1 to n, check that the random number you chose is not being already used for a mapping for another number, and if not, store the mapping.

This works pretty well, up to a point. Let’s assume n=10. On your first unmapped number, any number 1 to 10 will work. On your second unmapped number, randomly you’ll still pick 1-10, but you’ll have a 10% chance of picking the number you picked for the first number. When that happens, you pick again 1 to 10. If that number is available, store it, and move on.

This works as long as you don’t need to generate a mapping for all of n (just some numbers in n.) When you try to pick the nth number using the random algorithm, there’s only a 1/nth chance of selecting the last available mapped number. This means in theory you have to pick n times for the nth number — in practice, I have a hunch it’s much worse than that.

At some point, it makes sense to fall back to the first algorithm – generate a list of known original numbers and their mappings, take from that the yet-unmapped original numbers, and the pool of available to-be-mapped numbers, randomly order the to-be-mapped numbers, and apply them to the rest of the pool. This sounds like better approach than hoping the nth mapping random mapping will pick the last remaining available number.

But where is this cutoff between randomly selecting a single element, versus iterating over all the previous selections and completing all the outstanding mappings? Do I make the call on the percentage of n completed? (For example, after n/2 elements, iterate over the rest.) That seems wasteful if I’m only going to use (n/2)+1 variables, and the effeciency of the random algorithm might not decay until much later.

Or, instead of looking at basing the cutoff on the percentage of n, base it off how many random retries any mapping requires. If there are too many collisions, no matter where it lies in n, quit the random approach and iterate over the rest. (For example, for any number in n, if it took more than n/2 tries to pick an available number, assume the random algorithm has failed you, and iterate.) But that’s a harder cut off to determine….

It makes sense that after n/2 the per-random selection will less efficient for each new number. I hypothesize that the cost of the iterative algorithm at that point will be less than letting the random-selection one continue as the number of available options decreases. But what about stopping it after x retries? This might only happen on the last few elements, if x was high enough… It could also happen before n/2 and in that case you ate up a bunch of space you didn’t need.

Which approach do you think is better, and where would you make the cutoff?

Is it me, or are the FunSize Snickers bars smaller than they used to be? As in, the packaging might be the same, but the bars seem small in the wrappers. These used to be the size of my thumb, now I think they’re skinnier and shorter in all dimensions. Am I crazy, or anyone else notice this too?

Congratulations to Jeff Erickson who was highlighted in the latest edition of Illinois Alumni Magazine as a great CS prof. He, I guess, slipped the interviewer my name, and she called me for a phone interview.

The piece released today. (Local copy) (And coming soon in glossy print to a coffee table, bathroom reading bin, and birdcage near you!) See page 12, or search for my or Jeffe’s name.

The article did a decent job of stroking, but I don’t think Amy Reiter, the author, did a good enough job explaining how complicated some of the theories Jeff teaches are, and how plainly and easily he does it. This is mind-twisting stuff, and he makes it fun. I would have made the following emphasis points in my quotes: one fluid motion As in, blink and it’s done. Your fingers mesh, they unmesh, your shoe is tied. (Jeff, if you want to thank me for the interview, I need a refresher on how exactly you do that.) The other point was the then-300-level theory course was the pinnacle CS theory course. It’s the hard class you take. This is the class whose syllabus’ vocabulary sends fear and doubt into the meek.

I didn’t bother trying to explain to her that if I could solve minesweeper in polynomial time, the universe would implode itself. I’m not sure that would have impressed her, (kinda like my label maker,) and so I think that knowledge is best served in the hands/minds of those of us who will solve minesweeper in P. Oh, yes. We will.

I’m surprised how often I was quoted/referenced in the article. (Counting it up, Jeff has three times as many direct quotes, so I guess it’s okay.) As an alumni magazine, I guess they cover all interests when they get an alum to talk about current professors. Even more bases when that alum is a full time academic professional who’s also a grad student.

Anyway, congrats Jeff. Today, I’m quoted in an alumni magazine! Now to work on getting referenced in an academic journal! (I have to work on lowering my Erdos number. Unless Jeffe has one, and the alumni mag counts, lowering mine from infinity to Jeffe+1.)