15 ms·
Can someone honestly tell me if they have actually read these books AND found them useful ON TGE JOB? What do you guys do for work? I tried reading part 1?? Lik
by Bayko 4y ago
Can someone honestly tell me if they have actually read these books AND found them useful ON TGE JOB? What do you guys do for work?
I tried reading part 1?? Like ten years ago and it was pretty much assembly language or something I believe. And gave up since it wasnt something that I needed in academia back then and there were far better ways to learn DSA
- lupire 4y agoDo you normally expect to read encyclopedias for your job?
- daoist_shaman 4y agoIt’s something nice to put on the shelf and fantasize about enjoying, one day, when there’s time.
- Tomis02 4y agoUseful on the job? Absolutely. They give me hope that when my life is over I'll have done something more significant than pushing bits between API calls. Disclaimer: I'm nowhere close to finishing any of the books.
- Labo333 4y agoI'm currently going through Fascicule 6A dedicated to SAT solving and I can tell you it is by far the best reference. I haven't found anywhere else a complete reference that builds a SAT solver from scratch while explaining why each technique is used. Regarding more classical algorithms, I never bothered reading the other fascicles. I think there are much more practical references but none is as complete and detailed as Knuth's treatment. He goes to the bottom of any algorithm, not just proving it has the right complexity but also asking what inputs are the most difficult, what other problems it can solve, etc. In the end you understand the field much better and have a good idea of what the boundary of knowledge (ie research) looks like. But, and I say that as an ICPC world finalist, if you just want to solve practical problems you probably won't need TAOCP.
- lupire 4y agoKnuth's chapters are mostly decades old. I don't think they are near the boundaries of research. (except the starting boundaries.)
- wollsmoth 4y agoI bought volume 1, figuring if I actually worked up the gumption to finish it I'd continue from there. It looks very nice on my bookshelf.
- elcapitan 4y agoI don't own any of them, but sometimes get them from the library for interview prep. Totally over the top for that, but sometimes inbetween googling and overcomplicated other books it's a nice relief to read through these lines, into which very obviously a lot of thought has gone. The opposite of all the fast-lived crap we have to deal with on a daily basis, and therefore also useful for the job. Motivating, I would say.
- lupire 4y agoFun is fun, but if you want help with Leetcode, something like CLR(S) is more helpful.
- elcapitan 4y agoCLRS is what I own, but I never found it too helpful for that in particular. For this kind of quick refresher/prep work I found the "Algorithm Design Manual" more practical, because it gets to the point quicker. Then sometimes expanding on some very specific details with the Knuth books, but yeah, that is also partially just for fun.
- hardwaregeek 4y agoIMO Volume 1 isn't that useful because it's mostly setting up the mathematical and architectural foundations. Knowing how to evaluate limits and recurrence relations isn't particularly valuable knowledge for the average programmer. I enjoyed the dancing links stuff from a recent fascicle. I used it to build a sudoku solver in C. So it's moderately useful.
- martincmartin 4y agoI once used them at work. I had a monitor that was too low, so putting a volume or two of Knuth under it raised it to the right height. That's the only time I've ever used them though.
- giantg2 4y agoQuite expensive for that use.
- jahewson 4y agoAnd yet significantly cheaper than Apple's Pro Stand.
- leoc 4y agoAnd more prestigious to boot.
- randcraw 4y agoMy laptop is raised to the height of my other monitors by Feynman's boxed set of Lectures on Physics, Aho & Ullman's Foundations of Computer Science, and a Scott Adams compendium. This way my computing is based on a strong foundation...
- rjha 4y agoLoL :) we should have a __how you boost your monitor to the right height thread __ I use Mckusik's freebsd book, Brooks computer architecture, Myth and meaning by Levi-Strauss. The last one is for calibration only.
- urthor 4y agoUllmann's is actually out of print and increasingly scarce. Your laptop stand will likely become a family heirloom in the decades to come.
- 4y ago
- kragen 4y agoTAOCP is not job training now, if it ever was; that is trying to get the cart to pull the horse. The point of a job, unless you're lucky enough to get a job where you can change the world, is to pay your living expenses so that you have the leisure to do things like read TAOCP and write Sudoku solvers. If that's not your idea of an enjoyable vacation, don't read it; you'll regret it.
- openfuture 4y agoThe world changes through the collective effort of the people who inhabit it. Not because some demigod wrote a script.
- bo1024 4y agoThe one can be a special case of the other...
- kragen 4y agoMostly the world changes due to unpredictable emergent phenomena, but occasionally you do get intentional changes as well. But intention is individual, not collective; there's no such thing as collective intention. At best you have many people's intentions in agreement. Rarely does that arise in a workplace.
- psychoslave 4y agoWhat do you mean with "collective intention"? A person intention is the result of collective effort of its neurons. Things like collective representations and collective unconscious are well established concepts. Whether these things positively exists outside of one mental experiment is an other matter, but so is the notion of individual and self.
- kragen 4y agoMerrily, merrily, merrily, merrily, life is but a dream.
- thomasahle 4y agoAs an algorithms researcher, I have often been reading Knuth on the job. Most of the time, perspiring with worry that a 1960s article might have scooped me.
- deleted 4y ago[deleted]
- jseutter 4y agoI used them to implement an arbitrary precision math library for an embedded processor that needed to do some precise calculation in an autonomous environment. The embedded processor had no floating point capabilities. The book showed me the method of how to do it efficiently in a manner that could be adapted to the 16 bit architecture I was working with. It also showed me how to detect and handle overflow situations, as well as when they would happen. It kept me from creating a buggy, error-prone pile of crap code that I'm certain I would have created at the time. At the same time, it took me a couple of days of study to understand the two or three pages I was interested in. The material was the most condensed material I have consumed in computer science. Like you say, you have to learn a new machine architecture and assembly language to understand the examples. Things you learn from those books come at a high cost in terms of time and effort. It reminds me of studying the bible, where cross checking, reading different translations, studying hebrew and greek, and the culture of the day are all necessary if you want to get the best understanding you can. The TAOCP books are scholarly articles and almost a kind of shorthand notation of computer science concepts.
- kragen 4y agoIt may not be a coincidence that one of the author's other books is on Biblical studies: https://www-cs-faculty.stanford.edu/~knuth/316.html https://www-cs-faculty.stanford.edu/~knuth/316.html I didn't realize it had been blurbed by a professor emeritus at a seminary (as well as Martin Gardner).
- Tomte 4y agoMy take on it: https://www.2uo.de/Books/316-bible-texts-illuminated/ https://www.2uo.de/Books/316-bible-texts-illuminated/
- kragen 4y agoInteresting! A small correction: "innumerate" means "incapable of doing arithmetic"; perhaps you meant "innumerable", which means "incapable of being counted". Also you have "wuthor" for "author", "bible" for "Bible", "donÄt" for "don’t", "WHat" for "What", and "theologician" for "theologian".
- bugfix-66 4y agoI've been randomly skipping around inside these books for a long, long time. They're full of little gems that you won't find elsewhere. For example, in Volume 4A there's a simple technique for comparing two pointers in bit-reversed form. This technique was patented by Hewlett-Packard as a method of randomizing search trees (treaps): https://bugfix-66.com/fdb8bb4fa84cf810aa25ff40c88a13c18744109de057431280007fafb484ebab https://bugfix-66.com/fdb8bb4fa84cf810aa25ff40c88a13c1874410... From Volume 3, here is by far the fastest method of sorting integers (Singleton's method), an algorithm I have used professionally several times (e.g., for beam search in a speech decoder): https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054... Knuth's books are just packed with gems like that. The meticulous high quality of the books is also remarkable. However, if you look very carefully you can find rare mistakes. I received payment from Knuth and have an account at his bank: https://www-cs-faculty.stanford.edu/~knuth/boss.html https://www-cs-faculty.stanford.edu/~knuth/boss.html Getting your name on the above list was once a Hacker rite of passage.
- Tomte 4y ago> However, if you look very carefully you can find mistakes. Opened the book, thought "no, it can't be". Agonized for days and weeks if I'm making a fool of myself. Sent the bug report. First word in first sentence in first paragraph in first chapter was wrong. Got my cheque. ;-)
- mkehrt 4y agoWhat was it?!
- Tomte 4y ago"Infinitely many alphabets can be generated by the programs in this book". But the number of parameters is finite, and all parameters have a finite number of possible values. His errata changed the wording thus: Zillions of alphabets can be generated by the programs in this book. (https://ftp.rrze.uni-erlangen.de/ctan/systems/knuth/dist/errata/errata.twelve https://ftp.rrze.uni-erlangen.de/ctan/systems/knuth/dist/err...)
- kramarao 4y agoI used them to implement a random number generator in an embedded system to generate morse code, for training ham radio operators. I also used him KMP algorithm for writing pattern matchers. I suspect that most of these algorithms have been implemented and available as libraries for people to use. The challenge of programming has moved from designing such isolated algorithms to modeling the problems, modularizing the code, creating an evolutionary path for a system, and balancing the wants of tomorrow with the needs of today. Still, if you are working at the core problems of organizing, searching, sorting, managing data, you might might the books useful.
- lupire 4y agoThis is also why MIT switched its intro to CS class from Scheme to Python ~15 years ago.
- kieckerjan 4y agoOver 25 years ago I was researching algorithms for a search engine I had been commissioned to write, and for its disk allocation strategy I had settled on a "buddy algorithm" from The Art of Computer Programming Vol 1. It had nice properties and was easy to make. I implemented it to a tee, only to see it fail (I think in the part that merges abandoned blocks). I banged my head against this problem for days before finally daring to entertain the notion that the algorithm might be flawed. This was TAOCP after all! Turned out my university library had an old edition and I had run into one of the scarce bugs in it (which had been duly fixed in the next edition). So yes, I have used TAOCP on the job and, to prove it, a scar of which I am rather proud.
- lupire 4y agoIf you can't find a bug that exists in your copy of TAOCP, maybe you didn't learn what it was teaching you :-) (Adapted from Feynman, who apologized for errors in his Lectures, but refused to accept blame for anyone who cited them in a dispute. The truth speaks for itself.)
- Affric 4y agoWould you be willing to provide a reference for the original? My Google-fu is failing me.
- lifefeed 4y agoVol 1 is just an intro to math and his language, you don't really need it, but it's kinda fun. I read some of Vol 2, Seminumerical Algorithms, to hone my instincts on how random numbers work in practice. I have referred to it on occasion when people say things like, "if we seed the random number generator, take the random number, then feed that into the seed, the result would be more random." I read most of Vol 3, Sorting and Searching, when applying for jobs. It was more interesting than leetcode grinding. I don't know if it was more useful, but it was better for my sanity.
- disgruntledphd2 4y agoI dunno, I found that chapter 2 was incredibly useful, as he covers all the fundamental data structures very very well. Mind you, I actually learned his assembly (MMIX) so maybe it was more useful for me.
- linschn 4y agoA colleague of mine had invented a technique for factoring composite numbers, that he thought would be quite fast. I thought a little about it and saw that it would degenerate into sat solving. I checked taocp and indeed my colleague's idea was in there. Also a faster algorithm was presented in the relevant section. I lended the book to him and we saved around a month of work.
- bombcar 4y agoThis is exactly what TAOCP can be best at - if you know enough about the problem domain to be dangerous, or even to build a solution, you will know enough to read the relevant portion of TAOCP, where it is very likely you will find value.
- lupire 4y agoThere is quite a lot of money waiting for you if you ever figure out how to factor composites quickly. (Any old bum can factor primes quickly.)
- linschn 4y agoWe had a very specific use case, where the input was a known composite, and some properties of the factors were known. Also, while no fast algorithms are known (and may never be depending on if p=np) some are faster than others depending on the properties of your inputs, and choosing the right one can mean saving a lot of time and effort.
- deltasepsilon 4y agoIt just means you're not doing anything interesting on your job. If you have constraints, i.e. not enough compute, not enough memory, not enough storage, then you'll need a solution and, odds are, somebody has had the same problem before and it's been written up already in Knuth's TAOCP. Of course, the problem won't be exactly in the form it's been written up, but you have to have enough experience and knowledge to know the abstract form of your problem in order to figure out what parts of TAOCP would be useful to you. Want a concrete example? Well, I'm in the generation that go to assume that storage was basically constant access regardless of whether you wanted to access the 1st byte, or the Nth one. New, high-performance memory like NAND flash, is weird because it's fundamentally unreliable. In order to make NAND reliable you have to do stuff, and some of the stuff you can do, makes NAND look like tape, and accessing tape is best done sequentially. Guess what TAOCP has? All these great ideas about maximizing random access to sequential media.
- wing-_-nuts 4y ago>It just means you're not doing anything interesting on your job. That man had a family...
- dc-programmer 4y agoSerious question - why wouldn’t you search for the algorithm you need (or the problem statement) on Google scholar these days? I have the books but if I ever found myself reaching for them at work, I would consult most recent literature
- bcwarner 4y agoThe most use I've gotten out of it was when I had it on my bookshelf in my Zoom background while TAing a class I think. One of the head TAs recognized it and asked if I had actually read it, and I told him I managed to read through volume 1 once and not solve many of the problems, which took about 3 months reading ~10 pgs/day. He was still impressed, and I think it helped me get the head TA role after he graduated, as he nominated me for it. In terms of actual programming use, not much, but I still haven't read the other volumes yet.
- lupire 4y agoShouldn't TA jobs be handed out based on you knowledge and teaching and management ability, not fashion prejudice?
- bcwarner 4y agoYeah stuff like that is handed out on competence, when it came to situation, there were a few other equally qualified candidates who had been TAing that class. It worked out so we all held head TA at one point. TAOCP in the background probably played a tiny role if anything, but it's the one distinguishing event I remember, which is strange and funny to think about.
- dragontamer 4y agoI'm not sure if TAoCP is "workplace on the job" material. TAoCP is aiming at damn near "perfection" of programming. Donald Knuth is analyzing the exact assembly language of all of his decision-making with these algorithms. The assembly language is represented as a random variable, and an _exact_ count of those assembly language statements (in loops and other complex jumps) is analyzed. Everything from the highest-level algorithm design / mathematical concepts is discussed... down to the lowest-level assembly level details / implementation of the code. And everything in between. ----------- As such, when Knuth / TAoCP covers a subject, it feels comprehensive, in a way that no other writer has ever accomplished. So how does this work out in practice? Well, there's plenty of tutorials on hash tables out there. But only Knuth's writing on Hash tables / linear probing has ever hit the entire subject for me. Other books will go over linear probing vs quadratic probing vs double-hashing. Meanwhile, Knuth carefully derives the formulas of each, and how it changes at the assembly level implementation. ----- Is that useful for workplace environment? Probably not. In work, you only need to know "Linear Probing Hash Tables work like this, do it", and maybe not the analysis of it. But if you're doing more fundamental programming, such as "GPU Implementation of Hash Table", something that very few other people have done... the Knuth-level analysis is the only thing that hits "rock bottom" and gives me all the insight "behind" the data-structure and its design. I'd say Knuth's stuff is for people who invent new fundamental data-structures or other implementation details like that. Its not for typical workplace programming. -------- For anyone who wants to know Knuth's writing style, I think his writing on Alpha-beta pruning (from the 1970s) is an excellent introduction to Knuth's writing style. "An Analysis of Alpha-Beta Pruning" by Knuth / Moore, 1975. Alpha-beta pruning always was kinda mystical to me. But Knuth recognizes the intermediate steps needed to understand the subject fully. The brilliance of discussing F1 (branch-and-bound) before discussing F2 (alpha-beta pruning) cannot be understated. Knuth recognized that branch-and-bound is what most people thought of by Alpha-beta pruning. But then comes up with specific examples where F2 (true alpha-beta pruning) makes a difference over F1. And then uses math to demonstrate how often these cases come up. Does it help in implementing AB pruning? I dunno. But it helps a lot if you wanna change AB pruning / change the fundamental search and understand why things are done that way. You only need to study "F2" if you're copy/paste programming. But the study and analysis into "F1" (branch and bound) holds deeper understandings to the entire concept of search trees. Even if you never, ever, ever will program F1.
- klik99 4y agoPart 1 is the most "useless" - it's basically required reading to be able to read the rest of the book. There are a few sections in data structures that I read to actually apply (I can't remember the exact parts, but I remember pouring over the book), but mostly it's enjoyable if you like programming for programmings sake. If you think of programming as a practical means for achieving some end (job or creative pursuit) then these books aren't for you. There is absolutely practical stuff in here, but it's all shown from first principles. At any rate, don't judge the book on the first part - the first part is important to get the rest of the book, and it's as well written as the rest, but it doesn't reflect how much fun (again, fun for those who are into programming in itself) the rest of the book is.
- lupire 4y agoA great book is to be pored over with a pour-over.
- klik99 4y agoOh I forgot to mention - I’m literally made of liquid so I read books by pouring over them, sorry for the confusion!
- slavapestov 4y agoPart 1 has some cool material. The mathematical preliminaries, polynomial arithmetic to motivate linked lists, and symbolic differentiation to motivate trees. The MIX simulator written in MIX too!
- klik99 4y agoYes, to be more clear about my point: there is a lot of learning about MIX to set the groundwork for future stuff, which can feel arbitrary and disconnected from practice. It can be off putting to a new reader. It took longer to read than just about any other part of the book, since the rest of the book has a much higher density of interesting material. Also it’s the only section that is really “required reading” and I most enjoy this book by bouncing around. I just want to encourage new readers to stick with it, it’s not exactly representative of the whole book.
- treffer 4y agoTAOCP is the encyclopedia of algorithms. It is usually not something you read front to back. I have so far found 1-2 references that I could otherwise not decode, plus wanted to know about n-way sorting. And that's how I would recommend to use it. I have it on my shelf to pull it out if I have to. Which is rare but it does happen. And as such it proved value to me, on the job, as I know how to get into these things as needed. But it has a similar insane price to usefulness ratio as an encyclopedia. What I've done so far? Everything from Sysadmin to DevOps to Engineer (data heavy) to SRE to Data Engineer. If you want to learn DSA then you should probably start with something that goes less deep, is less complete but covers useful algorithms from many areas.
- dyingkneepad 4y agoI read selected parts of it while in the University, studying Computer Science. I think that is the more appropriate time for you to read such a book, since it gives you the basics. I read the section on Hash Tables while at work because one of our hash table implementations was exactly what he proposed in his book and there was no explanation on why some things were done, especially the choice of the hashing functions. I first tried looking for the information in other books (like Cormen et al.) but everybody just simply references the book from Knuth without explaining things either. So I bought it just for that... I really really wanted to have time to read the rest of it. But also my comic book collection and a whole lot of other books I bought in the last 30 years. Maybe one day.
- lupire 4y agoTAOCP is far far more than the basics.
- nottorp 4y ago> found them useful ON TGE JOB? Algorithm training is useful on most jobs for preventing you from going accidentally quadratic.
- commandlinefan 4y ago> actually read these books AND found them useful ON THE JOB I did read all three - it took me about three years to get through all three and (at least try to) work each exercise. Useful on the job? No, not really, but I can't think of a non-fiction book(s) I've enjoyed reading much more than these. All of the code examples are in assembler, and not just any assembler, his own imaginary assembler (but you can download a compiler and an emulator for it). I'd be hard-pressed to come up with anything that he covers here that's not already part of the standard library of any programming language you could possibly consider using - but it's still great reading, and illuminating in indirect ways.
- todd8 4y agoI read these the first time so far back that the extensive section (with the fold out pages) covering sorting on external tape drives was of interest to me. Over the intervening years I've gone back to these books many times to check on my understanding of subjects. (I've also bought and used all of his other books too: TeX, Concrete Mathematics, and other collected works.) I worked as an OS Architect at IBM and then Chief Scientist at a very successful startup. Subjects like analysis of algorithms, memory management, optimizing disk access, search tries, random number generation, and many more found in TAOCP have all been useful in my professional life. I've had to give many technical presentations and to present my designs to committees of experts and CS professors. Knuth wasn't the only source of my preparation for this kind of work, but he was a very important source. Are there better books on algorithms? Maybe. I also like the popular Introduction to Algorithms [1], Sedgwick's Algorithms [2], and Skeina's Algorithm Design Manual [3]. All of these are good and all of them sit on the shelf right next to Knuth's books. Depending on the subject, any one of these might have the best treatment. BTW, Sedgwick was a Ph.D. student of Knuth. To keep up with the literature I also recommend a membership in the ACM with access to their digital library. [1] Thomas H. Cormen , Charles E. Leiserson, et al. (2022), Introduction to algorithms, MIT Press. [2] Robert Sedgewick and Kevin Wayne, (2011), Algorithms, Addison-Wesley. [3] Steven S. Skiena, (1997), The algorithm design manual, Springer.
- gjm11 4y agoI think #1 and #3 of these make a particularly good combination; they have very different and quite complementary merits. CLRS is rigorous and precise and analytical and theoretical. Skiena is handwavy and pragmatic and not always quite correct. CLRS is written for people who will be implementing complicated algorithms. Skiena is written for people who will be using other people's implementations. CLRS is deep. Skiena is shallow. CLRS is heavy going. Skiena is pretty easy reading. (But ignore everything Skiena says about generating random numbers.)
- sn9 4y agoJust to throw in some praise for Sedgewick's books: the diagrams are so gorgeous that even Edward Tufte cites them for their beauty and utility. https://www.edwardtufte.com/bboard/q-and-a-fetch-msg?msg_id=0001OR https://www.edwardtufte.com/bboard/q-and-a-fetch-msg?msg_id=... Ctrl-f "Sedgewick".
- secondcoming 4y agoI bought them on a whim and they just lay around for years. I gave them away to someone who thought they were interesting. The assembly language he invented added very little to his work.
- disgruntledphd2 4y agoI dunno, I learned the newer one (MMIX) and it taught me so much about low level programming, honestly some of the best investments of time I ever made. That being said, if you already know ASM/C then maybe it wouldn't be as useful.
- rented_mule 4y agoTAOCP was invaluable for a couple of jobs I had. One job involved indexing arbitrarily large books (gigabyte+ was not uncommon) on an embedded CPU with less than 1MB of RAM available to the indexer (this is 15+ years ago, before smart phones). It also involved searching hundreds of those books in a few seconds with ~8MB of RAM available. Indexing was taking place on a single core CPU while the user was using the device, so the indexer had to be able to stop its work within a few milliseconds of any user action and resume later without losing progress. On the surface, Knuth's concepts felt old fashioned (abstract assembly language and talk of multiple tape drives for intermediate storage). But that mapped very well onto this indexing problem. Books and indexes resided on an SD card and individual files on the SD card could act very much like Knuth's individual tape drives. Doing append only operations on those files (as you would want to do on a tape drive) proved fast and reliable. My 1MB of RAM would have been an embarrassment of riches when the original volumes of TAOCP were released. I don't remember if any of the algorithms that shipped as part of that device were straight out of TAOCP, but the thinking involved was heavily influenced by those books. Whenever I was stuck, it was back to Knuth. My next job was focused on distributed systems. We were rebuilding an ads system because the older one couldn't handle the scale needed. That involved lots of MapReduce and lots of stream processing (before there were good open source stream processing packages to build on top of, this started in 2010). Those same tape drive oriented algorithms came right to the surface again. When processing TB or PB of data, you want single pass algorithms wherever you can come up with them - merely linear isn't good enough. Same as tape drives - there's a huge benefit if you can avoid having to rewind. And so many stream processing primitives (windowed joins, groupings, etc.) are exactly what people were doing with tape drives 50 years ago. Now we were using many GBs of RAM spread across many machines, but relative to the amount of data being processed, it was still miniscule. This all required spotting the similarities between the world Knuth drew his examples from and the constraints I was working under. But once I did, his concepts were quite useful. And the framework for thinking about things was more valuable to me than any specific algorithm or data structure. It was much more useful to me as a narrative to read rather than a reference to pull something out of.
- sn9 4y agoHow on earth do you even find work like this? I would love to have a career working on problems like this but can't imagine how I'd get a job doing anything but commonplace back-end work.