Donald Knut: When will the fourth volume finally come out?
"It is now very clear that at the speed with which I am writing, I will not finish the whole project until my ninetieth anniversary."
Read and evaluate the scope of work. And do not rush Grandpa Knut, he tries so hard.
Publishing support is Edison , a company that develops corporate portals and video-transfer applications .
')
The third volume is about sorting and searching. This area has changed a lot since I wrote the final version of the book. So I think about sorting and searching as if I were in Princeton now. You know, I finished work on the second part of the book and I was ready to come to Stanford, but I constantly had new ideas about sorting, since this area was subject to change.
So after my arrival at Stanford, I had to teach and start doing completely new things that I had never done before. It took some time and I could not finish work on the third part of the book before my trip to Norway in 1972, when I had a sabbatical. Actually, it was not a real academic leave, I just call it that. And in fact it was a vacation at their own expense. I had been working at Stanford for three years and thought it would be a great idea.
Professors usually work for 6 years, then they leave for a year on academic leave, then again 6 years of work and again 1 year of academic leave. I thought that maybe I would choose a 4-year cycle. I will work for 3 years, take a vacation at my own expense, then again 3 years and then academic leave. Stanford rules did not hinder such a plan. And I received an invitation from the University of Norway to spend one year there as a visiting professor, and since I didn’t need material assistance from Stanford, I could go there, taking leave at my own expense without all these payment problems.
And I loved Norway - we visited it in 1967, believe it or not. It was another one of those things that happened in 1967! And I fell in love with this country and the Norwegian national anthem - Ja, vi elsker dette landet. We love this country.
And I went to Norway and it was there that I finished the work on the third part and began to write the fourth. During that year, I lectured at the university every Wednesday, in my free time I was at home, wrote a book and read, and spent the rest of the time with my children.
And when, finally, the third part came out, it added a new aspect to this whole idea of ​​analyzing algorithms, because when you start talking about the topics that are described in the third part, it turns out that even though describes specific situations, sorting, searching - the lessons that you learn to apply to many other situations, there are a lot of additional topics in it.
And that is why the third part was especially important to me. Paradigms and methods that we used to study algorithms of all kinds, it seemed they all arose in the context of sorting. And I could create a single story about all this, but I teach general principles and at the same time I can illustrate them with the example of a special subject: sorting and searching.
Then I come home and I think, ok, I'm ready. I will write the fourth volume. It is about combinatorial algorithms. Combinatorial ... this means that the algorithm operates with innumerable combinations of ways to perform actions and, as a result, there were many, many problems that people wanted computers to solve for them.
So many cases had to be solved. You needed a computer to do this, but now no one could figure out how to do it effectively. A good idea could create a method that works millions of times faster and I collected all these good ideas, but people had new and new great ideas. And then ..., there is such a concept combinatorial explosion, which means for most people that the size of the problem increases to a giant scale and very quickly.
For me, a combinatorial explosion meant that the study of combinatorial methods was greatly intensified. In 1974, 1975 and 1976, when I was working on the fourth book, more than 50% of all articles in all technical journals were about the topics described in it. In other words, it's like sitting on a boiling pot, you cannot control it. Every time I wrote something in one week, in the next it became obsolete.
You know, it’s like trying to write a book about the internet today or something. And so it seemed impossible to finish the fourth book. I try my best, collect material for her, read newspapers, take a lot of notes. Upstairs I have hundreds of folders with these notes.
When I started I had 30 folders and they were well organized, then I created folders called X1, X2, X3 and so on until X15 - not very well organized, but just extensions of the system. And then a new material appeared and I began to dump it in a pile, in the hope that one day I would have time to read it. And so I hoped ... But this area is growing very fast.
I finished the 3:16 book, I finished the Specific Math. And I still can’t go back to “The Art of Programming,” because I still have one unfinished business and this is Stanford GraphBase. This is a collection of literacy programs that are used for standard examples, which will be in the fourth part of the book The Art of Programming.
And it took me a few more years to make this work. It was necessary to release this base before the book itself came out, so that I could finish other projects with other people in different parts of the world who contributed to writing the book so that they could use the Stanford GraphBase for their work.
Around 1995, I was able to open the door of the very room where I had been throwing all the new materials for a book for 15 years. While I was working on TeX, I had no time to think about it and when I received something by mail related to the fourth, fifth or other volumes of the book, I just sent it to the heap, then I had boxes and more boxes and eventually accumulated about 17 feet of material in length.
And besides that, I had all the materials that I collected in previous years. So I decided that I needed to reorganize them all and it took another year, even more than a year, to view everything, every piece of paper that got there, and then send everything to the right place, create a computer index, so that I I could find everything, decompose everything in thousands of small file folders and also correct all errors in the first, second and third volumes.
People wrote to me, reporting errors in the first, second and third volumes. I have had letters since 1981, 1982, to which I have not yet responded. And I wrote all these people checks with interest from that day. You know, I had a small program that calculated these percentages and there was an error in it, so I think I paid a bit more interest. But in any case, I sent hundreds of checks and received a large list of misprints for “The Art of Computer Programming” for the first, second and third volumes that I could type using TeX and do it correctly.
All these years, people continued to buy books on a regular basis in bookstores, they bought editions, which was released in the 70s, but already in the 30th, in the 40th edition. And each of the books is still sold at about 4,000 books a year. The second part was published in 1981, the one in which I could not tolerate numbers, but the mathematical material was in order.
When my series of books “Computers and Layout” was published, those 5 parts, everything was done with new fonts, with the appropriate design. In the book "Concrete Mathematics" I was able to use a new font created by Herman Zapf, and for the book "3:16" I had a different font I was working on.
Therefore, at that time, only the book “The Art of Computer Programming” remained, in which there was an ugly design and anyway, I did not want to correct it. It took me so long to get back to writing the fourth part, how could I stop and redo the first three without waiting a little more?
To the rescue came Silvio Levy, who lives in Berkeley, who was very active in many mathematical projects and now works as a librarian at the Institute for the Study of Mathematical Sciences. He was a big fan of TeX and together we created CWEB, a literate programming system using C as a programming language instead of Pascal.
Silvio decided that he would collect the first three parts of the book at TeX for the public good and he asked the publisher for a symbolic payment, which of course they easily agreed. He, together with his wife Sheila, made the correction of errors and they did an amazing job, checking all three parts and connecting all the errors in my list of errors.
Then it didn't take me much time ... I mean it took 3 or 4 months, but this is nothing compared to how much time it would take for me to do this work if I did everything alone. As a result, in 1997/1998 we had an updated “Art of Programming” with a suitable layout and all 20 years of corrections that were previously in my files, but now turned out to be included in the text.
And then I was ready to start working on the fourth part. But she still hasn't come out, is she? So what happened. Well, in fact, about 400 pages of the book have already been produced in paperback, but for writing one page I need more than one day. And I simply cannot convince myself to agree simply to the reproduction of materials that I find in my files. Every time I look at something from the materials, I see that there is an opportunity to improve them, and this takes me a few more days.
So I add a lot of material in the course of writing the fourth volume, which is not in the literature. I cannot support what I already know, but those volumes of the book that I am writing now, I repeat to myself that they are so essential that they differ from the volumes that follow them and that next year I will simply combine those volumes which are not very original. But actually ... as for example, today I’ll finish the work on the catalog for the new section and this is about 60 pages, of which I think only 15 pages contain information that is not found in other literature.
But there are also several different ideas ... I can't help but keep up with the sources that I have when I write such an essential part of the book. So now it is extremely clear that with the speed with which I am writing, I will not finish the whole project until my 90th birthday.
But even though I am not adding anything, I do not go beyond the table of contents that I sketched on that day in January 1962, when I was asked to write a book about compilers. I still have about the same table of contents ..., but this area has increased so much and now there is such a vast amount of good material that I just cannot but include in the book.
My life now mainly consists of viewing materials for the fourth volume. All the materials that I continue to read in the library, create new ideas, and I combine them and contact people from all over the world with requests for help in debugging ideas and checking that I did everything right.
Let us hope that I will be able to continue this work for a long time. This is interesting because I have to combine the works of authors who did not even know about the works of each other and they have a chance to create a real connection between their works and I like to find ways to present the material.
I understand that now I’m already an old man and I’m no longer writing as lively as in my youth, but I still have 3000 pages of a manuscript written in the 60s, from which I can take sentences and phrases to rejuvenate a book.
And I also realize that this material is not easy reading, people can keep this book in the toilet or in a similar place, and maybe it will be on the shelf, just letting anyone know that they can understand it.
Some of these materials have no easy path, something inherently difficult, but I’m almost in awe of how things go. For example, this morning I compiled a table of contents and I saw those parts whose writing was not easy for me. But now, when they are finished, they look like a great story, and the fact that I was tormented by writing them no longer seems so obvious to me.
Read and evaluate the scope of work. And do not rush Grandpa Knut, he tries so hard.
Publishing support is Edison , a company that develops corporate portals and video-transfer applications .
')
Volume Three of "The Art of Computer Programming" (48/97)
The third volume is about sorting and searching. This area has changed a lot since I wrote the final version of the book. So I think about sorting and searching as if I were in Princeton now. You know, I finished work on the second part of the book and I was ready to come to Stanford, but I constantly had new ideas about sorting, since this area was subject to change.
So after my arrival at Stanford, I had to teach and start doing completely new things that I had never done before. It took some time and I could not finish work on the third part of the book before my trip to Norway in 1972, when I had a sabbatical. Actually, it was not a real academic leave, I just call it that. And in fact it was a vacation at their own expense. I had been working at Stanford for three years and thought it would be a great idea.
Professors usually work for 6 years, then they leave for a year on academic leave, then again 6 years of work and again 1 year of academic leave. I thought that maybe I would choose a 4-year cycle. I will work for 3 years, take a vacation at my own expense, then again 3 years and then academic leave. Stanford rules did not hinder such a plan. And I received an invitation from the University of Norway to spend one year there as a visiting professor, and since I didn’t need material assistance from Stanford, I could go there, taking leave at my own expense without all these payment problems.
And I loved Norway - we visited it in 1967, believe it or not. It was another one of those things that happened in 1967! And I fell in love with this country and the Norwegian national anthem - Ja, vi elsker dette landet. We love this country.
And I went to Norway and it was there that I finished the work on the third part and began to write the fourth. During that year, I lectured at the university every Wednesday, in my free time I was at home, wrote a book and read, and spent the rest of the time with my children.
And when, finally, the third part came out, it added a new aspect to this whole idea of ​​analyzing algorithms, because when you start talking about the topics that are described in the third part, it turns out that even though describes specific situations, sorting, searching - the lessons that you learn to apply to many other situations, there are a lot of additional topics in it.
And that is why the third part was especially important to me. Paradigms and methods that we used to study algorithms of all kinds, it seemed they all arose in the context of sorting. And I could create a single story about all this, but I teach general principles and at the same time I can illustrate them with the example of a special subject: sorting and searching.
Working on Volume Four of "The Art of Computer Programming" (49/97)
Then I come home and I think, ok, I'm ready. I will write the fourth volume. It is about combinatorial algorithms. Combinatorial ... this means that the algorithm operates with innumerable combinations of ways to perform actions and, as a result, there were many, many problems that people wanted computers to solve for them.
So many cases had to be solved. You needed a computer to do this, but now no one could figure out how to do it effectively. A good idea could create a method that works millions of times faster and I collected all these good ideas, but people had new and new great ideas. And then ..., there is such a concept combinatorial explosion, which means for most people that the size of the problem increases to a giant scale and very quickly.
For me, a combinatorial explosion meant that the study of combinatorial methods was greatly intensified. In 1974, 1975 and 1976, when I was working on the fourth book, more than 50% of all articles in all technical journals were about the topics described in it. In other words, it's like sitting on a boiling pot, you cannot control it. Every time I wrote something in one week, in the next it became obsolete.
You know, it’s like trying to write a book about the internet today or something. And so it seemed impossible to finish the fourth book. I try my best, collect material for her, read newspapers, take a lot of notes. Upstairs I have hundreds of folders with these notes.
When I started I had 30 folders and they were well organized, then I created folders called X1, X2, X3 and so on until X15 - not very well organized, but just extensions of the system. And then a new material appeared and I began to dump it in a pile, in the hope that one day I would have time to read it. And so I hoped ... But this area is growing very fast.
Updating Volumes One to Three of "The Art of Computer Programming" (81/97)
I finished the 3:16 book, I finished the Specific Math. And I still can’t go back to “The Art of Programming,” because I still have one unfinished business and this is Stanford GraphBase. This is a collection of literacy programs that are used for standard examples, which will be in the fourth part of the book The Art of Programming.
And it took me a few more years to make this work. It was necessary to release this base before the book itself came out, so that I could finish other projects with other people in different parts of the world who contributed to writing the book so that they could use the Stanford GraphBase for their work.
Around 1995, I was able to open the door of the very room where I had been throwing all the new materials for a book for 15 years. While I was working on TeX, I had no time to think about it and when I received something by mail related to the fourth, fifth or other volumes of the book, I just sent it to the heap, then I had boxes and more boxes and eventually accumulated about 17 feet of material in length.
And besides that, I had all the materials that I collected in previous years. So I decided that I needed to reorganize them all and it took another year, even more than a year, to view everything, every piece of paper that got there, and then send everything to the right place, create a computer index, so that I I could find everything, decompose everything in thousands of small file folders and also correct all errors in the first, second and third volumes.
People wrote to me, reporting errors in the first, second and third volumes. I have had letters since 1981, 1982, to which I have not yet responded. And I wrote all these people checks with interest from that day. You know, I had a small program that calculated these percentages and there was an error in it, so I think I paid a bit more interest. But in any case, I sent hundreds of checks and received a large list of misprints for “The Art of Computer Programming” for the first, second and third volumes that I could type using TeX and do it correctly.
All these years, people continued to buy books on a regular basis in bookstores, they bought editions, which was released in the 70s, but already in the 30th, in the 40th edition. And each of the books is still sold at about 4,000 books a year. The second part was published in 1981, the one in which I could not tolerate numbers, but the mathematical material was in order.
When my series of books “Computers and Layout” was published, those 5 parts, everything was done with new fonts, with the appropriate design. In the book "Concrete Mathematics" I was able to use a new font created by Herman Zapf, and for the book "3:16" I had a different font I was working on.
Therefore, at that time, only the book “The Art of Computer Programming” remained, in which there was an ugly design and anyway, I did not want to correct it. It took me so long to get back to writing the fourth part, how could I stop and redo the first three without waiting a little more?
To the rescue came Silvio Levy, who lives in Berkeley, who was very active in many mathematical projects and now works as a librarian at the Institute for the Study of Mathematical Sciences. He was a big fan of TeX and together we created CWEB, a literate programming system using C as a programming language instead of Pascal.
Silvio decided that he would collect the first three parts of the book at TeX for the public good and he asked the publisher for a symbolic payment, which of course they easily agreed. He, together with his wife Sheila, made the correction of errors and they did an amazing job, checking all three parts and connecting all the errors in my list of errors.
Then it didn't take me much time ... I mean it took 3 or 4 months, but this is nothing compared to how much time it would take for me to do this work if I did everything alone. As a result, in 1997/1998 we had an updated “Art of Programming” with a suitable layout and all 20 years of corrections that were previously in my files, but now turned out to be included in the text.
The Art of Computer Programming (82/97)
And then I was ready to start working on the fourth part. But she still hasn't come out, is she? So what happened. Well, in fact, about 400 pages of the book have already been produced in paperback, but for writing one page I need more than one day. And I simply cannot convince myself to agree simply to the reproduction of materials that I find in my files. Every time I look at something from the materials, I see that there is an opportunity to improve them, and this takes me a few more days.
So I add a lot of material in the course of writing the fourth volume, which is not in the literature. I cannot support what I already know, but those volumes of the book that I am writing now, I repeat to myself that they are so essential that they differ from the volumes that follow them and that next year I will simply combine those volumes which are not very original. But actually ... as for example, today I’ll finish the work on the catalog for the new section and this is about 60 pages, of which I think only 15 pages contain information that is not found in other literature.
But there are also several different ideas ... I can't help but keep up with the sources that I have when I write such an essential part of the book. So now it is extremely clear that with the speed with which I am writing, I will not finish the whole project until my 90th birthday.
But even though I am not adding anything, I do not go beyond the table of contents that I sketched on that day in January 1962, when I was asked to write a book about compilers. I still have about the same table of contents ..., but this area has increased so much and now there is such a vast amount of good material that I just cannot but include in the book.
My life now mainly consists of viewing materials for the fourth volume. All the materials that I continue to read in the library, create new ideas, and I combine them and contact people from all over the world with requests for help in debugging ideas and checking that I did everything right.
Let us hope that I will be able to continue this work for a long time. This is interesting because I have to combine the works of authors who did not even know about the works of each other and they have a chance to create a real connection between their works and I like to find ways to present the material.
I understand that now I’m already an old man and I’m no longer writing as lively as in my youth, but I still have 3000 pages of a manuscript written in the 60s, from which I can take sentences and phrases to rejuvenate a book.
And I also realize that this material is not easy reading, people can keep this book in the toilet or in a similar place, and maybe it will be on the shelf, just letting anyone know that they can understand it.
Some of these materials have no easy path, something inherently difficult, but I’m almost in awe of how things go. For example, this morning I compiled a table of contents and I saw those parts whose writing was not easy for me. But now, when they are finished, they look like a great story, and the fact that I was tormented by writing them no longer seems so obvious to me.
Read more
- Donald Knut: I sat in the back row and hunted jokes, and the teachers resigned and didn't often beat on the ass (1,2,3,7 / 97)
- Donald Knut: “My advice to the young” (93/97) and “Feeling the need to assert oneself” (9/97)
- Surreal Numbers: I worked for six days, and rested on the seventh (40,41,42 / 97)
- Donald Knut: How the “Art of Programming” was created (33,38,39 / 97)
- Donald Knut: When will the fourth volume finally come out?
- Donald Knut: How I spent the summer with the computer, not with the girls (19,20,21,22 / 97)
List of 97 videos with stories of Donald Knut
Youtube playlist
1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My computer experience
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Want to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with ...
32. Finding a solution to the problem of projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the ...
39. The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. ​​Moving to Stanford and wondering whether to make the right choice
47. Designing the house in Stanford
48. Volume Three Of The Art Of Computer Programming
49. Working on the Volume.
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typesetting
57. Working on TeX
58. Why should the designer
59. Converting Volume Two to TeX
60. Writing a users manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose and transcribed it to ...
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX.
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. At MIT
76. Back to work at Stanford
77. Taking up swimming help to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes of Computer Programming
82. The Art of Computer ...
83. Two final major research projects
84. lucky life
85. Coping with cancer
86. Honorary doctorates
87. The Importance of the Kyoto Prize
88. Pipe organisms of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books
97. Why I chose analysis
1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My computer experience
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Want to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with ...
32. Finding a solution to the problem of projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the ...
39. The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. ​​Moving to Stanford and wondering whether to make the right choice
47. Designing the house in Stanford
48. Volume Three Of The Art Of Computer Programming
49. Working on the Volume.
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typesetting
57. Working on TeX
58. Why should the designer
59. Converting Volume Two to TeX
60. Writing a users manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose and transcribed it to ...
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX.
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. At MIT
76. Back to work at Stanford
77. Taking up swimming help to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes of Computer Programming
82. The Art of Computer ...
83. Two final major research projects
84. lucky life
85. Coping with cancer
86. Honorary doctorates
87. The Importance of the Kyoto Prize
88. Pipe organisms of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books
97. Why I chose analysis
Source: https://habr.com/ru/post/313790/
All Articles