Category Archives: Theory of Computing

Summer Must Read: Annotated Turing

The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine by Charles Petzold

P.S. Charles has a blog, and some recent post are about Turing and this book.

Parallel Algorithms Dropped from CLRS

In an Intel Software Network article titled Parallel computing: disappearing from CS curricula???, Michael Wrinn demonstrated that parallel computing has gradually disappeared from popular CS curricula in the past 10+ years. His first example is:

[...] a panelist at IPDPS (in Miami, a couple of weeks ago) assert that parallel-processing topics have been disappearing from CS curricula in recent years. As anecdotal evidence, he pointed out the topic’s removal in the 2nd edition of Introduction to Algorithms [...]

The article goes on to give several other examples to prove his point. In the end, Michael wrote

[...] multicore computing platforms are now the norm. Recognizing that reality, let’s make the adjustment time short.

Are we expecting a surge of algorithm and data structure textbooks with an emphasis in multicore? :P

Jon Bentley on Three Beautiful Quicksorts

A while ago I checked out Beautiful Code from our library. Jon Bentley wrote chapter 3, which is about Quicksort, and paradoxically named the chapter “The Most Beautiful Code I Never Wrote”. This video is an extension of that chapter and will explain the name. I can recommend the talk, especially the third part in which he talks about the industrial implementation of qsort (that part starts shortly after 34:00).

Knuth Interview 2008-04-25

Available here at informIT.

Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation.

Among other things, he explained why the numbering of Volume 4 fascicles starts at 0 and not 1. (You may recall that there is no Volume 0 and so zero-based counting cannot be exactly the reason. Well, I mean not exactly.)

My Vote Goes to Red-Black

On Geomblog, Piotr mentioned a problem that I think many of us can share: if we really have to pick just one to teach (as in his case), do we go with 2-4 trees or red-black trees?

For the most part, the pros and cons of the two approaches are quite, urr, balanced. :P But there has been one critical issue that tilt my preference towards RB. On the surface, the issue is “augmentation”, ala CLRS chapter 14 style. But it really is about the number of rotations used during insertions and deletions…

There is a fascinating history behind this, which is summarized by Ottmann and Wood up to 1990. It all started with a design from Olivie and a swift response from Tarjan. The rest of the juicy bits, well, I offer no spoiler. This post merely needs the following fact to make sense: in the worst case, some implementations of RB need only $O(1)$ rotations during restructuring and the remaining work are color changes; some implementations need logarithmic number of rotations.

But if we can afford a logarithmic number of color changes in the worst case, isn’t it just “a matter of constants” even if we have to do a logarithmic number of rotations as well?

In many cases, the answer is indeed yes, but there is no lack of interesting cases due to augmentations that make rotations “expensive”. For a starter: see section 13.4 of Bob’s textbook, pp 570-571 in the C++ 3rd edition, where this very issue is raised and the model answer is presented. Here is a favorite example of mine: Seidel and Aargon used this to highlight why treaps are preferable to splay trees in applications like segment trees. Let’s end with one more related to this post: McCreight’s priority search trees, used as the motivating example in Ottmann and Wood, also critically rely on search trees that use only $O(1)$ number of rotations to restructure. More precisely, doing $p$ rotations yields a bound of $O(p \log n)$. See, it’s not just in the constants!

I will finish this by saying that this doesn’t imply a landslide victory for RB. Conceptually, 2-4 trees are really hard to beat! In fact, even though I would be speaking RB in my mouth, I would be thinking about 2-4 at the back of my mind! (Kind of like some foreign language speakers, no? Ten years ago I was exactly like this, haha.) And really, if we ever get to more advanced stuff like supporting finger searches, I will pick 2-4 on most but not all days. Complications… complications… :P

Exercise: To understand how a 2-4 speaker would speak in RB, what is “black-height” in the 2-4 language?

Reference: Thomas Ottmann, Derick Wood: How to Update a Balanced Binary Tree with a Constant Number of Rotations. SWAT 1990: 122-131

Algorithms in Media 2007-09-23

From this New York Times article:

