Ernie's 3D Pancakes

About damn time!

The Illinois Student Senate is publishing instructor evaluations online. Finally.

No, I'm not listed. My department, toin its infinite shame wisdom, doesn't release that data. Apparently, we officially prefer students to look at less official sources.

Harmonic Hot Air

My PhD student Kevin Milans brought back the following fascinating puzzle from FOCS; I don't know who gave it to him Kevin heard it from Mohammad Mahdian. I'll pose a few warm-up questions (with answers below horizontal lines) before I get to the real puzzle.

You are given n balloons, which appear to be utterly identical. For each integer k between 1 and n, exactly one of the balloons can hold 1/k liters of air. You know that the balloons have these different capacities, but you do not know which ballons have which capacities. The only way to discover the capacity of a balloon is to overinflate it, causing it to pop. Your goal is to fill the balloons with as much air as possible. You don't get credit for the air you put into balloons that pop; only the surviving balloons count toward your total. How much air can you get?

---

It's not hard to find a strategy to capture 1 liter of air. For example, you could put 1/n liters in each balloon. Or you could try to put 1 liter in each balloon, potentially popping all but the largest. Or you could try to put 1/10 liters in every balloon; in the worst case, you pop all but the ten largest balloons. The second and third strategies could get you more than 1 liter of air, but you can't guarantee that you'll get more than 1 liter, so in a worst-case sense, none of these strategies is better than any other. Is there a strategy that guarantees more than 1 liter?

---

No. There is no deterministic strategy that always gets more than 1 liter of air in the worst case. Imagine that the capacities are not fixed in advance, but rather are determined by an all-powerful malicious aversary. The adversary uses the following simple strategy for each integer k: The first time you try to put more than 1/k liters of air into a balloon, the adversary gives that balloon capacity 1/k, and the balloon immediately pops. With this strategy in place, if there are m surviving balloons, each of them contains at most 1/m liters, so the total amonut of air in all balloons is at most 1 liter.

But what about randomized strategies? Can we guarantee an expected return larger than 1 liter?

---

Yes! Consider the case of two balloons. Choose one balloon at random and inflate it to 1 liter. If it survives, inflate the other balloon to 1/2 liter, for a total return of 3/2 liters. If the first balloon pops, inflate the second balloon to 1 liter, for a total return of 1 liter. Since you are equally likely to choose either balloon first, each of these two cases is equally likely, so your expected return is 5/4 liters.

We can generalize this idea to larger values of n by inflating the balloons in random order. Initlally, let i = 1. Pick up a random empty balloon and give it 1/i liters. If the balloon pops, shrug and move on. If the balloon does not pop, increment i. Repeat this procedure until there are no more empty balloons. At the end, the L largest balloons are fully inflated, for some integer L, and all smaller balloons have popped.

Balloon k (the one with capacity 1/k) survives if and only if balloons 1,2,...,k are inflated in that order, which happens with probability exactly 1/k!, because the order is chosen uniformly at random. Thus, our expected total return is at most ∑_k≥1 1/k·k! ≈ 1.3178 liters.

