The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming. – Byte , September 1995 I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up. –Charles Long If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing. –Bill Gates It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers. –Jonathan Laventhol This first volume in the series begins with basic programming concepts and techniques, then focuses more particularly on information structures–the representation of information inside a computer, the structural relationships between data elements and how to deal with them efficiently. Elementary applications are given to simulation, numerical methods, symbolic computing, software and system design. Dozens of simple and important algorithms and techniques have been added to those of the previous edition. The section on mathematical preliminaries has been extensively revised to match present trends in research. Ebook (PDF version) produced by Mathematical Sciences Publishers (MSP),
Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.
Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.
In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.
A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.
At first, I enjoyed this dense and scholarly volume. Knuth's dry humor is peppered throughout the book, but pops up most frequently in the first few chapters. It seemed at odds with the negative (and adoring) opinions I'd read about the book.
I was told (by Knuth in his introduction) that I could skip as much of the math as I liked. So I dutifully skimmed through the math chapter and continued.
Then I hit MIX. It's the theoretical computer to which all of the program examples in the book will be written - in assembly language. It's interesting and clever and...awful.
Please understand that I have read Knuth's defenses for using assembly language to teach his algorithms. I understand them. And they make sense.
But now that I've slogged through this first volume, I can say with certainty that I hate MIX and I hate learning algorithms from MIX examples. "We hates it, we hates it, we hates it forever!" as Gollum would say.
Is it important to understand how a linked list works in memory? Absolutely. Does worrying about the housekeeping of a fictional computer designed in the 1960s aid in that understanding? Absolutely not.
Knuth admits that MIX is outdated and he's working on MMIX, which will be a much nicer RISC design. Certainly that would be an improvement. But I still feel a higher-level language (or a formaly-defined pseudocode) could show all of the lower-level concepts without the drudgery of assembly.
Let's move on from the assembly example issues and talk about the content of Volume One. For all of the words and symbols, very little ground is actually covered! By the end of Volume One, you'll only have learned about lists (stacks, queues, deques, etc.) and basic trees. Which is not to say those aren't fruitful structures ripe for thorough examination - certainly they are, and Knuth examines them thoroughly. It's just to say that the pace is utterly glacial.
In other words, and it pains me very much to say this, it's difficult to justify the time required to get through a book like this if you don't enjoy the MIX assembly puzzles or the higher math problems.
I appreciate this incredibly thorough and accurate work the way I appreciate models of large gothic structures created with toothpicks. But while the toothpick model can be enjoyed at a glance as a piece of visual art, The Art of Computer Programming can only be appreciated with careful study.
It's really quite difficult to put a star review on a single volume of a (some day) five-volume set of astoundingly thorough scholarship. In some ways, I don't even feel worthy of reviewing the thing. In the end, all I can do is rate the enjoyment and/or personal value of the knowledge I gained from the book.
I'll be perfectly honest, the only "useful" (using an extremely loose interpretation of that word) thing I actually remember from Volume One is how to use a pair of stacks to efficiently simulate a FIFO queue. That's a pitiful statement considering the amount of time I put into reading the thing.
I own the three-volume set (published before Volume 4A came out). My understanding is that the books get more interesting later on. The titles do sound interesting. But I can't get past the fact that they're going to be chock full of more MIX examples and exercises in higher math. It's going to be a while before I work up the stamina to crack the next one open.
oh, who am i kidding? i have never read this straight through, but i think i've covered a lot of it over the course of 8 years as an engineer. if i was stranded on a desert island with enough food and water to last the rest of my life, this series of books is what i would take with me. there are so many puzzles in these books that it could keep you occupied for a lifetime. i don't know how one man wrote these books.
This book is so deep that literally no one can read it and understand and keep that knowledge. Most people out here concede to not have read the whole thing. It's just too much.
It has become more of a status symbol amongst the intellectuals to show off that they "have read TOACP". But really this book is just an antique encyclopedia with extreme details. Yeah Bill Gates praised it, but Mr. Gates doesn't code any more.
For anyone graduating in the post pandemic world. This book is probably NOT for you, unless you are post doc researching algorithms or your job requires theoretical proofs of algorithms or low level coding. You can't do any good to your skillset by reading this book.
It's better to learn algorithms and data structures from other milder books which use pseudo code and extrapolate use cases into the real world.
If you are an engineer and want to be better at algorithms, just practice it on codeforces/leetcode because you would learn more that way than reading mathematical theory and MIX code.
This is not a book to be read, it's a book to be kept. Just in case you feel too chilled out at your software job. It will remind you to be humble.
This book outlines the design of computers and shows how many of the challenges of programming development have been addressed. It is a great and foundational computer science book. Today, understanding the operation of the processor is less critical and the way data structures are used has somewhat evolved. The math and assembly programs gave critical insight into practice and optimization at one time, however are less relevant now. Programmers who read it will still love this book. It was a nice validation to find the logic I had used once in a short program in one of the examples. It is striking how far the practice has come.
An excellent learning resource for anyone with an interest in computers or mathematics. Not exactly a light read, but it provides a great set of tools that can be applied to many situations. The problem sets were concise, interesting and a far better substitute to doing sudokus on the morning commute.
I tried to work through all the problems rated 25 or less, while glancing at the more complex/time consuming ones, but I sometimes lacked the skills to complete a problem. I would like to revisit this book after reading a few of the suggested books in the bibliography.
Donald E. Knuth's The Art of Computer Programming provides a detailed textbook for classical Computer Science, starting with the foundational mathematics and working through (in this volume) data structures such as Linked Lists, Trees, and Graphs.
While authoritative and enjoyable to read, I personally felt unprepared (even with advance warning) for the sheer volume of mathematics in Chapter 1, and spent the first 120 pages reeling from notations that I hadn't read before. After the "Introductory Mathematics", the book returned to more familiar ground detailing out algorithms, and (less important to the modern reader) how they might be implemented in a prototypal assembly language.
I skipped over several types of content this book provided, firstly, the assembly implementations (because the lowest language I work in happens to be C, still a level up from Assembly), secondly, the exercises (which would have taken me until early next year, judging by the sheer amount), and thirdly, the parts of Knuth's proofs that made my eyes bleed.
Overall, Knuth's writing voice is authoritative, friendly, and at times humorous. It's rare to find a Computer Science professor as enjoyable to read. Unfortunately, most notable algorithms covered in the book are also covered in other Computer Science manuals that you've probably read if you're readying yourself to joust this particular windmill. I'd recommend Volume 1. It certainly didn't scare me away from Volume 2.
This book was somewhat of a mixed blessing. I really enjoyed the mathematical exactness and thoroughness. However, I did not at all like the decision to have the sample code in a made-up assembly language. That made the programs utterly unreadable. Maybe I'm just not HC geek enough, but IMO when the point is to present algorithms, the sample code should be clear and easy to read. Using a higher level language would have been more appropriate.
Also, it would have been nice to have had flow graphs of all the presented algorithms instead of just a few of them.
I also have to admit that this book was such heavy reading that at the end I began to read more marginally and skip some paragraphs, getting just an overview of certain subjects.
- Toàn bộ chương 1 nói về kiến thức toán cho phân tích thuật toán. Nội dung không quá khó (trừ phần bài tập), nhưng tốc độ rất nhanh và không đi sâu (những phần được đào sâu thì nằm trong phần bài tập). Cho nên muốn đọc TAOCP hiệu quả thì tốt nhất là bạn nên đọc Concrete Mathematics (CMath) của Knuth trước, sau đó lướt sơ qua phần 1 của cuốn này; đừng quá bận tâm đến bài tập trong chương này nếu bạn đã làm kha khá bài tập bên CMath. - Ngôn ngữ MIX: do không dùng ngôn ngữ bậc cao hơn đồng thời được thiết kế theo hệ thống máy tính thời 1960s, MIX rất bất tiện và đôi khi khá rối. Nếu đã biết hợp ngữ thì phần này sẽ tương đối dễ chịu. Nhưng mình khuyến khích đọc để biết thời xa xưa dân tình viết code thế nào, phần bài tập có thể tự viết lại bằng ngôn ngữ khác. Chuyện này ảnh hưởng khá nhiều đến Chương 2 của sách, khi mà Knuth tận dụng 1 số tính năng hơi quái dị của MIX để tiết kiệm bộ nhớ cho CTDL. - Phong cách chứng minh của Knuth: rất "cô đọng", thậm chí có phần hơn "informal" khi Knuth thấy nó dễ hoặc là Knuth sẽ chứng minh dạng tổng quát (đôi khi không trực quan). Theo mình thì với cùng 1 Theorem, người đọc nên tham khảo thêm CLRS để hiểu rõ từng bước chứng minh, sau đó quay lại đọc phần Knuth viết sẽ thấy dễ hiểu hơn nhiều.
## Đánh giá một số chương
1. 1.2 Mathematical Preliminaries: đây là rào cản lớn nhất cho những ai muốn tiếp cận TAOCP mặc dù những kiến thức phần này được sử dụng ở từng chương trong sách. Nếu để ý bạn sẽ thấy Knuth luôn cập nhật thêm bài tập trong phần này để lượng kiến thức nền đủ để bạn hiểu được những chứng minh, dù là mới nhất liên quan đến thuật toán. Cách tốt nhất để đọc phần này (và không muốn đọc toàn bộ CMath) là làm toàn bộ bài tập nào dưới < 25 hoặc M20 hoặc HM < 15. Dĩ nhiên, mình đề xuất là đọc CMath thay vì tốn quá nhiều thời gian vào đây. 2. MIX: Đừng quá quan tâm, bởi tương lai Knuth sẽ thay bằng MMIX và trong Volume 4 đã hoàn toàn thay bằng MMIX. Ngôn ngữ này không quá khó để đọc, tuy nhiên chi phí cho một số câu lệnh có tương đối khác so với câu lệnh tương tự với phần cứng hiện nay. 3. 2.2 Linear Lists: Đây là phần hay nhất, nhưng cũng là phần gây nhiều trở ngại: Knuth rất thích dùng pointer, nhưng pointer trong MIX khá là free style, nó thậm chí không có type dẫn đến chuyện Knuth muốn làm gì thì làm với pointer. Điều đó dẫn đến chuyện bạn hầu như không thể viết lại kiểu 1-1 với thiết kế của các CTDL được đề cập trong sách. Phần này có khá nhiều ví dụ hấp dẫn, điển hình gồm chương trình giả lập thang máy, các toán tử trên đa thức, topological sort. 4. 2.3 Trees: Phần hay nhất trong sách. Lưu ý: một số chứng minh Knuth sử dụng cho cả trường hợp cây/đồ thị vô hạn, nên để dễ tiếp thu hơn, mình khuyến khích đọc phần chứng minh bên CLRS hơn.
Vậy bạn có nên đọc TAOCP Vol 1 không? Theo mình, nếu bạn là sinh viên năm 1-2 thì tốt nhất nên tạm gác cuốn này lại. Có nhiều cuốn dẫn nhập với các tiếp cận nhẹ nhàng hơn: đơn cử nhưng loạt sách về thuật toán của Robert Sedgewick (Sedgewick cũng là học trò của Knuth, và luận văn của ông là về phân tích độ phức tạp của Quick Sort - nếu đọc Volumne 3 phần Sắp xếp bạn sẽ để ý thấy có khác nhiều chỉ dẫn có tên của Sedgewick, hẳn là Knuth đã giao đống bài tập về cho Sedgewick làm). Dưới đây là một số cuốn mà mình nghĩ sẽ phù hợp với năm 1-2 hơn: - Introduction to Computer Science. - Algorithms. - Algorithms Design Manual. - Algorithms by Jeff
Mình đánh giá cao CLRS nhưng mình nghĩ CLRS nên dành đọc sau khi bạn đã đọc xong Algorithms của Sedgewick.
Although well written and thorough with some delicious humor, this did not meet up to my expectations. I did learn a few things about this and that (not the least tree traversals) but much space was wasted on superfluous detail. For instance I did not care squat for the MIX assembly language code examples that took up page after page. Personally I'm very interested in math, but there was also a disconnect between the chapters on background theory and the later ones on algorithms.
Knuth wrote this book for people who already know almost everything it tries to teach you. Sections move from easy to understand to immensely complex in a sentence or two. Finishing it is more of a badge of honor than an actual learning experience. Combine the fast pace with the outdated MIX computer, and the relevancy of this book to modern programmers is minimal. I still did learn some cool things, but it could have been a lot better.
Amazing monograph on computer science, very didactically written. With well-thought structure and great excercises, it is perfectly suitable as a textbook for two full courses, as well as a textbook for independent study. The excercises themselves, especially from the first chapter, provide great entertainment for the so inclined reader, in many areas of mathematics.
More elegant science writing - one of the deep, foundational thinkers in Computer Science. Packed with insight, rigour, and interesting mathematical puzzles (I love mathematics, but usually I find mathematical puzzles very uninteresting.) And a ditto goes to Volumes 2 and 3.
Reading this book once is not enough. It's an amazing piece that everyone should read, or at least skim through. There are so great tips and insights I've never seen elsewhere, and reading the whole thing just opens up your mind to a lot of things.
This is a fantastic piece of literature for computer science. It is however, not an introductory book, so the reader must know quite a lot of mathematics and abstract computer programming to get the most out of this book. Even though it is quite old, it is still relevant in many ways.
I have been meaning to read these 4? books for quite some time. They are widely known, and highly praised classics. But based on Volume One it is hard to see why. Despite some clearly minor brushing up ( in 1997 third edition ) it is still all fairly archaic. The Book declines to state information about timing of earlier editions, not surprisingly. I believe it was the late 1960s, early 1970s. It is at least an interesting read from an historical perspective. Some of the figures given for available memory and execution time are simply astonishing by today's standards. And it is useful to be reminded that a lot of today's standard ideas and practices had to be discovered/invented by someone at some time. There are some good historical notes. Everyone should study basic CPU/memory architecture and do some Machine Language/Assembler coding at some time or another. For educational value. But even the Virtual Machine / Language given in this text as the basis for the rest of the volumes is archaic - for example making use of several old constructs only necessitated by the hardware limitations of the time and long since gone. Such as self modifying instructions! There is the promise of an updated more modern MMIX. Still nowhere to be seen. But this is of little importance. What is of importance is the sheer absurdity of studying algorithms and their performance by writing them in machine code in the first place. This is so wrong on so many levels. I guess it made some kind of sense way back in 1970 or so. Very ancient times in the history of computing. But it is part of the authors fundamental style to get bogged down in minutia. If you do too I think you will waste an enormous amount of time on it. There are much better more recent books on algorithms and performance which can get you to the essential points much more quickly - and still cover all of the essential details. But sure, scan through this book for a look at the history and a better appreciation of where it all came from. But I wouldn't put a huge amount of time into it. I think it is highly overrated. I have an open mind though and some time available so let's see if volume 2 is any better.
Make no mistake: this book is important to have for any serious computer scientist. That said, it does have some notable shortcomings. In some areas it spends too much time on things that aren't that important, and in other areas it glosses over details for things that are important. A lot of the key information in the book shows up only in the exercises (and the answers, for which the book deserves a lot of credit for giving); that's good, but the problem is it makes the reader work too hard to dig out the information. The job of an author is to make the reading easy. Unfortunately Professor Knuth falls a bit short in this respect.
The author expresses their admiration for the book series "The Art of Computer Programming" by Donald Knuth and the message it sends about the owner's expertise in computer programming. They mention how Bill Gates highly recommends the book and how owning the books made them feel like a "Real Programmer" and "Serious Practitioner of Computer Science." However, the author feels that they are not capable of understanding the depth of the content and have not read the books. The author reflects on the early days of computer programming, specifically with the IBM 650 mainframe, and how it required a combination of math and mechanical engineering that could be understood by one person but is not the case anymore. They also mention that they have not read the books and this is not a book review.
skimmed most of this over the break. Reading the whole thing will of course take at least a month, even though the concepts in the first volume are rather basic. The chapter on trees was really good, although I didn't have time to read the whole thing.