Don Knuth releases Volume 4, Pre-fascicle 6A [gzipped ps]

http://www-cs-faculty.stanford.edu/~knuth/fasc6a.ps.gz

by dhruvbird • 14 years ago

141 45 14 years ago

www-cs-faculty.stanford.edu

ScotterC2• 14 years ago

Would prefer a warning that it's a download link.

kinleyd2• 14 years ago

Agreed. The link should have taken us to a page describing what it's about, with the option to download.

Jach2• 14 years ago

I think the title says what's necessary. But if it did link to such a page (there is no such page that describes just this release that I found by googling the url) someone would complain that it's just blogspam, post the download link in their comment, and get upvotes. There were tweets I found that reference it, who knows what sort of anger that would have generated if the submitter linked to a tweet. (There's already discomfort on this page over Knuth just using the word 'tweet'!)

dhruvbird2• 14 years ago

Fixed

insaneirish• 14 years ago

Change the link.

Shorel• 14 years ago

Honestly, what else would you expect?

Reading the TeX source online?

ScotterC2• 14 years ago

I had no idea what it was. When I clicked, all I knew was that I had heard of Donald Knuth before.

jk• 14 years ago

It is not a gzipped file; open with any postscript viewer.

cshesse• 14 years ago

file fasc6a.ps.gz fasc6a.ps.gz: gzip compressed data, was "fasc6a.ps", from Unix, last modified: Thu Jul 26 12:45:44 2012, max compression

cnvogel• 14 years ago

It is gz-compressed, but (1) your browser might decompresses it on the fly after seeing the "Content-Encoding: x-gzip" and (2) most postscript viewers decompress on the fly as gzipped postscript is so prevalent.

    $ curl -s http://www-cs-faculty.stanford.edu/~knuth/fasc6a.ps.gz | dd bs=16 count=1 | xxd

    0000000: 1f8b 0808 689e 1150 0203 6661 7363 3661  ....h..P..fasc6a

eru5• 14 years ago

> [...] most postscript viewers decompress on the fly as gzipped postscript is so prevalent.

Not only prevalent, but also the right thing to do. PDF was an attempt to (among other aims) achieve smaller filesizes than PS. But that was premature optimization: While a PS file is usually bigger than a PDF, gzipped PS beats PDF.

rrmm3• 14 years ago

On page 29, Knuth says, "We can regard both variables and clauses as active agents, who continually tweet to their neighbors in this social network." This in the context of statistical physics.

Seeing Knuth talk about tweets feels weird.

On another note, anyone actually run into a random k-SAT problem in "real life"?

eta_carinae• 14 years ago

> Seeing Knuth talk about tweets feels weird.

Does it make you feel better that he released the book as a .ps?

rrmm3• 14 years ago

I would have preferred a .dvi! (font embedding issues notwithstanding).

dunham2• 14 years ago

The big issue for me are the bitmap fonts. Fortunately he used a modern dvips, so you can run it through "pkfix" to get a version with scalable fonts. (Once it's converted to pdf, it's more challenging to fix.)

repsilat• 14 years ago

On another note, anyone actually run into a random k-SAT problem in "real life"?

Because there's a lot of research into solving SAT "pretty quickly", one of the half-reasonable ways to approach an NP-complete problem is to find an efficient reduction and use a premade SAT solver/heuristic. I don't think nearly as much work has gone into that sort of thing as, say, integer programming (http://en.wikipedia.org/wiki/Integer_programming), but I remember reading something about it a couple of years ago.

Of course, when people realise their problem is NP-complete they tend to go a different way with things. The usual answers are:

1. Problems in practice are small enough for brute-force (or a simple backtracking search)

2. We probably don't need optimality, just use some kind of heuristic or metaheuristic.

3. Too hard, let's do something else.

zeroonetwothree• 14 years ago

Yeah in my experience reductions to IP are simpler and result in smaller problem sizes.

brandall10• 14 years ago

More than weird, will a 'tweet' have relevance 50 years from now? Even a social network? Seems using things that have a temporal cultural context is a bit iffy.

Granted, I haven't mustered the courage to begin reading TAOCP, but my impression is it's a timelessly relevant masterwork for the man.

jacobolus• 14 years ago

The whole thing is filled with dry humor. If you’re not chuckling when you read it, you’re not paying enough attention. :-)

First example from this new section about satisfiability, the epigraphs:

> “He reaps no satisfaction but from low and sensual objects, or from the indulgence of malignant passions.” – David Hume, The Skeptic (1742)

> “I can’t get no ...” — Mick Jagger & Keith Richards, “Satisfaction” (1965)

Or an example from the text, from a few pages later on:

> “Start with any truth assignment. While there are unsatisfied clauses, pick any one, and flip a random literal in it.”

> Some programmers are known to debug their code in a haphazard manner, somewhat like this approach, and we know that such “blind” changes are foolish because they usually introduce new bugs....

kcl• 14 years ago

"Tweet" is such a good replacement for "asynchronously broadcast" that it won't matter whether Twitter is still around. The meaning is clear from context. It would not surprise me if "tweet" became a reserved word in computer science research.

Zenst• 14 years ago

Bit off topic, but I have to say "temporal cultural context" is pure wordsmith genius. Thank you.

rrmm3• 14 years ago

> More than weird, will a 'tweet' have relevance 50 years from now? Even a social network? Seems using things that have a temporal cultural context is a bit iffy.

I don't think Knuth is under any illusions about staying relevant: The original editions had code examples for a machine having 6-bit bytes and used self-modifying code to store the return address of subroutines rather than a stack.

In later editions he updated the examples, but even with respect to algorithms the new fascicles make references to quite recent papers and results. The books as timeless as they are, are products of their time more so than most books on mathematical topics.

jere• 14 years ago

The word tweet has existed for over a hundred years. Assuming that birds still exist in 50 years, its meaning should be pretty easy to infer in that context.

I'm betting "social" and "network" will still be recognizable words in 50 years too.

eru5• 14 years ago

> More than weird, will a 'tweet' have relevance 50 years from now?

It might just give the whole work a nice and quaint touch.

bulibuta• 14 years ago

Just made my morning, thanks!

walrus• 14 years ago

Just curious: how did you find this? I don't see a link to it anywhere on Knuth's website. The only reference I can find to it is on Twitter[1].

[1] https://twitter.com/pervognsen/status/230892091188846592

rosh• 14 years ago

It was on Reddit a few days ago... http://www.reddit.com/r/compsci/comments/xb6ft/

jinmingjian• 14 years ago

a (very incomplete) draft of section 7.2.2.2...still great

sp3324• 14 years ago

Any suggestions for software to read this on a desktop?

trotsky• 14 years ago

http://projects.gnome.org/evince/

eru5• 14 years ago

Gnome's standard document reader Evince works out of the box. As does Okular, KDE's standard reader. (Evince is also available for Windows, I don't know about Okular.)

makmanalp• 14 years ago

Also for osx, preview works fine for the .ps.

emmelaich• 14 years ago

Google Docs^WDrive works .. eventually. Seems to take a while to process.

I'd make it public, but that would be a copyright violation.

I wonder if Google hashes and caches the result. If they do the next upload should be much faster for anyone.

Don Knuth releases Volume 4, Pre-fascicle 6A [gzipped ps]

Related Stories