Computer science is changing: the amount of data available for processing is growing exponentially, and so must the emphasis towards its handling. Like the 19^th century change in physics from mechanics to statistical mechanics, the new algorithms sacrifice the precision of a unique answer for the fast search of statistical properties. The following draft of a book by Hopcroft and Kannan breaks the path of what most future algorithms manuals may look like:

Download (PDF, 1.83MB)

Heavy on proofs, many topics have been selected for their mathematical elegance, not their pragmatism. On the final version of this much anticipated book, I would love to see more content on hash algorithms, parallel algorithms, graph spanners or a more extensive discussion on Support Vector Machines.

I was aware that there are too many errors on any CAS to be listed on the margin of their accompanying documentation. But finding the culprit after hours of debugging, a very simple bug but with a very high impact since other complex calculations are being based on its proper calculation, is a disturbing experience. It turns out that, in Mathematica,

In[1]:= badIntegration = Integrate[1 / (2 + Cos[x]), {x, 0, y}, Assumptions -> y > Pi]

Out[1]:= 2(Pi+ ArcTan[Tan[y/2]/ Sqrt(3))/Sqrt(3)

is symbolically evaluated as a discontinuous function, even if it must clearly be continuous, since the integrand is everywhere continuous, finite and positive. But the Weierstrass substitution method used internally when symbolically calculating integrals of inverse trigonometric functions sometimes produces discontinuities. Go figure.

Lesson learned: as a safety measure, always use multiple CAS programs (SAGE, Maple, …)  to compare solutions when getting strange results.

It’s funny how two of the most studied algorithms of a discipline, that are considered polynomially optimal for decades under a set of well-accepted assumptions, turn out not to be so great. That’s the case of the famous A* and IDA* algorithms, cornerstones in AI and currently implemented in thousands of computer games because there were thought to be polynomial in the search space since 1968 under a set of broadly defined heuristics, even though nobody has found practical instances of them after hundreds of proposal and attempts. Their optimality is finally debunked in “How Good is Almost Perfect”: general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the most optimistic assumption of estimators with heuristic error bounded by a small additive constant. What is worse, other similar search techniques cannot perform better than A*.

These are the kind of results that reminds you to always revisit assumptions, to search more closely where others may have obviated, no matter how well-accepted and reputed are the sources, in particular with folklore wisdom, beliefs and other uncanny heuristics.

Addictive Number Theory

In 1996, just after Springer-Verlag published my books Additive Number Theory: The Classical Bases [34] and Additive Number Theory: Inverse Problems and the Geometry of Sumsets [35], I went into my local Barnes and Noble superstore on Route 22 in Springfield, New Jersey, and looked for them on the shelves. Suburban bookstores do not usually stock technical mathematical books, and, of course, the books were not there. As an experiment, I asked if they could be ordered. The person at the information desk typed in the titles, and told me that his computer search reported that the books did not exist. However, when I gave him the ISBN numbers, he did find them in the Barnes and Noble database. The problem was that the book titles had been cataloged incorrectly. The data entry person had written Addictive Number Theory.