[click here to zip down to the schedule of public lectures]

I've just learned that 2015 is `11111011111` in binary notation.
Which is why I've just turned 77.

For many years I've resisted temptations to put out a hasty electronic version of The Art of Computer Programming, because the samples sent to me were not well made.

But now, working together with experts at Mathematical Sciences Publishers, Addison-Wesley and I have launched an electronic edition that meets the highest standards. We've put special emphasis into making the search feature work well. Thousands of useful "clickable" cross-references are also provided --- from exercises to their answers and back, from the index to the text, from the text to important tables and figures, etc.

*Note: However, I have personally approved ONLY the PDF
versions of these books. Beware of glitches in the ePUB and Kindle
versions, etc., which cannot be faithful to my intentions because
of serious deficiencies in those alternative formats. Indeed,
the Kindle edition in particular is a travesty, an insult to
Addison-Wesley's proud tradition of quality. Readers of
the Kindle edition should not expect the mathematics to make
sense! Maybe the ePUB version is just as bad, or worse ---
I don't know, and I don't really want to know. If you have been
misled into purchasing any part of eTAOCP in an inferior format, please
ask the publisher for a replacement.
*

The first fascicle can be ordered from Pearson's InformIT website, and so can Volumes 1, 2, 3, and 4A.

Volume 4B of The Art of Computer Programming will begin with a special section called ‘Mathematical Preliminaries Redux’, which extends the ‘Mathematical Preliminaries’ of Section 1.2 in Volume 1 to things that I didn't know about in the 1960s. Most of this new material deals with probabilities and expectations of random events; there's also an introduction to the theory of martingales.

You can have a sneak preview by looking at the current draft of pre-fascicle 5a (50 pages), last updated 01 October 2015. As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions. I'm particularly interested in receiving feedback about the exercises (of which there are 124) and their answers (of which there are 124).

There's stuff in here that isn't in Wikipedia yet!

The middle third of Volume 4B will be a major introduction to the topic of Boolean Satisfiability, emphasizing its many applications, together with a variety of algorithms to solve SAT problems with greater and greater speed. I began studying this topic in autumn 2011, and found it to be amazingly interesting. Thus I've had great fun telling this story, and connecting SAT with many other aspects of computer science and math.

It's not a short story; indeed, this section has turned out to be the largest by far of any in The Art of Computer Programming. But the material is rich, beautiful, instructive, and important, so I'm pleased to have had the opportunity to pull it together from many sources.

Here then, ta-da, is the final draft of pre-fascicle 6a (318 pages). This is revision 6, dated 23 September 2015. It includes 526 exercises and a comprehensive index. I'm putting it online now for beta-testing; Addison-Wesley plans to publish it in paperback before the end of 2015. Happy reading!

I worked particularly hard while preparing some of those exercises, attempting to improve on expositions that I found in the literature; and in several noteworthy cases, nobody has yet pointed out any errors. It would be nice to believe that I actually got the details right in my first attempt. But that seems unlikely, because I had hundreds of chances to make mistakes. So I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out as yet.

I still cling to a belief that these details are extremely instructive, and I'm uncomfortable with the prospect of printing a hardcopy edition with so many exercises unvetted. Thus I would like to enter here a plea for some readers to tell me explicitly, ``Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,'' where N is one of the following exercises in prefascicle 6a:

