Recent News
Recent News
[click here to zip down to the schedule of public events]
a curious progression of factors that can also be premultiplied by $(-1)^8$ and written $\prod_{k=0}^4 (2k-1)^{8-2k}$. (Others write $\bigl(\sum_{k=0}^9 k\bigr)^2$, or $\sum_{k=0}^9 k^3$.)
Oliver Manger sent me a delightful image of “dancing lynx”
for my `\W-th birthday!
Johan de Ruiter has discovered π in SuperSlitherlink (an extension of classic Slitherlink that was invented by the prolific puzzle author Michael Rios)! The problem is to form a single loop by connecting dots with horizontal and vertical lines that conform to a given set of k×k clues: Each clue specifies the number of edges that belong to the loop and lie on the boundary of a k×k subsquare. Furthermore, no edges lie inside that subsquare.
Ordinary Slitherlink limits all clues to the case k=1, but
the SuperSlitherlink puzzle
has both 2×2 and 3×3 clues.
(Here is its solution.)
So put on your thinking cap: Can you solve Johan's new 10-digit puzzle?
(He has another, considerably tougher, that extends to 18 digits!)
… and living in Cleveland!
Olin Hall at Case Western Reserve University, home of the Computer and Data Sciences department, has just celebrated the completion of a major renovation project. In the spring of 2024 I was asked for advice about special artwork that might be appropriate to include in the remodeled building. This was a thrilling prospect for me, because I've long been a fan of “Geek Art” — artwork that appeals to both halves of people's brains by being doubly beautiful, having both visual beauty and scientific beauty. (See Chapter 47 in my Selected Papers on Fun and Games.) What better place for Geek Art than the walls of a thriving CS department?
Thus began an exciting collaboration with the CWRU design team, led by Kathleen Barrie. We decided to focus on the intriguing patterns called knight's tours — the longest possible sequences of knight moves on a chessboard, or on similar boards of different sizes. These striking patterns are not only eye-catching, they also rank among the earliest achievements in combinatorial mathematics and graph theory, because they have a venerable history going back more than 1200 years to ancient Kashmir.
Many different species of knight's tours can now be seen on the walls of Olin Hall, near the elevators on floors 3, 4, and 8. Closeup views and details about their surprisingly subtle properties can be found here. (All of these photographs are due to Jerry Birchfield of Field Studio Photography.)
Long ago, when I was a student at Case Institute of Technology, the computer center was directed by Fred Way III, an enlightened professor who allowed dozens of undergraduates like me to write software for the entire campus. Those halcyon days have been immortalized in a “light box” display, designed by Tim Lachina, that now greets students and visitors when they enter Case's newly refurbished Olin Hall.
In fact there actually are two light box displays: On the left is a collage that features images from the 1950s, exemplifying the creative spirit that was rampant when I had the good fortune to spend days and nights with Case's first computers. (It also shows excerpts from the 1960 student handbook — a project that I worked on with Jill Carter, who became my wife a year later.)
Around the corner and to the right is a second collage, which features images from my subsequent life as a computer scientist, covering more than sixty years of Theory and Practice and Fun.
Just before the end of February my publisher (Addison–Wesley) sent me my first copies of Volume 4, Fascicle 7 of The Art of Computer Programming, entitled “Constraint Satisfaction.”
People who wish to purchase copies of this 304-page paperback for themselves can get the best deal at informIT.com; that website also has the publisher's traditional hype about the great stuff inside. (Or, you can see a free preview of the whole thing in compressed PostScript form: Prefascicle f7a. The contents of that prefascicle agrees fairly well with the contents of the first paperback printing of Volume 4, Fascicle 7, except for parts of the index. As usual, the prefascicle is “frozen” and will not be maintained, while the paperback will gradually improve with time.)
The fourth “volume” of The Art of Computer Programming deals with Combinatorial Algorithms, the area of computer science where nonobvious techniques have the most dramatic effects. I love it the most, because one good idea can often make a program run a million times faster. It's a huge, fascinating subject, and Part 1 (Volume 4A, 883 pages, now in its twenty-fourth printing) was published in 2011; Part 2 (Volume 4B, 714 pages, now in its second printing) was published at the close of 2022. The first 275 or so pages of Volume 4C have just appeared in print, as announced above, together with an index.
While preparing many of the new exercises in Volumes 4B and 4C, I spent a lot of time 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 on 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 the finer points out carefully as yet.
I still cling to a belief that such details are extremely instructive. 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 exercise numbers:
(If you're depressed by current world news, you might find some solace by immersing yourself in a bit of research into eternally beautiful patterns.)
Please don't be alarmed by the highly technical nature of these examples; more than 750 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). Thanks in advance!
By the way, if you want to receive a reward check for discovering an error in TAOCP, your best strategy may well be to scrutinize the answers to the exercises that are listed above.
Preliminary sketches of material that will be in later parts of Volume 4C have also been drafted, and courageous readers who have nothing better to do might dare to take a peek at the comparatively raw copy in these “prefascicles.” One can look, for instance, at Pre-Fascicle 8a (Hamiltonian Paths and Cycles); Pre-Fascicle 9b (A Potpourri of Puzzles). Thanks to Tom Rokicki, those PostScript files are now searchable!
I seem to get older every day, and people keep asking me to reminisce about the glorious days of yore. If you're interested in checking out some of those videos and other archives, take a look at my news page for 2020, which I've updated with a few items captured after that year.
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.
Don Knuth's home page
