Ask HN: Looking for a book on algorithms and data structures
I want to learn Algorithms & Data Structures from scratch then move on to doing LeetCode.
But I want a structured guide / textbook that I can follow which also contains exercises.
I have checked the CLRS book, but, it's more of a reference than a book that you can read from cover to cover. For example a basic Stack is explained in a page and a half or two, for me this is not enough, I want a book that can go into the details of each specific DS or Algorirhm.
*TL;DR:* Are there any books better than CLRS for DS & Algos?
97 comments
[ 2.8 ms ] story [ 187 ms ] threadWhy not? It's a simple data structure. What more do you think can be said about it?
http://i.stanford.edu/~ullman/focs.html
"This book has been taken out of print by W. H. Freeman. You are welcome to use it if you like. We believed in 1992 it was the way to introduce theory in Computer Science, and we believe that today."
The book's introduction to stacks is in chapter 6, link: http://infolab.stanford.edu/~ullman/focs/ch06.pdf
I'm not aware of any book like that. At the uni, the process is repetitive and incremental.
First you learn how to implement the algo, then you learn how to count (discrete math) and, finally, you learn how to analyze its complexity. Concurrently, you might see some more details on how those data structure are used in Operating System and learn how to implement them in some lecture about parallel computing.
MIT has a great resource online. They have recorded lecture, exercises, lecture notes with reading suggestion, etc.
Their intro to algo. https://ocw.mit.edu/courses/electrical-engineering-and-compu...
Also, see what it the reading for similar lectures on other universities.
1. https://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/03...
2. https://www.coursera.org/learn/algorithms-part1#syllabus
I can't say if it is good or not, I lost mine well over a decade ago.
Amazing book. Very readable. I highly recommend it. The book has a section call "War story" at the end of each chapter in which Skiena shares his real life experience of when the contents from that particular chapter came in handy for him.
Go through it. You won't regret
https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...
You should really consider taking a few community college math courses if you're serious. Math is extremely difficult to learn on your own. Not only because of not knowing what you don't know, but because it requires intense effort and repetition which is very hard to force yourself to do. You can work through the concepts and delude yourself into thinking you understand something when really you're just hand waving it. Taking an actual course and being faced with the gaps of your knowledge by someone else is very humbling and essential to actually learning it.
I keep seeing this and I don't quite understand how this one works.
If I were studying math on my own (which I've done and still do), I'd do the following:
1. Pick a book. Say, Rudin's Principles of Mathematical Analysis[0]. Read a section, then attempt problems. Pick a problem. Say, "prove {1/n: n is natural} U{0} is compact directly from the definition(not using Heine-Borel)". It's guaranteed your "proof" is not a proof.
2. Compare your solution to existing solution manuals or ask a question on MSE[1]. Since the given book by Rudin is super-massively famous, each question has probably been asked/answered about a bagillion times each on MSE, so just searching MSE alone would likely to spit out many answers to your questions. People on MSE will tell you exactly why your "solution" is wrong and where you tripped up. Sometimes even the clarifying answers are hard to understand. But then you can ask new questions, think more, correct your misconceptions until it all finally clicks. Do that with all the rest of the problems[2].
I don't see how the process above is delusional.
[0] This book is not a realistic fit for a novice, though. Instead, one would start with books like [3], [4], [5], [6] to learn how to prove things and think like a mathematician would.
[1] https://math.stackexchange.com/
[2] In reality, the more math you see and do, the more mathematically mature and less dependent on others(to check your work) you become. In fact, if you can solve any problem in "B@by Rudin" and some famous abstract algebra textbook (say, Dummit & Foote's "Abstract Algebra") cold, you're way ahead of most any undergrad math major in the world! Because standards on undergrad math majors are not that high, nor that brutal the world over no matter what they say. If, additionally, you can solve any given problem in a book like, say, Hatcher's "Algebraic Topology" or any other famous grad level textbooks on, say, differential geometry or, uhh, functional analysis, you're officially in the big leagues. Again, if you're worried about being delusional about your proofs, you can always present them on MSE.
[3] "Book of Proof" by Richard Hammach. It's online free.
https://www.people.vcu.edu/~rhammack/BookOfProof/
[4] "Discrete Math" by Susanna Epp
https://www.google.com/books/edition/Discrete_Mathematics_wi...
[5] "How to Think About Analysis" by Lara Alcock
https://www.google.com/books/edition/How_to_Think_about_Anal...
[6] "Linear Algebra" by Kuldeep Singh
https://www.google.com/books/edition/Linear_Algebra/BJNoAgAA...
Because those that are just starting to learn math don't take your approach to learning.
I had a lot of bad habits that I had to break when I was learning math that really caused me to do poorly in many classes. If you are coming at it from a more qualitative field, then it's very easy to read the book and come away with nothing from it.
I'm taking a discrete math course and I was trying to offer up some advice on the school's subreddit to someone struggling in the class. They mentioned something about me taking the easier prof, so that's why I'm doing well. I said that I had fully worked at least 50 problems in each chapter we covered and asked how many they had done. The response was I went to lecture, read the notes once, and attempted the homework exercises; I didn't know you had to do some much work in this class.
Alternate: Ask a question, get a not-quite-right answer, and find yourself completely stuck two chapters further in with no way of figuring out where you went wrong.
It's very rigorous and considered one of the more difficult reads. But if you start at chapter 1 page 1, it covers all the math you'll ever need for the rest of the books (which is sufficient maths to reach masters or even PH.d level comp sci)
I know I've recommended it to high schoolers. A lot of math is just getting used to the nomenclature and vocabulary. The sooner you get used to rigor the better
Chapter one of TAOCP for better or worse, is a very rigorous mathematics introduction.
I'm not recommending it for it's algorithms (which are unfortunately somewhat out of date). I'm recommending it because it's an incredible mathematics introduction, albeit a very difficult one.
So tape merging is in fact, useful again strangely enough. That's one of the sections that suddenly and surprisingly has regained relevance.
But Volume 1 has lots of out-of-date advice and is somewhat of a shame, because its otherwise an excellent introduction to computing + the mathematics needed to understand computing. For example, the assembly language is based on the 1960s computers, such as decimal computing and 6-bit numbers (based on the days of old, before 8-bits were standardized).
Functions are introduced by self-modifying code first and foremost: by rewriting "jump" instructions at the end of functions as a return. No one does this anymore: pretty much all compilers do the stack-thing instead. (Push return address onto a stack register).
The Fascicle on MMIX updates a lot of those sections to a modern-like 64-bit assembly language. However, the sections on cofunctions, arrays, garbage collection aren't part of that update... and should be updated (Knuth's discussion on these concepts is great, but are told in an "old way" based on 1960s tech)
Volume2: Seminumerical Algorithms (chapter 3 / 4) is again, a decent introduction to the subject. But the RNG stuff is fully obsolete. The statistical tests may have passed muster in the 1970s or 1980s, but today's statistical tests (aka: PractRand) go above and beyond what Knuth discusses.
There's a lot of interesting discussions in the randomness chapters: such as the efficacy of multiplication when it comes to bit-mixing (and I feel like modern RNGs are sleeping on that tidbit), but modern RNGs are generally based on a simpler sequence of ADD / XOR / SHIFT instructions based around the concept of permutations / perfect bijections.
----------------
Ironically, I consider the section on "tape sorting" to be "suddenly up-to-date" again. Modern RAM acts more like a tape (sequential is far faster than random), meaning that thinking of sorting problems in terms of external-sort is surprisingly relevant.
Given that today's cache is 768MB (see AMD's Milan-X CPUs: expected to be a ~$5000 CPU-server chip), we see that L3 cache basically serves as the RAM from Knuth's time, while today's DDR4 RAM really acts as the fast-sequential / slow-random layer that Knuth studied so much.
To be perfectly honest, I doubt I would've ever gotten through college-level maths without being forced to do it, as it can be very frustrating and difficult in the beginning. Unless you are quite confident in your self-discipline and enthusiasm to learn maths, rather than books I'd recommend something interactive (online course, forums, challenges).
If you are interested in a starting point to learn mathematics that are relevant for CS, I'd start with propositional logic and boolean algebra, as well as proofs via induction.
You can find Discrete and Combinatorial Mathematics (an Applied Introduction), 5th Edition, Ralph P. Grimaldi online and an answer key can be found online as well. (This book covers two discrete math courses. Chapters 1-5, 7, 8, 12 is a first course in discrete math. I'm not sure what chapters the second course covers, but that requires linear algebra as a prerequisite.)
It's not perfect, but it's a start. I think you need to be familiar with some high school algebra, exponents, and logarithms. You can find some review information in the appendix. If you have troubles with recalling that information, then you can try Khan academy. (It really is an if you don't use it, you lose it situation with much of math.)
You're probably aware of this already, but most people don't read the book and come away with the knowledge required to solve the problems. You'll need to work through the examples in the chapter, be able to recall the definitions and theorems, and then work the exercises at the back of the book.
I think the discussion of proof methods is pretty poor in the book. You can find many intro to proof method type supplemental notes online to help fill in the details.
There really is so much information out there that you can pretty much always find an alternative explanation or viewpoint for undergrad level material. Many profs will post their own lecture notes, homework, and solutions. There are some math forums that have explanations. So find a book you're reasonably comfortable with and supplement it with extra material.
There's a small workshop for it here: https://learnaifromscratch.github.io/calculus.html throwing in some youtube tutorials. The book presents everything as functions and their parameters, like linear functions, trig, sigmoidal, e and logarithms, you learn all the parameters to these functions and can type into desmos online graph to see what they're doing visually. You don't have to do the whole thing just use it for background material when an algorithm text uses calculus methods like L'Hopital's rule.
Poh-Shen Loh has a discrete math course open on his youtube channel https://www.youtube.com/c/DailyChallengewithPoShenLoh/search... you can use the book he recommends to look up anything that is assumed knowledge in lectures. Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. A book called Asymptopia by Spencer is well done too, good chapters for learning everything you want about big-O/omega/theta some topics are advanced and some anyone can do.
https://ocw.mit.edu/courses/electrical-engineering-and-compu...
This prompted me to check out khan academy. Man, that is an incredible resource. I really envy the schoolchildren of today that have instant access to this incredibly smart tutor, who can be rewinded at the touch of a button.
Edit: unfortunate for me ofc.
https://www.amazon.com/Algorithm-Design-Manual-Computer-Scie...
And his CSE 373 course lectures: https://www3.cs.stonybrook.edu/~skiena/373/videos/
Unfortunately, it isn’t done yet (1), and the completed parts have are very basic and have parts that are a bit dated (multi-tape sorting, for example)
(1) and likely never will be. Knuth is turning 84 in two months, and isn’t even halfway writing it, after almost 60 years
It would have to be done in Knuth’s spirit, and there would be lots to argue over what to include, before even writing about it
How complete are Knuth’s notes? Would he have found Foo important enough to include, even though his notes don’t mention it? Should the completion include stuff discovered after his death? Should earlier volumes be revisited, as Knuth probably would do, if he had an eternity to live?
Note I am _not_ saying TAOCP isn't readable, I consider it very well written. But it's terse, hard, too deep and too detailed for a beginner, IMHO.
What really put me to the next level is this amazing free training program which I still recommend anyone who wants to nail the interviews. It teaches each algorithm and data structure and gives you appropriate challenging exercises so you really understand them: https://train.usaco.org/
It's available for free online, or if you'd like you can buy a physical copy. It's got 14 chapters that take you through a variety of data structures, introduces you to the theory behind them, and teaches you the basics of analyzing them.
I've done many of the exercises from this book, and found them useful for learning the topic.
https://timroughgarden.org/videos.html
http://www.algorithmsilluminated.org/
https://algs4.cs.princeton.edu/home/
You can even find an excellent two-part MOOC on Coursera:
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/algorithms-part2
Maybe it's not the "purest" class or book, but it's engaging and it lets you understand how algos work AND how to use them in practice.
I wonder though if "programming contest" (usually more like "algorithm puzzle contest") books like Skiena's might be useful, though I can't help but think that doing an algorithms course first shouldn't be useless.
[0] https://www.edx.org/course/data-structures-an-active-learnin...
[1] https://stepik.org/579
I liked ALGS4 by Sedgewick as my introduction to Algorithms. I still refer to the Coursera course. I actually started with CLRS and doubled back to ALGS4. I wish I did it in reverse order but it was still useful reading CLRS and refreshing my math skills.
I would say grab a few and see which ones you like. CLRS, ALGS4, Algorithm Design Manual, and Algorithm Design by Kleinberg and Tardos are a good start. You can look in the bibliography of each books for more suggestions from the experts themselves.
If you're interviewing for senior positions, it is worthwhile to read through Designing Data Intensive Systems. This will prepare you for System Design interviews where you do need to actually understand stuff.
Do you mean "Designing Data Intensive Applications" by Martin Kleppmann? That's what most of my search hits found. If something else, do you have a link? Thanks.
I admit I haven't explored many other books on this topic but CLRS is very good in my opinion.
The book not only describes the algorithms per se, but also teaches how to think about the algorithms and the problems they are solving. I enjoyed it very much as a complimentary reading to the classic Knuth volumes.
[0] https://en.wikipedia.org/wiki/Udi_Manber