- 6: Establish a (new) lower bound on van der Waerden numbers
*W*(3,*k*) - 11: Verify a beautiful reduction of 3SAT to 3D matching
- 24: Analyze Bailleux and Boufkhad's efficient cardinality clauses
- 57: Find a 6-gate way to match a certain 20-variable Boolean function at 32 given points
- 68: Encode the Life transition function in a small number of clauses
- 74: Prove that finite mobile flipflops in Life have many forbidden configurations
- 105: Investigate tomographically balanced matrices
- 165: Devise an algorithm to compute the largest positive autarky of given clauses
- 177: Enumerate independent sets of flower snark edges
- 191: Count the
*n*-variable functions expressible in 3CNF, for*n*=3,4,5 - 204: Construct difficult 3SAT instances with
*N*variables and at most (4/3)*N*clauses - 212: Prove that partial latin square construction is NP-complete
- 215: Analyze a simple backtrack algorithm on random 3SAT instances
- 237: Establish the pigeonhole principle efficiently using extended resolution
- 245: Prove that Tseytin's unsatisfiable graph-parity clauses make CDCL solvers take exponential time
- 246: But those clauses can be refuted efficiently with (clairvoyant) extended resolution
- 257: Find an efficient way to remove redundant literals from learned clauses
- 283: Find a linear certificate of unsatisfiability for the flower snark clauses
- 297-299: Analyze Papadimitriou and Schöning's random-walk algorithm for satisfiable 3SAT problems
- 304: Analyze the exact running time of random-walk algorithms on a particular 2SAT problem
- 306-308: Study the reluctant doubling strategy of Luby, Sinclair, and Zuckerman
- 318: Find the best possible Local Lemma for
*d*-regular dependency graphs with equal weights - 322: Show that random-walk methods cannot always find solutions of locally feasible problems using independent random variables
- 335: Express the Möbius series of a cocomparability graph as a determinant
- 339: Relate generating functions for traces to generating functions for pyramids
- 347: Find the best possible Local Lemma for a given chordal graph with arbitrary weights
- 356: Prove the Clique Local Lemma
- 363: Study the stable partial assignments of a satisfiability problem
- 374: Design efficient data structures for the preprocessing of SAT clauses
- 386: Prove that certain CDCL solvers will efficiently refute any clauses that have a short certificate of unsatisfiability
- 399: Compare preclusion clauses to support clauses for constraint satisfaction problems
- 409: Find optimum makespans for certain open shop scheduling problems
- 428: Show that Boolean functions don't always have forcing representations of polynomial size
- 440: Construct efficient forcing representations for functions defined by context free languages
- 442-444: Study the UC and PC hierarchy of progressively harder sets of clauses
- 481: Construct a circuit for the sum of
*n*bits that uses fewer than 4.5*n*gates - 518: Reduce 3SAT to testing the permanent of a {-1,0,1,2} matrix for zero

Please don't be alarmed by the highly technical nature of these examples;
more than 100 of the *other* exercises are *completely non-scary*,
indeed quite elementary. But of course I do want to go into high-level details also,
for the benefit of advanced readers; and these darker corners of my books
are naturally the most difficult to get right. Hence this plea for help.

Remember that you don't have to work the exercise first. You're allowed
to peek at the answer; in fact, you're even encouraged to do so.
Please send success reports to the usual address for bug reports
(`taocp@cs.stanford.edu`),
if you have time to provide this extra help. Thanks in advance!

Hooray: After fifteen years of concentrated work with the help of numerous
volunteers,
I'm finally able to declare success by releasing Version 1.0 of the
software for
`MMIX`. This represents the most difficult
set of programs I have ever undertaken to write; I regard it as a major
proof-of-concept for
literate programming, without which I believe the
task would have been too difficult.

Version 0.0 was published in 1999 as a tutorial volume of Springer's Lecture Notes in Computer Science, Number 1750. Version 1.0 has now been published as a thoroughly revised printing, available both in hardcopy and as an eBook. I hope readers will enjoy such things as the exposition of a computer's pipeline, which is discussed via analogy to the activites in a high tech automobile repair shop. There also is a complete implementation of IEEE standard floating point arithmetic in terms of operations on 32-point integers, including original routines for floating point input and output that deliver the maximum possible accuracy. The book contains extensive indexes, designed to enhance the experience of readers who wish to exercise and improve their code-reading skills.

I'm pleased to announce the appearance of an excellent 200-page companion
to Volumes 1, 2, and 3, written by Martin Ruckert.
It is jam-packed with goodies from which an extraordinary amount can be
learned. Martin has not merely transcribed my early programs for `MIX`
and recast them in a modern idiom using `MMIX`; he has penetrated to
their essence and rendered them anew with elegance and good taste. His
carefully checked code represents a significant contribution to the art of
pedagogy as well as to the art of programming.

