Longtime algorithms researchers will remember that in the 1980s, parallel algorithms used to be a hot topic, but that it faded as Moore's law caused new single-processor machines to be faster (and much easier to program) than parallel computers made with many older and cheaper processors. Nowadays, Moore's law itself has faded (or, more accurately, stopped leading to single-processor speedups) and parallel computing has been making a comeback, especially as many researchers have realized that we already have powerful and highly parallel processors cheaply available to us in the graphics coprocessors of our home video game systems. Researchers such as (at UCI) graduating student Nodari Sitchinava and his advisor Mike Goodrich have been hard at work on developing analysis models and algorithms for these new systems and figuring out how many of the old PRAM-algorithm techniques can be carried over to them. But there has also been a lot of work in this area in non-theory communities that could benefit from our theoretical expertise. In part, this is one of the themes of the Workshop on Massive Data Algorithmics to be held in conjunction with SoCG in Aarhus this summer, and older parallel algorithms conferences such as SPAA have also adapted to these new directions.

Uzi Vishkin has asked me to publicize another workshop, even more focused on this subject, to be held a little closer to (my) home. The Workshop on Theory and Many-Cores is to be held in College Park, Maryland, on May 29, 2009, the day before STOC and in the same state. There's an abstract submission deadline of April 27 (less than two weeks away). As the conference announcement states,

The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.

The main objective of the workshop will be to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.

Today is Don Knuth's 70th birthday. Happy birthday, Don!

I could say a lot about my own relation with Knuth's work: as a freshman in college in 1981 I was hired to help typeset a book in TeX (The Handbook of Artificial Intelligence), my first published paper was on graph drawing using TeX, and my thesis work concerned dynamic programs closely related to the line-breaking algorithms in TeX. But I thought it might be appropriate, instead, to do something a little more technical.

Knuth was the first to use the phrase “analysis of algorithms,” at the 1970 ICM in Nice. He popularized and extended O-notation (previously used in functional analysis) as an essential tool for algorithm analysis. And, his Art of Computer Programming set the standards for the field and is still well worth reading today. So, it seems a little presumptuous for me to analyze one of Knuth's own algorithms. I set out only with the goal of understanding one of his many papers, “Dancing Links,” which concerns a backtracking algorithm for an NP-complete problem, a subject of some interest to me. But, as so often, the problem took over and wouldn't let me go until I'd found something to add to it. Several times I thought I'd reached the end of the analysis, only to discover another refinement that kept it going deeper, until eventually this grew from a blog post to something resembling the outline of a full paper. I imagine Knuth is familiar with this process, on a much larger scale, as his Art of Computer Programming also grew far larger than he originally envisioned. Regardless, here is my analysis.

So you're all familiar with Avrim Blum's Motwani and Raghavan's (?) slick analysis of quicksort in CLRS, avoiding probabilistic recurrences and easily getting the correct constant in the leading term, right? (If not, I review it below.) What CLRS doesn't tell you is that the same analysis works almost as well for quickselect.

( Read more... )

Some years before Dijkstra attributed it to Hamming, Gingerich considered an interesting variant of Hamming's problem: list, in order, only those regular numbers in the interval [60^k,60^k+1).

The motivation comes from the study of Babylonian mathematics. In the sexagesimal system the Babylonians used, which we still use a modified version of for times, latitudes and longitudes, and angles, the power of the initial base-60 digit was not specified. That is, if I tell you that a duration of time is 1:12, it's not obvious from that notation whether I mean one hour and twelve minutes (that is, 72 minutes), or one minute and twelve seconds (that is, 72 seconds); both are written the same way. So, in a Babylonian table of the reciprocals of regular numbers, one would not have separate entries for 72, 72×60, and 72×60×60; all three would just be written as 1:12. Grouping equivalent numbers in this way allowed the Babylonians a considerable space savings in their arithmetic tables: there are O(k²) different k-digit sexagesimal representations of regular numbers to be listed, while there are Θ(k³) actual regular numbers that can be represented with k digits. The sorted order of the regular numbers in Gingerich's range is the order in which the Babylonians would have listed these numbers.

Gingerich listed these numbers out of order, and then sorted them. Can we do better, and list them in sorted order in a constant number of arithmetic operations per output value? Yes!