Hello? Hello? Is this thing still on?
I've been a bit quiet here for the last few years, partly as a new parent, learning to deal with children, and more recently as an associate department head, learning to deal with bureaucracy. (The two skills are remarkably similar!) But now that my kids are now well into their transformation from cute gobs of poo into full-fledged independent human beings, and my three-year sentence term as an administrator is coming to a close, I find myself wondering what I'm going to do when I'm no longer a grown-up.
My main job as associate head was hiring tenure-track faculty. Illinois CS just had an excellent year—five new faculty are joining us this fall and several more are starting in Fall 2017—but I need to wait for the ink to dry on our final offers before talking about the hiring process in any detail.
My other job was helping to launch a major revision of our undergraduate theory courses, as part of a wider curriculum revision. Our new required theory course (CS 374) has a steady-state enrollment of 400 students per semester. This curriculum change, combined with our skyrocketing enrollments (just like everyone else's) has had some interesting side-effects, which I'm sure I'll talk more about later.
One side-effect of the change is that my algorithms lecture notes no longer mirror the structure of the courses I teach, so I'm starting a major revision. With videos. Stay tuned.
But enough about me. The title of this post is a line from a 1940's cold-reading test for prospective radio announcers, popularized by Jerry Lewis (“The Announcer's Test”), Flo and Eddie (“The Tibetan Memory Trick”), and many others. The test has the same cumulative structure as “The Twelve Days of Christmas” or some versions of “Old MacDonald Had a Farm”; the kth “verse” consists of the first k lines from the following list (with “and” inserted between like k–1 and k):
- One hen
- Two ducks
- Three squawking geese
- Four limerick oysters
- Five corpulent porpoises
- Six pairs of Don Alverzo's tweezers
- Seven thousand Macedonian warriors in full battle array
- Eight brass monkeys from the ancient, sacred, holy crypts of Egypt
- Nine sympathetic, apathetic, diabetic, old men on roller skates, with a marked propensity towards procrastination and sloth
- Ten lyrical, spherical, diabolical denizens of the deep who all stall around the corner on the quo of the quay of the quivvey, all at the same time.
Roughly, the length of each line increases linearly, which means the length of each verse increases quadratically, which means the length of the entire announcement is cubic in the number of lines. This is the only "song" I know that requires Θ(n3) time to "sing" the first n verses. On the other hand, just writing down n lines requires Θ(n2) space, so in terms of Knuth's infamous paper “The Complexity of Songs”, the Announcer's Test has complexity Θ(N2/3). This is the only example I know of a "song" with this complexity.
Do you know of any other songs with complexity Θ(N2/3)? How about Θ(Nc) for any constant c other than 0, 1/2, 2/3, or 1? I look forward to reading your compositions in the comments.
Recent Comments