One of my best friends, Jin Kyung Lim, will be presenting a recital on the pipe organs of Stanford's Memorial Church at 7:30pm on Wednesday, November 4. She will be playing some wonderful music by Bach, Franck, and others, as well as a brief experimental piece by a Stanford professor.

I recently came across the following interesting comment, made by Alan Turing in a lecture to the London Mathematical Society on 20 February 1947 (when he was in the midst of planning the ACE computer):

The masters [programmers] are liable to get replaced because as soon as any technique becomes at all stereotyped it becomes possible to devise a system of instruction tables which will enable the electronic computer to do it for itself. It may happen however that the masters will refuse to do this. They may be unwilling to let their jobs be stolen from them in this way. In that case they would surround the whole of their work with mystery and make excuses, couched in well chosen gibberish, whenever any dangerous suggestions were made. I think that a reaction of this kind is a very real danger.

Among the other noteworthy points he made at the time are the importance of efficient and abundant computer memory:

The full storage capacity of the ACE available on mercury delay lines will be about 200,000 binary digits. This is probably comparable with the memory capacity of a minnow. ...

I believe that the provision of proper storage is the key to the problem of the digital computer, and certainly if they are to be persuaded to show any sort of genuine intelligence much larger capacities than are yet available must be provided. In my opinion this problem of making a large memory available at reasonably short notice is much more important than that of doing operations such as multiplication at high speed. Speed is necessary if the machine is to work fast enough for the machine to be commercially valuable, but a large storage capacity is necessary if it is to be capable of anything more than rather trivial operations.

Although I must stay home most of the time and work on yet more books that I've promised to complete, I do occasionally get into speaking mode. Here is a current schedule of events that have been planned for this year so far:

- Sunday March 8, 9:15am at First Lutheran Church in Palo Alto
- Discussing a multiyear project in which I'm attempting to write a major work for organ in my spare time, based on the Book of Revelation
- Thursday May 7, 5:15 in the CCRMA stage (at the Knoll)
- “Constraint-based composition”: Explaining the peculiar(?) methods that I'm using as I try to compose a major work for pipe organ in my spare time (watch video)
- Wednesday May 27, 2pm in Oxford Comlab, Lecture Theatre B
- Presenting a seminar talk “An asymmetric approach to symmetry breaking”
- Wednesday June 17, 5pm at the University of British Columbia's Point Grey campus
- “All Questions Answered” sponsored by UBC's Computer Science Department
- Thursday June 18, in the evening, at Simon Fraser University's Burnaby campus
- “Orthogonal Remarks” at the banquet of the Connections in Discrete Mathematics conference (view juggling video from 1972) (view open problem about peacefully coexisting queens in polygons, updated 18 July 2015)
- Wednesday July 15, 9am, in room 300 of Stanford's Huang Engineering Center
- Speaking for 90 minutes about “SAT and TAOCP” at the beginning of the SAT/SMT Summer School 2015
- Saturday October 17, 5pm, at Berkeley DoubleTree Hotel
- “Orthogonal Remarks” at Karpfest80 (view slides)
- Wednesday October 28, 2pm, in Oxford Comlab, Lecture Theatre B
- Presenting a departmental seminar talk “An amusing new paradox” (view handout)
- Tuesday November 3, 10am, at University College Cork in Brookfield G06
- Talking about “An amusing new paradox” (see abstract above)
- Wednesday November 4, 6pm, at University College Cork in Brookfield G01
- “All Questions Answered”
- Thursday December 3, 6pm, in the NVIDIA Auditorium, Huang Engineering Center
- A "Computer Musing" --- Universal Commafree Codes [the twenty-first annual Christmas Lecture]

Click here for the “recent news” that was current at the end of 2014, if you're interested in old news as well as new news.