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

Wow: 2016 is divisible by 4, and so is the quotient 2016/4.
(When Orwell wrote his famous book, did he realize that 1984 would be
a *leap leap leap* year?)

My academic appointment at Stanford officially began in 1968 — another leap leap year! — but I was actually on a leave of absence, doing some national service at Princeton. Finally I arrived on campus in September of 1969, and began to teach about computer programming.

I gave my inaugural colloquium lecture as a Professor of Computer Science on November 4, 1969, speaking about a newfangled concept that I'd decided to call “analysis of algorithms.”

As part of Stanford's ClassX Project, plans are afoot to stage a re-enactment of that lecture and to capture the video before a live audience.

The lecture hall in the Biology building, where I originally spoke, still stands, and we'll meet there. If you're interested in a nostalgia trip, see the lecture schedule below for further details.

One of the delights of Wikipedia is that its biographies generally reveal a person's full and complete name, including the correct way to spell it in different alphabets and scripts.

When I prepared the index to Volume 1 of The Art of Computer Programming, I wanted to make it as useful as possible, so I spent six weeks compiling all of the entries. In order to relieve the tedium of index preparation, and to underscore the fact that my index was trying to be complete, I decided to include the full name of every author who was cited, whenever possible.

None of my textbooks had done this. But in Caltech's library I learned that the Catalan numbers had not only been investigated by Lamé, Catalan, Rodrigues, and Binet, they had been studied by Gabriel Lamé, Eugène Charles Catalan, Benjamin Olinde Rodrigues, and Jacques Philippe Marie Binet. I also had become personally acquainted with Nicolaas Govert de Bruijn, Edsger Wybe Dijkstra, Charles Antony Richard Hoare, etc.. so I had lots of good data. My index presented Russian names like Andreĭ Nikolaevich Kolmogorov in a westernized transcription.

Later, when I typeset the index to the second edition of
Volume 2, using an early prototype of TeX in 1980,
I had the ability to
include Chinese and Japanese names in their native form.
And by the time the third editions came out in the 1990s, I was also able
use Greek, Hebrew, and Cyrillic alphabets, and to present
Arabic and Indian names in appropriate native scripts.
At last I did *not* have to rely entirely on transliteration when
listing the name of the father of algorithms,
Abu Ja‘far Mohammed ibn Mūsā al-Khowārizmī.
I even hand-crafted an ancient Sumerian name by using METAFONT to
draw the necessary characters of a cuneiform alphabet.

Over the years, many people have told me how they've greatly appreciated this feature of my books. It has turned out to be a beautiful way to relish the fact that computer science is the result of thousands of individual contributions from people with a huge variety of cultural backgrounds.

And at last, thanks to Unicode, the world's alphabets and scripts are present on almost everybody's computers and cellphones. So it's easy now for people who use different writing systems to share their names with each other.

The American Mathematical Society has just launched a great initiative by which all authors can now fully identify themselves, without becoming egocentric and immodest. It's an extension to the Author Profile feature that was introduced some years ago: You can now characterize your name, not only in the customary western alphabets used in traditional AMS publications, but also in any native script.

It's really easy to update your profile: Ed Dunne has given nice step-by-step instructions together with several well-chosen examples.

**I strongly encourage everybody to document their full
names at the AMS site, as soon as possible.** Just go to
`http://www.ams.org/mathscinet/MRAuthorID/search`
and identify yourself. That database already contains
more than 740,000 authors, so you'll be in good company.
**Even if you weren't born in a country
with exotic characters,** I urge you to complete your author profile
by including any middle name(s) that you have. Those names shouldn't
appear only in a few legal papers and on your dissertation, even if
you never actually use them in publications. They are an important
part of life. The rest of us shouldn't have to wait to learn
your full name until Wikipedia has a page for you.

Of course, if you have only two names, that's fine too.

P.S.: Wikipedia now informs me that Lamé had three more names that I didn't previously know about.

One of the most important sections of The Art of Computer Programming has now been published in preliminary paperback form as Volume 4, Fascicle 6: “Satisfiability”. Here are excerpts from the hype on its back cover:

This fascicle, brimming with lively examples, introduces and surveys “Satisfiability,” one of the most fundamental problems in all of computer science: Given a Boolean function, can its variables be set to at least one pattern of 0s and 1 that will make the function true?

Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.

Fascicle 6 presents full details of seven different SAT solvers, ranging from simple algorithms suitable for small problems to state-of-the-art algorithms of industrial strength. Many other significant topics also arise in the course of the discussion, such as bounded model checking, the theory of traces, Las Vegas algorithms, phase changes in random processes, the efficient encoding of problems into conjunctive normal form, and the exploitation of global and local symmetries. More than 500 exercises are provided, arranged carefully for self-instruction, together with detailed answers.

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 carefully 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 Volume 4 Fascicle 6:

- 6: Establish a (new) lower bound on van der Waerden numbers
*W*(3,*k*) - 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
- 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
- 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 those 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!

Volume 4B 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!

Here's Stephen Bean's video of an interview by Michel Schellekens that was filmed at my home on 23 April 2015.

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:

- Thursday February 4, 5:30--6:30pm in Herrin Hall room T175 (on the lower floor of the same biology building that now hosts the Math/CS library upstairs)
- “The Analysis of Algorithms,” a historic re-enactment of the lecture that I gave on November 4, 1969, upon becoming a Stanford prof (see above) (watch video in hires) (or in lowres via vimeo) (and/or watch cat videos from 1969)
- Tuesday March 8, 2pm, in Oxford Comlab, Lecture Theatre B
- Presenting a departmental seminar entitled “Random Samples From My Latest Book”
- Tuesday March 15, 13:00 in Hall F1 at the Royal Institute of Technology in Stockholm
- “All Questions Answered” as part of a ‘reach-out event’ for students and Institut Mittag-Leffler´s 100th anniversary
- Thursday March 17, 2:45pm, lecture room D2 at KTH, Lindstedtsvägen 17
- “Catalan lattices and bijections” as part of the 27th Nordic Congress of Mathematicians (view slides)
- Wednesday March 23, 5pm, somewhere at University of Bordeaux
- “Reminiscences of Marco” as part of a Conference dedicated to the scientific legacy of Marcel-Paul Schützenberger (view slides)
- Monday April 25, 4pm, Oak Lounge West at Tressider Union, Stanford
- “Theory, Practice, and Fun”, a lecture in the Autobiographical Reflections series of Stanford's Emeriti Council (view slides)
- Tuesday, June 28, 3:30pm, in McCaw Hall at Stanford
- A keynote talk, “Literate Programming”, for the useR! 2016 Conference (view slides) (view the KS demo program -- corrected version) (watch the video)
- Tuesday July 12, 2:30pm at Westin Boston Waterfront Hotel
- The 2016 Von Neumann Lecture (as part of SIAM's annual meeting AN16), “Satisfiability and Combinatorics” (get the puzzle that was handed out) (view the slides)
- Tuesday September 20, 6pm in the Koret Auditorium of San Francisco Public Library
- A public lecture, “32 years of METAFONT,”
part of the
`Type@CooperWest`program organized by Sumner Stone

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