|
|
This award-winning book demonstrates the art of literate programming with more than 30 examples. Each example is a programmatic essay: a short story that can be read and enjoyed by human beings as readily as it can be read and interpreted by machines. The programs contain state-of-the-art explanations of many important algorithms and data structures. They also define a workbench for combinatorial computing, and standard sets of data that can be used for benchmark tests of competing methods, as well as demonstration programs and games that make use of the data.
Hundreds of example programs that use The Stanford GraphBase will be distributed electronically as supplements to Volume 4 of The Art of Computer Programming when that volume is available, because Knuth will be using The Stanford GraphBase for many of the examples in that book.
Major topics include
Available from the publishers, ACM Press or Addison-Wesley Publishing Company.
Public-domain sources for all programs and data of The Stanford GraphBase are freely available. They can be obtained, for example, by anonymous ftp from the master sources on ftp.cs.stanford.edu in directory ~ftp/pub/sgb. The programs are highly portable and have been installed on a wide variety of computers and operating systems.
Download sgb-words.txt, the 5757 five-letter words of English
Sample graphs from TAOCP: chvatal-12.gb contiguous-usa.gb orient-express.gb
This book was cited by the Association of American Publishers as the best new book in Computer Science, 1994.
There's a nice online writeup in the Stony Brook Algorithm Repository.
The book contains several yet-unsolved problems on which I'm hoping readers will make significant progress. One of the most fun problems is based on the 1990 football season: What is the biggest score Stanford can rack up over Harvard by a simple chain of results from that year? My best solution was 2279, but Buel Chandler has improved that to 2448 by applying genetic programming ideas to some of my algorithms. See Chandler's cool page about genetic football for further information.
News flash, 25 November 2001: Mark Cooke has just reported the discovery of a sequence by which Stanford racks up 2473 points over Harvard, together with a matching upper bound (found in February 2002)! Also, Harvard over Stanford by 2358; Penn State over Columbia by 2542 (and that's the max over all pairs of teams). Details to follow...
An embarrassing off-by-one error was corrected in the programs that create random graphs (random_graph and random_bigraph). When making this change, I decided it was better to conform to the documentation than to remain totally compatible with past history. The graph that now is called random_graph(n,m,x,l,o,f,t,a,b,s), and which properly deserves that name, is the same as the graph that used to be called random_graph(n,m,x,l,o,f,t,a,b+1,s)---unless a=b, in which case the old program was correct and no change was necessary.
Please upgrade to the new versions of the SGB source programs, if your copy is dated earlier than July 1999. (I also made minor corrections in May 2007---worth making, but not crucial.)
A list of corrections to all changes made to the first two printings of this book can be found in the file ftp://ftp.cs.stanford.edu/pub/sgb/ERRATA. The third printing [summer 2002] corrected all those mistakes and, so far, it seems to need only the following additional corrections:
- page 7, line 8 from the bottom (25 Mar 07)
- change "hit" to "hits"
- page 188, line 15 (25 Mar 07)
- change "chap_name[k]=gb_save_string(str_buf);" to "{ if (str_buf[strlen(str_buf)-1]=='\n') str_buf[strlen(str_buf)-1]='\0'; chap_name[k]=gb_save_string(str_buf); }"
- page 287, line 8 (25 Mar 07)
- change "liberal use use" to "liberal use"
- page 338, line 2 (25 Mar 03)
- change `gb_graph' to `GB_SORT'
- page 569, line 18 (25 Mar 07)
- change "labrea" to "ftp.cs"
- page 571, Dijkstra entry (28 Mar 05)
- change `Wijbe' to `Wybe'
- page 573, Kruskal entry (28 Mar 05)
- change `Joseph Bernard' to `Joseph Bernard, Jr.'
Also the obsolete description of how to download the source files on page 53 needs to be brought up to date. (The online instructions above are correct.)
I will gratefully pay $2.56 to the first person who finds and reports anything else that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to sgb@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA.
PLEASE DO NOT SEND EMAIL TO SGB EXCEPT TO REPORT ERRORS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.
Don Knuth's home page
Don Knuth's other books