This is not the best strategy. Can you do better? (I'll post a better strategy in a few days.)

Is there a randomized strategy whose expected return is not bounded by any constant? I suspect the answer is no, but I don't have a proof. Yet.

Stuff I bought this weekend

• Dinner in Indianapolis with my brother-in-law, after finally seeing his amazing documentary In a Nutshell

• An Airport base station and Tetris shelves for my home office

• A midnight visit to the emergency room to have a 1mm splinter removed from the inside of my eyelid

Homeless?

Fellow algorithmist Herman Haverkort recently joined the ranks of the blogful. He already has several interesting posts up, on learning to give good talks, women in math and computing, and Dutch bureaucracy. More! More!

Malkovich. Malkovich. Malkovich. Malkovich.

My new filing technique is unstoppable

Boing Boing points to a description of an unconventional filing system proposed by Japenese economist Noguchi Yukio:

• All documents, regardless of their class, level of importance, or perceived chance of being required at a later date are stored in A4-sized envelopes, which have the flaps cut off[...] By "all documents," Noguchi means just that. He puts all categories of documents, including things like membership lists and his passport in envelopes.
  
• The title and date of the document are marked on the side of the envelope, as shown, and the envelopes are stored vertically on a bookshelf.
  
• Absolutely no "classification" of documents is attempted. The color coding is optional, and used only to shorten the amount of time to find a document.
  
• New documents (envelopes) are added at the left end of the "envelope buffer," and whenever a document is used (i.e., the envelope removed from the shelf), it is returned to the left end of the bookshelf. The result of this system is that the most recent (and frequently) used documents migrate to the left, while documents that are not used often or not used at all migrate to the right.
  

Algorithms folks should immediately recognize this as the Move To Front heuristic for dynamic list maintenance: After accessing any item in a linked list, move it to the front of the list. The cost of accessing an element of the list is equal to its rank in the list. So if you access the same item twice in a row, the second access has cost 1.

Moreover, assuming your file drawer has a fixed size, the Noguchi Filing System is also the same as the Least Recently Used paging algorithm buried inside every operating system on the planet: When your memory (or filing cabinet) overflows, throw away the page (or file) that you accessed least recently. The cost accessing a page is 0 if the page is in memory, and 1 if it isn't.

These are both classical examples of competitive online algorithms. An online algorithm is an algorithm that responds to a sequence of requests—for example, "Put this file in the drawer", or "Get my passport out of the drawer". The algorithm must handle each request as soon as it arrives. There is some cost associated with the algorithm's behavior—for example, the number of files that we examine. At the end of the day, we will most likely look back and realize that the algorithm made some sub-optimal decisions that led to extra work, but such wasted effort is inevitable. The algorithm can't look into the future; it has to handle each request immediately. Our goal in designing a good online algorithm is to minimize the amount of wasted effort.

This goal can be formalized as follows. Let A(X) denote the cost of online algorithm A on request sequence X, and let OPT(X) be the cost of the best possible offline algorithm, meaning an algorithm that knows the entire request sequence in advance. The competitive ratio of algorithm A is the maximum, over all request sequences X, of the ratio A(X)/OPT(X). If the competitive ratio is R, we call the algorithm R-competitive. We want this ratio to be as small as possible.

My poor departed high school English teachers are spinning in their graves at the ugly phrase "competitive ratio". After all, it's not the ratio that's competitive, but the algorithm. It really should have been called "competitiveness". But once the term was introduced, it stuck. Alas, we theoretical computer scientists aren't known for our L33t gr@mm3r 5ki11z.

In fact, both MTF and LRU are motivating examples in the paper of Danny Sleator and Bob Tarjan [pdf] that first introduced competitive analysis. Sleator and Tarjan proved the following theorems, among others:

• Move to Front is 2-competitive, and this is the best possible competitive ratio of any (deterministic) online list-access algorithm.

• Least Recently Used is M-competitive, where M is the number of pages that fit into memory, and this is the best possible competitive ratio of any (deterministic) online paging algorithm.
  

So no wonder the Noguchi Filing System is so attractive—in a very real sense, it's the best possible filing system!

Well, almost. We can do slightly better, at least on average, if we introduce some randomness. The following list-access algorithm, called BIT, is 7/4-competitive. Whenever you access a file that you've accessed before, move it to the front of the list. But the first time you access a file, flip a coin, and move the file to the front of the list only if the coin comes up heads.

Even this isn't the best algorithm known; another slightly more complicated algorithm is 8/5-competitive. On the other hand, the best lower bound known for the competitive ratio of randomized list-access algorithms is 1.50084, so there is still lots of room for improvement.

Academic Irrelevance

Malcolm "Tippy" Gladwell has an interesting piece in The New Yorker about the college admissions process, especially in Ivy League schools. The main point of the article is that schools like Harvard and Princeton do not set their admission standards to attract the best students, but to attract the best alumni, where (to put it bluntly) “best” means “most likely to give money to their alma mater”. Given the size of their endowments, the admissions officers at these places are obviously very good at their jobs.

Along the way, Blinky makes a couple of interesting side observations, neither of which is terribly surprising, but which both bear repeating. One is about the inflated perception of an Ivy League education. Getting into Harvard may be a good predictor of success, but actually going to Harvard doesn't seem to have that much impact.

To assess the effect of the Ivies, it makes more sense to compare the student who got into a top school with the student who got into that same school but chose to go to a less selective one. Three years ago, the economists Alan Krueger and Stacy Dale published just such a study [pdf]. And they found that when you compare apples and apples the income bonus from selective schools disappears.

“As a hypothetical example, take the University of Pennsylvania and Penn State, which are two schools a lot of students choose between,” Krueger said. “One is Ivy, one is a state school. Penn is much more highly selective. If you compare the students who go to those two schools, the ones who go to Penn have higher incomes. But let’s look at those who got into both types of schools, some of whom chose Penn and some of whom chose Penn State. Within that set it doesn’t seem to matter whether you go to the more selective school. Now, you would think that the more ambitious student is the one who would choose to go to Penn, and the ones choosing to go to Penn State might be a little less confident in their abilities or have a little lower family income, and both of those factors would point to people doing worse later on. But they don’t.”

Krueger says that there is one exception to this. Students from the very lowest economic strata do seem to benefit from going to an Ivy. For most students, though, the general rule seems to be that if you are a hardworking and intelligent person you’ll end up doing well regardless of where you went to school.

Later in the same story, Gladwell points out an excellent reason not to rely too heavily on standardized test scores for admissions.

In a recent research project funded by the Law School Admission Council, the Berkeley researchers Sheldon Zedeck and Marjorie Shultz identified twenty-six “competencies” that they think effective lawyering demands—among them practical judgment, passion and engagement, legal-research skills, questioning and interviewing skills, negotiation skills, stress management, and so on—and the L.S.A.T. picks up only a handful of them. A law school that wants to select the best possible lawyers has to use a very different admissions process from a law school that wants to select the best possible law students. And wouldn’t we prefer that at least some law schools try to select good lawyers instead of good law students?

Meanwhile, a Comical of Higher Education story describes some upcoming changes to the GRE.

According to David G. Payne, executive director of the GRE program, the changes are intended to make the test a more accurate gauge of how qualified prospective students are to do graduate-level work. "Oftentimes it's been a challenge to convince faculty members and deans that we're really measuring skills that are closely aligned with what they do," said Mr. Payne.

("Oftentimes"? Sheesh!)

Maybe that's because they aren't. Graduate-level work, at least in computer science, doesn't involve many multiple-choice exams. A significant fraction (but alas, not all) of my department's PhD admissions committee sees GRE scores as—at most—a bozo filter. A low quantitative score indicates that the applicant hasn't even mastered basic high-school math; that student probably don't have the necessary talent or preparation to be a successful computer scientist. But above that minimum baseline, the scores are just noise. Same with GPA. What's far more important in determining admissions is evidence of active independent curiosity: non-required advanced classes, independent study projects, non-boilerplate recommendations from faculty, intelligent questions in the statement of purpose, and so on.

We don't want to admit successful first-year graduate students [pdf]. We want to admit future successful computer scientists.

Sound familiar?

A late paragraph in the Comical article had me alternately laughing and staring at my screen in slack-jawed confusion for several minutes.

ETS has also made some technical changes to how the [GRE] is administered and graded. The traditional 200-to-800-point scale will be replaced with one ranging from 120 to 170 because the number of questions on the test is different.

Umm.... yeah. Okay. Why not start the scale at 0, and go up to, oh, I don't know, 100? Like, um, you know, a... how you say?... ah, yes. Percentage?

Then I figured it out. They're trying to measure IQ. Yay.

Quick! To the Dolphinmobile!

Dolphins!
Dolphins!
Dolphins!
Dolphins!
Dolphins, dolphins, dolphins!
Dolphins, dolphins, dolphins!
Da na na na na na na na na na na na na,
DOLPHINS!

[Insert "old chum" joke here.]

Four

Fortunately, there's usually a Mac only one block away.

Old-school computer science called [and still calls! -Jeff] for methodical coding practices to ensure that the large computers used by banks, governments and scientists wouldn't break. But as personal computers took off in the 1980s, companies like Microsoft didn't have time for that. PC users wanted cool and useful features quickly. They tolerated -- or didn't notice -- the bugs riddling the software. Problems could always be patched over. With each patch and enhancement, it became harder to strap new features onto the software since new code could affect everything else in unpredictable ways.