Slashdot Mirror
Book Review: The Art of Computer Programming. Volume 4A: Combinatorial Algorithm
asgard4 writes "Decades in the making, Donald Knuth presents the latest few chapters in his by now classic book series The Art of Computer Programming. The computer science pioneer's latest book on combinatorial algorithms is just the first in an as-of-yet unknown number of parts to follow. While these yet-to-be-released parts will discuss other combinatorial algorithms, such as graph and network algorithms, the focus of this book titled Volume 4A Combinatorial Algorithms Part 1 is solely on combinatorial search and pattern generation algorithms. Much like the other books in the series, this latest piece is undoubtedly an instant classic, not to be missing in any serious computer science library or book collection." Keep reading for the rest of asgard4's review.
The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1
author
Donald E. Knuth
pages
883
publisher
Addison-Wesley Publishing
rating
9/10
reviewer
asgard4
ISBN
0-201-03804-8
summary
Knuth's latest masterpiece. Almost all there is to know about combinatorial search algorithms.
The book is organized into four major parts, an introduction, a chapter on Boolean algebra, a chapter on algorithms to generate all possibilities (the main focus of the book), and finally 300 pages of answers to the many exercises at the end of every section in the book. These exercises and answers make this work an excellent companion for teachers of a university course.
The book begins with some introductory examples of combinatorial searching and then gives various definitions of graphs and directed acyclic graphs (DAGs) since a lot of combinatorial algorithms conveniently use graphs as the data structures they operate on. Knuth's writing style is terse and to the point, especially when he presents definitions and proofs. However, the text is sprinkled with toy problems and puzzles that keep it interesting.
After the introduction, the first chapter of the book (out of only two) is titled "Zeros and Ones" and discusses Boolean algebra. Most readers that have studied computer science in some form should be intimately familiar with most of the discussed basics, such as disjunctive normal forms and Boolean functions and their evaluation. The reader might be surprised to find a discussion of such an elemental foundation of computer science in a book on combinatorial algorithms. The reason is that storage efficiency is especially important for these types of algorithms and understanding the basic storage unit of computer systems nowadays (as the decimal computer is a definite thing of the past) is of importance.
After covering the basics of Boolean algebra and Boolean functions in quite some detail, Knuth gets to the most fun part of this chapter in my opinion: the section on bitwise tricks and techniques on integer numbers. Being a software engineer in the video games industry, I recognized a lot of the techniques from my day-to-day work, such as bit packing of data and various bit shifting and bit masking tricks. There is also a discussion of some interesting rasterization-like algorithms, such as the shrinking of bitmaps using Levialdi's transformation or filling of regions bounded by simple curves. The chapter concludes with Binary Decision Diagrams that represent an important family of data structures for representing and manipulating Boolean functions. This topic was also quite interesting to me since I have never been exposed to it before.
The second and main chapter of the book is titled "Generating All Possibilities". In this particular volume of the The Art of Computer Programming series, the only subsection of the chapter in this volume is on generating basic combinatorial patterns, or more specifically generating all n-tuples, permutations, combinations, partitions, and trees. We can expect more on this topic from Knuth in his continuation in Volume 4B and beyond.
The discussion on n-tuples starts out with a lengthy focus on Gray codes, which are binary strings of n bits arranged in an order such that only one bit changes from string to string.
A quite fun example for generating all permutations presented in this part of the book is alphametics, also sometimes known as verbal arithmetic — a kind of puzzle where every letter of a word stands for a digit and words are used in equations. The goal is to assign digits to letters in such a way that the equation is correct. A classic example is SEND + MORE = MONEY (the solution is left as an exercise for the reader).
The next section deals with generating all combinations. Given a set of n elements, the number of all possible combinations of distinct subsets containing k elements is the well-known binomial coefficient, typically read as "n choose k". One of the more interesting algorithms in this section of the book to me was generating all feasible ways to fill a rucksack, which can come in quite handy when going camping.
After combinations, Knuth moves on to briefly discuss integer partitions. Integer partitions are ways to split positive integer numbers into sums of positive integers, disregarding order. So, for example 3, 2+1, and 1+1+1 are the three possible partitions of the integer 3. Knuth, in particular, focuses on generating all possible integer partitions and determining how many there are for a given number. The book continues with a concise presentation of the somewhat related topic of set partitions, which refer to ways of subdividing a set of elements into disjoint subsets. Mathematically, a set partition defines an equivalence relation and the disjoint subsets are called equivalence classes; concepts that should be familiar to any mathematics major. Again, the focus is on generating all possible set partitions and determining how many partitions can be generated.
The main part of the book closes with a discussion of how to exhaustively generate all possible trees, which is a topic that I have never given much thought to. I am familiar with generating permutations, combinations, and partitions, but have never really been confronted with generating all possible trees that follow a certain pattern. One main example used throughout this part of the book is generating all possible strings of nested parentheses of a certain length. Such strings can be represented equivalently as binary trees.
Knuth's latest book is comprehensive and almost all encompassing in its scope. It compiles an incredible amount of computer science knowledge on combinatorial searching from past decades into a single volume. As such, it is an important addition to any computer science library. This book is not necessarily an easy read and requires a dedicated reader with the intention of working through it from front to back and a considerable amount of time to fully digest. However, for those with patience, this book contains a lot of interesting puzzles, brain teasers, and almost everything there is to know on generating combinatorial patterns.
On a final note, if you don't have volumes 1-3 yet you can get all volumes in a convenient box set .
Martin Ecker has been involved in real-time graphics programming for more than 10 years and works as a professional video game developer for High Moon Studios http://www.highmoonstudios.com/ in sunny California.
You can purchase The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1 from amazon.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
The book begins with some introductory examples of combinatorial searching and then gives various definitions of graphs and directed acyclic graphs (DAGs) since a lot of combinatorial algorithms conveniently use graphs as the data structures they operate on. Knuth's writing style is terse and to the point, especially when he presents definitions and proofs. However, the text is sprinkled with toy problems and puzzles that keep it interesting.
After the introduction, the first chapter of the book (out of only two) is titled "Zeros and Ones" and discusses Boolean algebra. Most readers that have studied computer science in some form should be intimately familiar with most of the discussed basics, such as disjunctive normal forms and Boolean functions and their evaluation. The reader might be surprised to find a discussion of such an elemental foundation of computer science in a book on combinatorial algorithms. The reason is that storage efficiency is especially important for these types of algorithms and understanding the basic storage unit of computer systems nowadays (as the decimal computer is a definite thing of the past) is of importance.
After covering the basics of Boolean algebra and Boolean functions in quite some detail, Knuth gets to the most fun part of this chapter in my opinion: the section on bitwise tricks and techniques on integer numbers. Being a software engineer in the video games industry, I recognized a lot of the techniques from my day-to-day work, such as bit packing of data and various bit shifting and bit masking tricks. There is also a discussion of some interesting rasterization-like algorithms, such as the shrinking of bitmaps using Levialdi's transformation or filling of regions bounded by simple curves. The chapter concludes with Binary Decision Diagrams that represent an important family of data structures for representing and manipulating Boolean functions. This topic was also quite interesting to me since I have never been exposed to it before.
The second and main chapter of the book is titled "Generating All Possibilities". In this particular volume of the The Art of Computer Programming series, the only subsection of the chapter in this volume is on generating basic combinatorial patterns, or more specifically generating all n-tuples, permutations, combinations, partitions, and trees. We can expect more on this topic from Knuth in his continuation in Volume 4B and beyond.
The discussion on n-tuples starts out with a lengthy focus on Gray codes, which are binary strings of n bits arranged in an order such that only one bit changes from string to string.
A quite fun example for generating all permutations presented in this part of the book is alphametics, also sometimes known as verbal arithmetic — a kind of puzzle where every letter of a word stands for a digit and words are used in equations. The goal is to assign digits to letters in such a way that the equation is correct. A classic example is SEND + MORE = MONEY (the solution is left as an exercise for the reader).
The next section deals with generating all combinations. Given a set of n elements, the number of all possible combinations of distinct subsets containing k elements is the well-known binomial coefficient, typically read as "n choose k". One of the more interesting algorithms in this section of the book to me was generating all feasible ways to fill a rucksack, which can come in quite handy when going camping.
After combinations, Knuth moves on to briefly discuss integer partitions. Integer partitions are ways to split positive integer numbers into sums of positive integers, disregarding order. So, for example 3, 2+1, and 1+1+1 are the three possible partitions of the integer 3. Knuth, in particular, focuses on generating all possible integer partitions and determining how many there are for a given number. The book continues with a concise presentation of the somewhat related topic of set partitions, which refer to ways of subdividing a set of elements into disjoint subsets. Mathematically, a set partition defines an equivalence relation and the disjoint subsets are called equivalence classes; concepts that should be familiar to any mathematics major. Again, the focus is on generating all possible set partitions and determining how many partitions can be generated.
The main part of the book closes with a discussion of how to exhaustively generate all possible trees, which is a topic that I have never given much thought to. I am familiar with generating permutations, combinations, and partitions, but have never really been confronted with generating all possible trees that follow a certain pattern. One main example used throughout this part of the book is generating all possible strings of nested parentheses of a certain length. Such strings can be represented equivalently as binary trees.
Knuth's latest book is comprehensive and almost all encompassing in its scope. It compiles an incredible amount of computer science knowledge on combinatorial searching from past decades into a single volume. As such, it is an important addition to any computer science library. This book is not necessarily an easy read and requires a dedicated reader with the intention of working through it from front to back and a considerable amount of time to fully digest. However, for those with patience, this book contains a lot of interesting puzzles, brain teasers, and almost everything there is to know on generating combinatorial patterns.
On a final note, if you don't have volumes 1-3 yet you can get all volumes in a convenient box set .
Martin Ecker has been involved in real-time graphics programming for more than 10 years and works as a professional video game developer for High Moon Studios http://www.highmoonstudios.com/ in sunny California.
You can purchase The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1 from amazon.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
I can just, like, do all that in Visual Basic, without reading a bunch of boring words about theories and junk.
I already have the entire O'Reilly library, plus selected volumes from the "for dummies" and "...in 21 days" series. Why do we need another lousy computer book? This one doesn't even appear to cover anything useful like HTML coding or Adobe software.
Yeah, but is it in 3-D? All the latest cool tech involves 3-D (soon to be the bell bottoms of this era).
After all the Foo for Dummies books that review on /. and rate a 10/10, Donald Knuth just gets a 9/10? Sad...
Lorem ipsum dolor sit amet, consectetuer adipiscing elit.
Much like the other books in the series, this latest piece is undoubtedly an instant classic, not to be missing in any serious computer science library or book collection.
During a job interview I was given a test. Some questions/problems were good, other were not. One of the not-so-good questions presented 8 or so sorting algorithms and asked for their run time complexity (O notation). I answered bubble sort and quick sort and then added that I bought Knuth vol 3 so I didn't have to memorize such trivia. I'm not sure the engineer who created and graded the test liked the answer but the manager of the team (not an engineer) loved the answer after I explained what Knuth vol 3 was. I got hired.
Someone actual read The Art of Computer Programming? Are you sure it wasn't just sitting on your shelf?
Knuth's books are awesome, not just for the content (which would itself be a bargain at quadruple the price) but also for the sheer intimidation factor.
However, I've got to admit: the volumes I'm most looking forward to -5, 6, and 7- are yet to come. This bothers me, because with the way Volume 4 keeps growing, I'm no longer convinced that he's going to live long enough to finish the series, not because of any slowness on his part but because the work just keeps getting bigger and bigger. Has he made arrangements for others to finish the series in case the worst happens?
Decades in the making, and all he can complete is Volume 4A part 1. How long for part 2? Will we ever see 4B?
Give me Classic Slashdot or give me death!
Fun stuff. I guess I'll need to buy the book. If you know the theory behind things, you can often do a better job of making things work.
Boooooo! Give me more shill reviews of Packt Publishing books by RickJWagner and his various sockpuppet personalities! We need them to help pay for CmdrTaco's micropenis enlargement surgery! Get this faggot's book out of my Slashdot right now!
I spend all day writing Model-View-Controller, DAOs, debugging, and writing JavaScript. Reading rich algorithmic stuff really just makes me sad.
Democracy Now! - your daily, uncensored, corporate-free
This new book combines all of the previously-published Volume 4 fascicles from 2005 to 2009, all of which I bought last year and am still reading. Those fascicles are:
All the volumes combined are a true masterpiece for the computer science community. I do not know of many other fields in the sciences where the core ideas, both theoretical and practical, are wrapped up so well. The only comparison I know of is The Merck Manual for physicians. If anyone knows of definitive and comprehensive readings for other engineering fields like EE, CivilE, or ChemE, I'd like to know of them.
Knuth's books didn't start making much sense until I took the first semester of Discrete Math. Basically I didn't have many of the problems for which those texts were the solution until then, but I certainly started to benefit from them long before I was into "advanced academic computing" (and continued to benefit during those analysis courses.)
-fb Everything not expressly forbidden is now mandatory.
You should like someone I went to college with.
There's no -1 for "I don't get it."
They'll be a nice addition to the other pristine volumes on your "personality bookshelf" ...
Be forewarned. Some of us who have fairly pristine looking copies today once pooled resources and read a shared copy back in the day.
Only students of advance academic computing theory can actually glean anything from them ... Very different for our "instructables" DIY culture.
I think it is a little more approachable than you suggest. I read it sophomore year of a computer science program, while some proofs were beyond my abilities the concepts and algorithms were not. Basically these volumes can be used as practical references to algorithms and concepts. Part of the popularity of the books is due to its making grad school level work practical, you get the fancy math with greek letters :-) and you get assembly language level implementations.
Also I've know a few DIY'ers who read university level materials on their own initiative. YMMV.
Now my 3 volume slipcased set will look awkward and incomplete and knaw away at me every time I see additional books next to it that I know conceptually belong in the slipcase.
Reply to That ||
In the movie Real Genius, when Jordan is guarding the hallway filled with ice, she's holding a volume of Knuth. Upside down. Sure, a bit of light reading.
So no, it's not just for sitting on the shelf. :-)
My other car is a 1984 Nark Avenger.
is there anything here that isn't in wikipedia already?
SEND + MORE = MONEY
0001 + 0001 = 00010
The Art Of Cheating, Problem?
---- MISSING MISCELLANEOUS DATA SEGMENT --- [sigdash] trolololol
As George R.R. Martin said to fans wanting to know when the next volume of "A Game of Thrones" was coming out, "I'm not your bitch."
Have you worked all the problems in the previous volumes yet, or just the easy ones?
Yeah, ok, me neither :-)
Actually, I'd probably have gotten through much more of the first three volumes if Knuth's coding style wasn't so horrible. There's MIX, which was the ugliest baroque botch of an assembler language out there when he could have taught the same lessons with a simple clean assembler language, and pseudocode, which tended to be ugly spaghetti code that was much harder to follow than either Algol (which had been the CACM standard language for publishing algorithms in for a decade or so) or top-down-structured pseudocode. On the other hand, the math parts were brilliant and clear, and the code did represent them adequately even though it wasn't very readable.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
In a computer course? You betcha! If you're lucky, the compiler will find spelling errors and typos for you, and if you're not, it'll let them through to become runtime errors. When I was in college, we used the Cornell version of the PL/I compiler that auto-corrected mistakes, sometimes even correctly. (Since we were using punchcards, even having it correct them badly was helpful, because it would let more of your program run so you usually find one or two more bugs if you had any.)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
I have a 10 year old son who wants to learn programming. Any ideas?
I await his ten thousand page book on cooking...
A stunning result probably too recent to have made it in to the book under review: we now have a closed-form formula for the partition numbers.
I think Knuth would agree that no work is ever perfect
Which doesn't harm it in the slightest. Bench pressing a barbell will give you the desired effect irrespective of whether you're a half centimetre off at extension. (The metaphor holds -- reading Knuth is weight training for the mind.)
And SEND+MORE=MONEY isn't quite right, it's off by one. SEND+MORE=MONEY-A would work.
Do not mock my vision of impractical footwear
If you love this stuff, then read and learn. You will move on to more interesting work, because it will just become inevitable for you.
I waited far too long to follow my dreams, but I've made several jumps, from systems administration, to development, to technical leadership. I now get to (occasionally) design interesting things involving advanced algorithms, sometimes at the cutting edge of research. I've even had occasion to reference the Art of Computer Programming (but mostly it still sits on my shelf looking cool!)
I never could get more than 10-20 pages into Gravity's Rainbow. And you left out A Brief History of Time.
I forget whether the "advanced academic computing theory" course I first used Knuth in was "CS100" or "CS201", probably the latter. But that was 30+ years ago, and kids these days get to college having been exposed to a bit more than BASIC in high school. And self-taught programmers these days probably don't bother with assembler language unless they're trying to automate toasters (so the "instructables" DIY crowd) or write viruses.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
is he the best teacher?
Put another way, if a motivated student wanted to become a top-notch programmer and cared only about his knowledge and not the bragging rights of being able to read Knuth's books to completion, would you still recommend this series or is there another resource that you would like to share that you think explains the concepts better?
Personally, whenever I pick up one of these books, I get turned off due to having to learn a trivial programming language just to understand the examples. (Not because I think learning it would be difficult but because it feels inefficient. I wouldn't be interested in computer science if efficiency wasn't a main motivation in my life.)
please
No.Neil Gaiman said that GRRM is not your bitch :)
Kuth's books are awesome, too bad he'll most likely die before we get to read all the brilliant things he has yet to write. :(
I respect Knuth for his stand that a man of such technical sophistication does not have to be at odds with faith. In fact, he wrote a pictorial Bible study:
http://www.amazon.com/3-16-Bible-Texts-Illuminated/dp/0895792524
Knuth as quoted from a reviewer:
"it's tragic that scientific advances have caused many people to imagine that they know it all, and that God is irrelevant or nonexistent. The fact is that everything we learn reveals more things that we do not understand... Reverence for God comes naturally if we are honest about how little we know."
I read in the blurb about Gray codes and only one bit changing at a time, eg: 00, 01, 11, 10, 00 (etc). Yep, its how ball mice work. If you are at 10 and suddenly you go to 11, the ball went that-a-way. If you are at 10 and then 00, the ball went the other way. A clock pulse generator, with a 50% duty cycle, and two sensors, which completely cover an entire open 'window' will generate a gray code. So one clock pulse generator with two sensors for one axis (say the x axis), and one clock pulse generator with two sensors for the other axis (say the y axis). The sensor/clock pulse generator sets are arranged at 90 degree angles. Now-a-days though, super-duper optical mice do it a bit differently. Thanks for reading, I'm here till Thursday! Try the veal!
Or were you pointing that out?
Computer memory is just fancy paper, CPUs just fancy pens with fancy erasers; the 'net is just a fancy backyard fence.
If you don't understand the combinatorial stuff, how do you follow calculating the order of a sort?
Computer memory is just fancy paper, CPUs just fancy pens with fancy erasers; the 'net is just a fancy backyard fence.
The dude is 73 years old. There's a good chance we won't see any more volumes from him considering how long this one took. There was a fair amount of doubt that 4a would ever see print.
Now if we can just get those hyperlongevity + brain mapping technologies working...
"Slow down, Cowboy! It has been 3 years, 7 months and 26 days since you last successfully posted a comment."
I thought Barney Fife died a few years ago. Good to know he's still kicking. I like his brand of comedy.
Back in 1983, when I was still in school, I published an article in Dr. Dobb's Journal on how to perform various binary operations efficiently. I also sent a letter to. Knuth describing one algorithm in particular: An efficient means of calculating a weighted sum of the bits in a word.
The minute I put the letter in the mailbox I regretted bothering Knuth with such a trivial matter. I was greatly relieved when there was no response; I assumed the letter had circular-filed.
Then about three years ago I got a phone call from someone working with Knuth. They informed me that after 25 years my letter was about to become an exercise in volume 4A, and asking how I wanted my name to appear in the index. And now the book is out, and there it is: Section 7.1.3, exercise 44.
It goes without saying that I was delighted by what happened. But even more than that, I am in awe of the level of scholarship behind this work, where such a little thing as this algorithm was tracked for almost three decades.
I've never taken an theoretical CS class of any sort, but I read, enjoyed, and understood large chunks of Vols 1-3 back when I was a high school senior. Methinks you seriously underestimate the quality of these books and overestimate the difficulty of reading them.
Where's the eBook. As a matter of principal (and the fact that I don't want to buy a bigger house) I have stored away all my computer books which are available in eBook form whether I've purchased the eBook or not as I can more easily buy it then find the printed copy on my old shelves. I am looking forward to moving all my printed books to the recycling bin in the future. This is 2011, there's just no reason for printed books anymore... well except for going to the book store to find things which look interesting to download.
Please let him know that since we know he keeps the books in Tex format, it's time for a Kindle edition.
These books are useless because everything is expressed in terms of Knuth's ludicrous obfuscatory pseudo-OS. And the typography makes the material look like it was last revised in 1965. Other fonts than Century Schoolbook are available.