Algorithms, as closely guarded as state secrets, buy and sell stocks and mortgage-backed securities, sometimes with a dispassionate zeal that crashes markets. Algorithms promise to find the news that fits you, and even your perfect mate.

Perfect!

“Algorithms” sound scary, but less scary than “Operations Research”

See this great post in Michael Trick’s OR Blog on a recent article in the Economist magazine titled “Business by numbers”.

Among other things, this is how the Economist article begins:

Algorithms sound scary, of interest only to dome-headed mathematicians.

Well, I have no idea what “dome-headed” means, but Google tells me that dome-headed creatures can be scary. Now, domed-head mathematicians… hmm, maybe it has to do with banging the head to the wall? :P

I know it is Theory when I see it

Please see Developing for Developers by Derrick Coetzee.

Algorithms Considered Quaint

Wiley has published a new book that, in a certain sense, is about algorithms: Computer Science Reconsidered: The Invocation Model of Process Expression, by Karl M. Fant. From the back cover:

A groundbreaking, seminal work that challenges the theoretical foundations of computer science

For some juicy bits of this book, I refer you to the article Want to be a computer scientist? Forget maths, with the subtitle:

A new book seeks to demolish the concept that computer science is rooted in mathematics and, in particular that the notion of the algorithm is fundamental to computer science.

After reading the article, I realized that there are so many things that can be said about this new book and I really don’t know how to begin. I guess I just have to rely on fellow bloggers. You know, with quotes like—

Any program utilising random input to carry out its process, such…is not an algorithm.

—I can only imagine that Mike Mitzenmacher has more than a few things to say on the subject. And consider this—

A logic circuit is not a sequence of operations.

—that, that… that’s a brilliant observation! My sky is falling…

Godel Prize 2007 Announced

http://www.eatcs.org/activities/awards/goedel2007.html

The 2007 Gödel Prize for outstanding journal articles in theoretical computer science is awarded to:
Alexander A. Razborov and Steven Rudich

for their paper
“Natural Proofs”, Journal of Computer and System Sciences, Vol. 55, No. 1, 1997, pp. 24-35.

It was first presented at the Twenty-sixth Annual ACM Symposium on Theory of computing, Montreal, Quebec, Canada. 1994, pp. 204 – 213.

I note that Natural Proofs have been written a couple times before on the blogosphere, and I further note that the prize must have been announced at least a week ago from seeing a link into the latter post. Ha!

A Purple Dragon Was Born

When I was a kid, I was told that a book could gain immortality when people referred to it without even mentioning its title. At that time I wasn’t sure what that meant.

As I grew up, I started to hear about legends of the Green Dragon and the Red Dragon that soar over the great land of Computer Science…

After some twenty years, this semester, the Purple Dragon has finally made its debut to take over the reign of the Red Dragon.

But somehow, deep inside, I felt something looks “wrong” ever since I laid my sight on its cover. I couldn’t identify the subtle cause.

And this morning, ah ha! I finally realized—the computer has disappeared! Indeed, everything else like the Sword of LALR Generator are still there. The computer, however, has disappeared.

I can only imagine that the Knight has an UMPC mounted behind the Shield on his/her forearm. Or perhaps, with the advancement of technology in the last twenty years, the battlefield is now the Matrix.

P.S. Seriously, parsing has definitely advanced in the last twenty years. For a great theory-meets-practice story, you can read about ANTLR. It’s fascinating.

SODA 2007 List of Accepted Papers

Posted here:

http://www.cs.colorado.edu/~hal/alist.txt

Update: Some stats are available in this post in Geomblog.

Multiplying 70-by-70 Matrices

Strassen’s algorithm for matrix multiplication is a classic example of how a straightforward algorithm may be beaten asymptotically by a witty one. But there is a problem if you use this example in teaching—how did Strassen come up with the seven intermediate submatrix products?

If you dig up Strassen’s 1969 paper, you’ll see that he didn’t give us any hint. Others have attempted to offer plausible explanations, and you can find one in CLR(S), or a similar and apparently earlier one by Brent on the web.

Now I don’t know about you, but I was never quite convinced when I was reading CLR as a student. But the real kicker comes when later on you were told that Victor Pan has a way to multiply two 70-by-70 matrices with 143640 multiplications… Seventy!?

