Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Book Review: The Art of Computer Programming. Volume 4A: Combinatorial Algorithm

samzenpus posted more than 3 years ago | from the read-all-about-it dept.

Book Reviews 176

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 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.

cancel ×

176 comments

Sorry! There are no comments related to the filter you selected.

Boring. (0, Troll)

Anonymous Coward | more than 3 years ago | (#35670042)

I can just, like, do all that in Visual Basic, without reading a bunch of boring words about theories and junk.

Re:Boring. (0)

St.Creed (853824) | more than 3 years ago | (#35670132)

Go away, Troll. The sun's coming up.

Hmm... (0)

MrEricSir (398214) | more than 3 years ago | (#35670418)

You should like someone I went to college with.

Re:Boring. (0)

Anonymous Coward | more than 3 years ago | (#35670486)

oh devxxx, you've forgotten to add a Visual $tudio or Micro$oft link in your post.

QQ

Re:Boring. (3, Funny)

makubesu (1910402) | more than 3 years ago | (#35671182)

YOU CAN'T HANDLE THE KNUTH!

texting from jesus turns up, as it was written, (-1)

Anonymous Coward | more than 3 years ago | (#35670080)

again? different? the guy has timing?

"British archaeologists are seeking to authenticate what could be a landmark discovery in the documentation of early Christianity: a trove of 70 lead codices that appear to date from the 1st century CE, which may include key clues to the last days of Jesus' life. As UK Daily Mail reporter Fiona Macrae writes, some researchers are suggesting this could be the most significant find in Christian archeology since the Dead Sea scrolls in 1947.
The codices turned up five years ago in a remote cave in eastern Jordan—a region where early Christian believers may have fled after the destruction of the Temple in Jerusalem in 70 CE. The codices are made up of wirebound individual pages, each roughly the size of a credit card. They contain a number of images and textual allusions to the Messiah, as well as some possible references to the crucifixion and resurrection. Some of the codices were sealed, prompting yet more breathless speculation that they could include the sealed book, shown only to the Messiah, mentioned in the Book of Revelation. One of the few sentences translated thus far from the texts, according to the BBC, reads, "I shall walk uprightly"--a phrase that also appears in Revelation. "While it could be simply a sentiment common in Judaism," BBC writer Robert Pigott notes, "it could here be designed to refer to the resurrection."
But the field of biblical archaeology is also prey to plenty of hoaxes and enterprising fraudsters, so investigators are proceeding with due empirical caution. Initial metallurgical research indicates that the codices are about 2,000 years old--based on the manner of corrosion they have undergone, which, as Macrae writes, "experts believe would be impossible to achieve artificially.""--yahoo news

Another classic example (-1, Troll)

Hultis (1969080) | more than 3 years ago | (#35670084)

MORE + BOOKS = MONEY

who needs this? (5, Funny)

Anonymous Coward | more than 3 years ago | (#35670096)

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.

Re:who needs this? (0)

Anonymous Coward | more than 3 years ago | (#35670284)

HTML are you serious? Stupid capitalist book anyway.

Re:who needs this? (-1)

Anonymous Coward | more than 3 years ago | (#35671128)

Idiot, you obviously don't know anything about computer programming. The Art of Computer Programming is all about CONCEPTS. If you want a book to hold your hand the entire time, stick to books 'for dummies'. You are clearly the target audience for such books.

Re:who needs this? (4, Funny)

mangu (126918) | more than 3 years ago | (#35671518)

Idiot, you obviously don't know anything about computer programming. The Art of Computer Programming is all about CONCEPTS. If you want a book to hold your hand the entire time, stick to books 'for dummies'. You are clearly the target audience for such books.

May I recommend to you the "Wooosh for Dummies" book?

Re:who needs this? (1)

drooling-dog (189103) | more than 3 years ago | (#35671444)

Algorithms! We don't need no stinkin' algorithms!

Decades in the making! (1, Funny)

Sponge Bath (413667) | more than 3 years ago | (#35670098)

Yeah, but is it in 3-D? All the latest cool tech involves 3-D (soon to be the bell bottoms of this era).

Re:Decades in the making! (0)

Anonymous Coward | more than 3 years ago | (#35670260)

Yes, it uses a ground breaking container format [penny-arcade.com] which is fully 3D.

Re:Decades in the making! (0)

Anonymous Coward | more than 3 years ago | (#35670362)

Yeah, but is it in 3-D? All the latest cool tech involves 3-D (soon to be the bell bottoms of this era).

An algorithm to generate the book in 3-D Form is left as an exercise for the reader.

9/10 ??? (4, Insightful)

condition-label-red (657497) | more than 3 years ago | (#35670106)

After all the Foo for Dummies books that review on /. and rate a 10/10, Donald Knuth just gets a 9/10? Sad...

Re:9/10 ??? (0)

larry bagina (561269) | more than 3 years ago | (#35670240)

30 years since his last book and all he can manage is two chapters.

Re:9/10 ??? (1)

turgid (580780) | more than 3 years ago | (#35670482)

"We only know 3 chords, but they're good ones!" - Status Quo.

Re:9/10 ??? (4, Funny)

gman003 (1693318) | more than 3 years ago | (#35670504)

Be fair - he had to generate every possible combination of characters for a 883 page book, then select the optimal one to be published. Even with a really good algorithm, that's going to take a while.

Have you finished learning the previous volumes? (1)

billstewart (78916) | more than 3 years ago | (#35670978)

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.

Re:Have you finished learning the previous volumes (1)

errandum (2014454) | more than 3 years ago | (#35671890)

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. :(

Re:9/10 ??? (1)

Rene S. Hollan (1943) | more than 3 years ago | (#35670538)

I think Knuth would agree that no work is ever perfect, and be satisfied with 9/10.

I once had a grad school prof who would never give perfect marks on assignments (we had weekly assignments in addition to papers and other work), for the same reason. He would even takes 1/4 marks off (out of 10) for spelling and typographical errors.

I once received an assignment back, marked 9-3/4 / 10. I hurried through the paper to find the error. Apparently there was a ribbon defect in the ribbon I used to print the final draft and an "r" had the hook of the letter broken in the middle. The red note beside it was "-1/4: did not proof read".

Re:9/10 ??? (1)

by (1706743) (1706744) | more than 3 years ago | (#35670724)

I'm betting you either loved that prof or absolutely hated him. Hopefully the former!

Re:9/10 ??? (2)

Hijacked Public (999535) | more than 3 years ago | (#35670780)

Was the prof Edward Tufte?

Marking off for spelling and typography (1)

billstewart (78916) | more than 3 years ago | (#35671020)

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.)

Weight training for the mind (1)

Nefarious Wheel (628136) | more than 3 years ago | (#35671250)

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.

Re:Weight training for the mind (0)

Anonymous Coward | more than 3 years ago | (#35671294)

Umm.. I assure you that SEND+MORE=MONEY has a solution (unique).... Without spoiling it completely M=1.

Work on your mental weight training a tad bit more.

Re:9/10 ??? (1)

GreatBunzinni (642500) | more than 3 years ago | (#35671058)

The sad part is that quite possibly the only reason the book was given a 9/10 is because it is Knuth's book. Otherwise, as any other book on combinatorial algorithms, the book would never be reviewed, as the author doesn't have the faintest grasp on the subject, and this book review would be again dedicated to vacuous "learn X in n hours" books.

Knuth, it may get you a job. (4, Interesting)

perpenso (1613749) | more than 3 years ago | (#35670152)

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.

Re:Knuth, it may get you a job. (5, Funny)

falzer (224563) | more than 3 years ago | (#35670414)

I just tell potential employers that I ascended Nethack multiple times.

Re:Knuth, it may get you a job. (1)

hugetoon (766694) | more than 3 years ago | (#35670424)

Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

Re:Knuth, it may get you a job. (1)

chemicaldave (1776600) | more than 3 years ago | (#35670590)

Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

That all depends on how the questions were presented. Was it a fill in the blank style question which really is trivia, or did it ask the participant to analyze actual code and determine the complexity himself? My hunch tells me it was a memorization type question, in which case his answer was pretty clever.

Re:Knuth, it may get you a job. (1)

perpenso (1613749) | more than 3 years ago | (#35670690)

Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

Actually when I took that test I had already designed programming tests for job interviews at my previous employer. One of my first tasks at the new employer was to create a new test. I realize creating such tests is hard. The problem with the one I took was that the author had not really put much effort into it. It looked liked someone copied questions from undergraduate computer science quizzes.

Re:Knuth, it may get you a job. (1)

tixxit (1107127) | more than 3 years ago | (#35670760)

That's true, but I think the question is bad on principle. I think a better question would be to give the interviewee a problem, and ask them what algorithm they'd use to solve it and why. For instance, what sorting algorithm (or data structure) would you use in the following situations, and why?

  1. Handle online sorting of packets that are usually in-order already, but occasionally not?
  2. Sort a terrabyte of data?
  3. Sort a list of ~1000 items in memory?

This is better because it doesn't require the person to remember specific details, but just understand the underlying concepts (which are much harder to forget).

Re:Knuth, it may get you a job. (1)

spiffmastercow (1001386) | more than 3 years ago | (#35671244)

smoothsort, mergesort, quicksort. where's my job?

Re:Knuth, it may get you a job. (1)

Dails (1798748) | more than 3 years ago | (#35671612)

Your answer should be "Smoothsort, how much data per item to sort, how big is each item," since two objects each containing 500GB of data would be way easier to sort than 20,0000 objects each containing 5MB of data.

Maybe that's why you can't find your job :)

Re:Knuth, it may get you a job. (1)

spiffmastercow (1001386) | more than 3 years ago | (#35671772)

Your answer should be "Smoothsort, how much data per item to sort, how big is each item," since two objects each containing 500GB of data would be way easier to sort than 20,0000 objects each containing 5MB of data.

Maybe that's why you can't find your job :)

Well, in fairness, mergesort is going to work pretty well in either of those situations. But I'll admit that I was assuming that the unit of data was at least smaller than a block of disk space, which is where mergesort comes in, as it can work on small amounts of data (4-8kb, or whatever the block size is for the file system), then sort those blocks by their file index, and then groups of files by their file index, and so on up the chain.

Re:Knuth, it may get you a job. (1)

Mindcontrolled (1388007) | more than 3 years ago | (#35671412)

Nah, the real question to ask is whether bogosort or bozosort is less efficient... That shows the true wizard.

Re:Knuth, it may get you a job. (2)

ShavedOrangutan (1930630) | more than 3 years ago | (#35670664)

Did the position give you the opportunity to apply that knowledge?

Re:Knuth, it may get you a job. (2)

perpenso (1613749) | more than 3 years ago | (#35670870)

Did the position give you the opportunity to apply that knowledge?

Yes. I needed to sort data in a time critical manner. I thought about the nature of my data, mostly already sorted, consulted Knuth's summary table and tried the algorithm he identified as having good performance on data of that nature. After implementation I profiled a run with a large data set and the sorting code barely showed up, 1% execution time. Good enough, moved on to next task.

Re:Knuth, it may get you a job. (2)

A nonymous Coward (7548) | more than 3 years ago | (#35670752)

Excellent section on sorting. I sped up a sort program 100x using that, after much study and fine tuning. This was back in the late 70s on an 8 bit machine with 8k of RAM to play with. Several years later, we switched hardware and interviewed some clown, who, when asked what he would do, said he would allocate a 1MB array and use bubble sort. Ouch!

Re:Knuth, it may get you a job. (2)

billstewart (78916) | more than 3 years ago | (#35671132)

I remember when I first got to use Virtual Machines, on an IBM VM/CMS system back in the mid-late 70s. You could define a virtual machine with a whole megabyte of storage! That was as big as a quarter of the physical RAM on the whole mainframe, not that it would actually all be in core at once!

And yeah, Knuth's volume on searching and sorting was really important when computers had that kind of scale, and the principles mostly still apply even now when disk drives are the slow part and tapes don't exist.

wait a minute (4, Funny)

Anonymous Coward | more than 3 years ago | (#35670154)

Someone actual read The Art of Computer Programming? Are you sure it wasn't just sitting on your shelf?

Re:wait a minute (2)

fishbowl (7759) | more than 3 years ago | (#35670332)

I often found the whole focus on the MIX hypothetical machine to be counterproductive to learning the material. I always went to CLR first for anything, and to Knuth for certain things where I wanted more depth or just a different explanation. Knuth's pseudocode resonates with me fairly well, but MIX examples tended to just give me headaches. Yes, I did read the introduction, and yes I'm glad he didn't try to use any of the languages that were in vogue in 62.

Re:wait a minute (0)

Anonymous Coward | more than 3 years ago | (#35671208)

I liked how MIX was used specifically because it's a really fucking weird (theoretical) machine. It proved that the algorithms are universal, and not dependent on 8 bit bytes and 32 bit words or whatever.

Re:wait a minute (1)

billstewart (78916) | more than 3 years ago | (#35671364)

Languages in vogue in 62? (Not that the first volume actually shipped until 68...)

  • That would be Algol, which would have been a great language for Knuth to teach in (and the CACM used it for most articles about algorithms for years, though they still tended to be in Fortran then.)
  • LISP was around, but was sufficiently abstract that it wouldn't have matched most of the things Knuth was trying to teach because it doesn't have the physicality.
  • But even F0RTRAN II would have been better than Knuth's pseudocode for most of his examples, if you got a newer version that had COMPLEX numbers.
  • COBOL had enough header baggage that it would be awkward, and I don't know if the early COBOLs could have done the job or not.
  • Assembler languages? Most of them would have been more clear than MIX, though I can understand not wanting to show manufacturer favoritism, and there were some weird ones that would have been worse. The PDP-1 came out in 61, but I'm not sure how many were around that early, and the 1965 PDP-8 was wildly successful but Knuth was probably well into writing and not willing to abandon MIX by then.

Re:wait a minute (2)

martyros (588782) | more than 3 years ago | (#35671778)

Yeah -- I bought the first three as a set, but I never could bring myself to invest the effort to learn an imaginary language. The book could have been written in a very simplified C, which can be trivially reduced to assembly if need-be, but can be easily read by nearly any programmer today. His books could have a much wider impact if they were translated into something that had a lower barrier-to-entry.

In Real Genius... (1)

HiggsBison (678319) | more than 3 years ago | (#35670642)

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. :-)

Re:wait a minute (0)

Anonymous Coward | more than 3 years ago | (#35670652)

actually read it cover to cover, all 3 books, and these new ``books''. It's actually an ok "subway" book---just read a few pages every commute.

Re:wait a minute (1)

Citizen of Earth (569446) | more than 3 years ago | (#35670674)

What? It has words inside??

Re:wait a minute (1)

chienyul (239641) | more than 3 years ago | (#35670856)

In Seinfeld's words, "great great book if I may say so. I almost read the whole thing".

Re:wait a minute (1)

makubesu (1910402) | more than 3 years ago | (#35671166)

I've been meaning to read my copy, but what will keep my paper held down?

More Knuth is Always Welcome (3, Interesting)

Millennium (2451) | more than 3 years ago | (#35670178)

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?

Re:More Knuth is Always Welcome (1)

petermgreen (876956) | more than 3 years ago | (#35670366)

not because of any slowness on his part

He banged out volumes 1, 2 and 3 over about 5 years. It's been nearly 40 years since then with relatively little progress. Something has slowed knuth down big time whether it is other commitments, reduction in mental capacity, inceasing complexity of the work or some combination thereof.

Re:More Knuth is Always Welcome (0)

Anonymous Coward | more than 3 years ago | (#35670516)

He has ditched the internet, so he's made better progress lately. His lolcat contributions will be missed though.

Re:More Knuth is Always Welcome (4, Funny)

larry bagina (561269) | more than 3 years ago | (#35670526)

That something was TeX. Have you ever tried using it? We're lucky he got part A out. The entire chapter (not just part A) would have been published 30 years ago if he hadn't been dicking around with the font, margins, gutters, line breaks, etc.

Re:More Knuth is Always Welcome (1)

gewalker (57809) | more than 3 years ago | (#35670918)

I don't understand. Is he part of the Duke Nuke'm Forever development team?

I love this story [ed-thelen.org] about Donald Knuth writing an Algol compiler during the summer of 1960

Re:More Knuth is Always Welcome (1)

billstewart (78916) | more than 3 years ago | (#35671384)

There was this little thing called TeX that occupied a bit of his time....

Last time I saw Knuth, he was over at Techshop making stuff on the laser cutter.

Re:More Knuth is Always Welcome (1)

assantisz (881107) | more than 3 years ago | (#35670904)

Well, according to his own website (http://www-cs-faculty.stanford.edu/~knuth/taocp.html) his plan is to finish volume 5 by 2020 and will then revisit volumes 1-3 to update them. And only then, and if he's still alive, will ge start on volumes 6 and 7, which he doesn't count as "central core of computer programming for sequential machines", though.

Re:More Knuth is Always Welcome (1)

vlm (69642) | more than 3 years ago | (#35670982)

Well, according to his own website (http://www-cs-faculty.stanford.edu/~knuth/taocp.html) his plan is to finish volume 5 by 2020 and will then revisit volumes 1-3 to update them. And only then, and if he's still alive, will ge start on volumes 6 and 7, which he doesn't count as "central core of computer programming for sequential machines", though.

In his latest book collected papers on fun and games he referred to it as his last book. Hopefully his last book as in last book of the "collected papers" series.

Hope it's not a cliff hanger (1)

Hatta (162192) | more than 3 years ago | (#35670194)

Decades in the making, and all he can complete is Volume 4A part 1. How long for part 2? Will we ever see 4B?

Re:Hope it's not a cliff hanger (1)

c0lo (1497653) | more than 3 years ago | (#35671514)

Decades in the making, and all he can complete is Volume 4A part 1. How long for part 2? Will we ever see 4B?

All I can say: we'll see it after DNF is released... marketing reasons: too many miracles in the same time come with risk of trivializing them.

Combinatorics and Permutations! (1)

geek2k5 (882748) | more than 3 years ago | (#35670204)

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.

Get this trash out of my Slashdot! (0)

Anonymous Coward | more than 3 years ago | (#35670220)

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 never read things like this (1)

bigsexyjoe (581721) | more than 3 years ago | (#35670254)

I spend all day writing Model-View-Controller, DAOs, debugging, and writing JavaScript. Reading rich algorithmic stuff really just makes me sad.

Re:I never read things like this (1)

Anonymous Coward | more than 3 years ago | (#35670338)

And that, dear Arsegroper, is why you never be a Master.

Re:I never read things like this (0)

Anonymous Coward | more than 3 years ago | (#35670374)

Yeah but some(read: team leaders) engineering types always claim that a good algorithm is "too academic for real use", despite the fact that most would probably be easier to implement than that bug prone three hashmaps + one stack "real world algorithm" they use to sum negative numbers.

Re:I never read things like this (1)

bigsexyjoe (581721) | more than 3 years ago | (#35670606)

Yup. If you're boss doesn't understand it, you can't use it. Or at least not make it central to your architecture. Trying to put in anything advanced is met with condescension at best.

Besides all that, most of what the work in the real world is just MVC, DAO, with an occasional webservice, or AJAX thing thrown in. If our clients can benefit from more, the people selling our service can't explain it anyway.

Re:I never read things like this (1)

billstewart (78916) | more than 3 years ago | (#35671420)

Yeah. I remember when I was running the machines that some physicists were using to do a networking simulation. Their core loop was grunging through a linked list to find the next event. I was disappointed that turning it into a heap only tripled the speed of the whole application, but the data set was large enough that the machine had to page it in and out, and there were other parts of the program that took time also, but until we fixed the event list, they weren't the dominant time-wasters.

Re:I never read things like this (2)

JoeD (12073) | more than 3 years ago | (#35670400)

Your comment makes me sad. You're missing so much really beautiful stuff that will help you in ways that you can't even imagine, and you don't even know it.

Re:I never read things like this (2)

bigsexyjoe (581721) | more than 3 years ago | (#35670650)

Like I said above, the people selling to the client understand little, so nothing complex is sold to them. Besides, you can't really use an algorithm your boss doesn't understand, can you? Knuth is the enticement into the world of programming, but the reality is usually grinding out crap for businesses.

Re:I never read things like this (1)

idontgno (624372) | more than 3 years ago | (#35671178)

Good point.

The pipefitter may admire and envy the sculptor, but the pipefitter that tries arranging the plumbing into something like a Highfield [annawilihighfield.com] is the pipefitter that loses his job and his union card.

Still, I don't think you should just walk away from Knuth, even if it doesn't pay the bills. Some parts of Knuth are art. Some parts of Knuth are more like craft. Some parts of Knuth is just basic workmanship. I recommend reading it for your own edification, just like the pipefitter may want to be an amateur sculptor in his off hours. (And who knows, maybe hit it big and ditch his pipefitting gig.)

Read, learn and move on (0)

Anonymous Coward | more than 3 years ago | (#35671414)

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!)

Re:I never read things like this (0)

Anonymous Coward | more than 3 years ago | (#35671686)

Model-View-Controller, DAOs, and even JavaScript are but passing fancies and in time may fade but Math is forever.

Combines all the Volume 4 fascicles (4, Informative)

jmcbain (1233044) | more than 3 years ago | (#35670312)

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:

  • Volume 4 Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
  • Volume 4 Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
  • Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)
  • Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)
  • Volume 4 Fascicle 4, Generating All Trees; History of Combinatorial Generation (2006)

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.

Re:Combines all the Volume 4 fascicles (2)

vlm (69642) | more than 3 years ago | (#35670636)

If anyone knows of definitive and comprehensive readings for other engineering fields like EE, CivilE, or ChemE, I'd like to know of them.

Closest I've got for EE is either the classic "Art of Electronics" or an ARRL handbook...

Re:Combines all the Volume 4 fascicles (1)

fwice (841569) | more than 3 years ago | (#35670840)

Closest I've got for EE is either the classic "Art of Electronics" or an ARRL handbook...

Completely agree on "The Art of Electronics". I'm curious what other people mention. My go-to books as an ECE are TAOCP, TAOE, and "Introduction to Algorithms" by Rivest et. al.

On the second tier are "The Practice of Programming" by Kernighan & Pike, "Hacker's Delight" by Warren, "The Pragmatic Programmer" by Hunt & Thomas, and a bunch of even more specific books on DSP, Stoch, and C. But these are a bit more subject specific and 'opinion' then reference a la the first tier.

Re:Combines all the Volume 4 fascicles (0)

Anonymous Coward | more than 3 years ago | (#35670698)

Newton's Principia?

Re:Combines all the Volume 4 fascicles (1)

Rostin (691447) | more than 3 years ago | (#35670990)

For chemical engineering: Perry's Chemical Engineers' Handbook.

Re:Combines all the Volume 4 fascicles (1)

metlin (258108) | more than 3 years ago | (#35671022)

For a while, Resnick & Halliday was the mecca for Physics, and Morrison & Boyd for Organic Chem. Can't really speak to other areas.

Re:Combines all the Volume 4 fascicles (0)

Anonymous Coward | more than 3 years ago | (#35671454)

You can get the pre-fascicles from here: http://cs.utsa.edu/~wagner/knuth/

Re:Combines all the Volume 4 fascicles (0)

Anonymous Coward | more than 3 years ago | (#35671520)

Encyclopedia of Optimization is pretty comprehensive, and applicable to most engineering disciplines as well as CS. If you use optimization techniques for analysis or machine learning, or have interest in those subjects then it is probably worth the $2000 or so price tag as it gives critical insight into how various techniques relate to one another and how to blend different approaches to solve a problem more efficiently.

It is a compilation of work written by various authors so not cohesive like Knuth; however, it is similar in that it has a wide scope and covers both theory and practice in depth.

http://www.amazon.com/gp/product/0387747583/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0792369327&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=1PNAD8E179E4RM7K6W81

Re:Combines all the Volume 4 fascicles (1)

Henk Poley (308046) | more than 3 years ago | (#35671680)

"Molecular Biology of the Cell" (colloquially: The Cell), is kind of like TAoP for cell biology. It's not short though. But combining all the TAoP Volume 4 Fascicles together, you are already at a large fraction of the amount of pages in The Cell. So I guess it's what you are looking for.

only for a select few (-1)

Anonymous Coward | more than 3 years ago | (#35670354)

They'll be a nice addition to the other pristine volumes on your "personality bookshelf", next to Atlas Shrugged, On The Road, and Gravity's Rainbow.

His books are incredibly impenetrable for the self-taught programmer. Only students of advance academic computing theory can actually glean anything from them.

Very similar to circuit theory: the academic texts are primarily S-domain transfer functions and advanced calculus. Very different for our "instructables" DIY culture.

Re:only for a select few (1)

fishbowl (7759) | more than 3 years ago | (#35670406)

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.)

Knuth volumes are approachable and practical (2)

perpenso (1613749) | more than 3 years ago | (#35670572)

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.

Re:only for a select few (3, Insightful)

billstewart (78916) | more than 3 years ago | (#35671470)

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.

Damn it (1)

jDeepbeep (913892) | more than 3 years ago | (#35670598)

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.

Re:Damn it (1)

Imagix (695350) | more than 3 years ago | (#35670770)

You could just buy the 4-book slipcase... it even comes with a bonus copy of volumes 1-4 that you can give to someone else! :)

but the real question is: (0)

Anonymous Coward | more than 3 years ago | (#35670952)

is there anything here that isn't in wikipedia already?

easy problem is easy (1)

marcello_dl (667940) | more than 3 years ago | (#35670956)

SEND + MORE = MONEY
0001 + 0001 = 00010

The Art Of Cheating, Problem?

Re:easy problem is easy (2)

kruhft (323362) | more than 3 years ago | (#35671120)

You set E to both 0 and 1.

Re:easy problem is easy (1)

Matthew Weigel (888) | more than 3 years ago | (#35671214)

So E represents 0 and/or 1?

Re:easy problem is easy (1)

MBCook (132727) | more than 3 years ago | (#35671480)

It's a quantum E.

Re:easy problem is easy (2)

Whatsisname (891214) | more than 3 years ago | (#35671488)

More like the Art of Failing, in your case.

Programming (1)

Peter656 (886166) | more than 3 years ago | (#35671026)

I have a 10 year old son who wants to learn programming. Any ideas?

Cookbook? (1)

Major Variola (ret) (1980538) | more than 3 years ago | (#35671124)

I await his ten thousand page book on cooking...

Partition Numbers in the News (3, Interesting)

lee1 (219161) | more than 3 years ago | (#35671232)

A stunning result [plos.org] probably too recent to have made it in to the book under review: we now have a closed-form formula for the partition numbers.

While Knuth may be the authority on algorithms, (1)

Yxven (1100075) | more than 3 years ago | (#35671814)

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.)

Fix the article title (0)

Anonymous Coward | more than 3 years ago | (#35671818)

please

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?