So I decided to come up with a fairy tale to explain this magical number. But as it turns out, there is not much need for my creativity. :P

In fact, back in 1984, Victor published a monograph that contains all the glory details that lead to his algorithm. Basically, he designed a class of matrix multiplication algorithms which is parameterized by the size of the submatrices used in the recursion. The number of multiplication happens to be minimized when the submatrices are chosen to be 70 times smaller. It’s just that. No fairy tale is necessary.

Incidentally, the first chapter of his book is more or less available in an article appeared in SIAM Review. You can see page 6 on which he talks about it.

TAOCP V4 F4

Starting from my inbox, I discovered that

The Art of Computer Programming, Volume 4, Fascicle 4 : Generating All Trees–History of Combinatorial Generation

is available for sale now. Here is a totally no-commission-involved link to the item on Amazon.com. The previous three fascicles are of course also available.

Seminar on The Coupling Method

From Prof. Kavita Ramanan from the Math Department:

The informal ‘Graduate Students Seminar’ on “The Coupling Method” that I am running is being held from 2:30–4:00 (it is usually done around 3:30 or 3:45) on Fridays at Wean Hall 6423. We are following the book “The Coupling Method” by Torgny Lindvall, though we will also read papers, etc. We have so far had just two lectures that have covered the first, introductory, chapter of the book by Lindvall and the related background material from Appendix 2.

Refreshments (pizza, coke) will be served.

To put yourself on the seminar mailing list, send an e-mail to spredoiu at andrew.cmu.edu.

IMPORTANT: Every week, anyone who plans to attend the seminar on Friday should e-mail Gerard Brunick — gbrunick at andrew.cmu.edu — by Thursday noon, so we can order the right amount of refreshments.

All students that plan to attend (reasonably) regularly are welcome.

A Small Constant

This is not a post to argue for or against the big-O notation. Instead I just want to share an observation using a toy example.

Consider a dictionary data structure that supports access in logarithmic time. Suppose we have two implementations A and B where A is two times faster than B. (To make it precise but toyish, imagine an access takes $\log n$ time and $2 \log n$ time respectively where $n$ is the number of elements.)

How would this factor of two become important?

Well, when there is a hard upperbound on the amount of time allowed in an access, then the maximum number of elements that can be stored in A is actually the square of that of B.

It’s squared, not just doubled.

Now here’s something to think about. You can have a digital photo album that can store a maximum of two thousand photos or another one with four million photos. They are equally responsive on your computer. Which one would you prefer as a customer?

(Or, perhaps we can wait 18 months and be happy with the former one? :P )

Quicksort Alike

Recently I had to “analyse” randomized Quicksort over a dinner table. Well, I wasn’t prepared to do it using only a pair of chopsticks and a bowl. So I “cheated”. :P

Instead of picking a random element and accept it as the pivot, we let the partitioning algorithm test if the random element is a balanced pivot, i.e., it sits between the 25-percentile and the 75-percentile. This test takes exactly linear time. And if not, the algorithm will pick another random element and re-test.

Clearly the probability of picking a balanced pivot is 1/2 and so the partitioning algorithm will finish in an expected constant number of trials. The rest of the proof is easy and using five more minutes I “proved” the expected $O(n \log n)$ bound with surprisingly little hand-waving. I also ate a lot of garlic bok choy in the process.

Now here are some simple questions that arise from this incident:

  • What about finding the median as the pivot? (And we have a choice of randomized and deterministic median algorithms.)
  • What about the concentration? Is this $O(n \log n)$ “with high probability”? (For instance, what is the probability that it takes 42 trials before a balanced pivot is found?)
  • Can we use a similar view to analyze the running time of the unmodified version of Quicksort? (Try to come up with a clustering of the nodes in the recursion tree and analyze the running time spent in each cluster of nodes.)

More homework questions…

Dantzig and Simplex

I have a Slashdot backlog… I am still on May 22. So it wasn’t until this noon that I learned about the passing away of George Dantzig, the inventor of the Simplex method for solving LPs. Salute.

This reminds of a discussion I had with one of our faculty candidates last semester. Vladlen Koltun gave a fabulous job talk here and the first half of it was devoted to his work on strongly polynomial time linear programming. His magic weapon seems to be arrangement polytopes. The key idea is that linear programming on any polytope can be reduced, in polynomial time of course, to linear programming on an arrangement polytope with provably polynomial diameter. My notes say the diameter is $n * d$, where $d$ is the number of variables (dimension) and $n$ is the number of half-spaces (“faces”).

The diameter of any given polytope is important for Simplex, which navigates on extreme points. This is one major reason why the Hirsch conjecture attracts a lot of attention. The conjecture states that the diameter of any polytope is bounded by $n – d$. (I know how to check that on a “hypercube” for $d$ being 2 and 3. :P ) The fear is that there may exist a “worst-case” polytope with super-polynomial diameter that will ruin Simplex.

But using this reduction idea as told by Koltun, the diameter may no longer be an obstacle and instead we may choose to focus our energy on navigating on an arrangement polytope. At this point let me end the summary by noting that he showed, together with Umesh Vazirani, that linear programming is still not easy even when reduced to arrangement polytopes. I don’t know if they have any newer developments since then.

Back to our discussion after his talk. Several years ago I hit upon a result which I have dug up back when I was studying the subject of smoothed analysis:

Carl W. Lee, Regular Triangulations of Convex Polytopes, DIMACS Technical Report 90-16, 1990.

In this paper, Lee showed that every $d$-dimensional polytope can “patched” into a $(d+1)$ dimensional polytope in which the original polytope is a facet of the new polytope and the new polytope has $2(n-d)$ diameter. It’s not quite Hirsch, but a linear diameter seems too good already.

Lee’s construction is pretty simple: add a new dimension and add a new point at coordinate $(0, \ldots,0,1)$, i.e., it is the only point that is not lying on the 0-plane of the new dimension. So you first get a pyramid. The degeneracy at the apex is handled by a careful but simple perturbation. More precisely, starting with the linear program:

$\max c \cdot x$
$a_i \cdot x \leq b_i, 1 \leq i \leq n$

We transform it into

$\max c \cdot x + 0x_{d+1}$
$a_i \cdot x + (b_i – \epsilon_i)x_{d+1} \leq b_i, 1 \leq i \leq n$
$x_{d+1} \geq 0$

where the $\epsilon_i$ are indeterminates with lexicographic order $0$ < $\epsilon_n$ << $\cdots$ << $\epsilon_1$ << $1$. (Apparently ASCIIMathML doesn't support \ll yet.) Check that the apex is indeed at $(0, \ldots, 0, 1)$. Because the $\epsilon_i$ are very small, we know that $(x, 0)$ is optimal for the new program iff $x$ is optimal for the original.

Not surprisingly, we are not done yet. It's true that in principle the new program can be solved in a linear number of pivots, but the hard question remains: which sequence of pivots do you want?

Now how Lee's method meshes with tools from smoothed analysis seems to be a long story. My day dreaming is that we could control the apex perturbation more carefully. Then the apex can be used as a polynomial time oracle: You start at an extreme point in the original polytope, take the airplane to go to the apex, compute, then jump down with a parachute along a carefully chosen edge to end up at another extreme point that is expected to be closer to the optimal.

I hope one day I will come back to write more. "Time is always against us. Please, take a seat there."

As an aside, from this Slashdot post I also learned about The Unsolvable Math Problem urban legend in which Dantzig unknowingly solved two major open problems as homework questions. Hehe.

FOCS 2005 Early Registration Ending

If you have not registered for FOCS 2005 yet, please consider doing it now. The early registration for the conference and also the hotel is ending this Friday (Sept 23).

http://www.cs.cmu.edu/~FOCS05/

SODA 2006 List of Accepted Papers

Well, I don’t know if SODA is rising, falling, or maybe falling in one regard because it is rising in another, but I do know that the list of accepted papers has been published. :P

According to Cliff Stein, there were 432 submissions, of which 135 have been accepted. A comment at Jeff Erickson’s blog reveals that 135 is the maximum that they can fit in 3 days, as discussed in the business meeting last year.

Update: this is the official list on SODA 2006′s web site.