Best algorithms book I ever read | Hacker News Reader

Best algorithms book I ever read

eriwen.com

208 pointsslashams42 comments

Algorithm Design Manual book review

I also highly recommend Sedgwick: http://algs4.cs.princeton.edu/home/

I haven't read the new edition, but his older editions were very accessible. More for practitioners. For example, I don't think there were many, if any proofs (but I may be way wrong on that). A good amount of actual code though.

Sedgewick's book is worth it for the diagrams alone. The fact that the writing is also good is a nice bonus.

> The only caveat here is that most of the examples are written in C, which can be troublesome if you don’t know or have forgotten about pointers.

It is hard for me to take advice seriously from someone who says this.

I bought this book on Yegge's recommendation as well, and this actually was a stumbling block for me at first.

"Whyyy is this variable, ★★p a pointer to a pointer?! p is never referenced in the function, so why are we two levels of indirection down?!" I didn't realize at the time that pointers are copied by value in C, so in order to modify the pointer you need to give the function a pointer to it.

I guess it was worthwhile, though, because it encouraged me to play around with C[1] a bit in order to grok it.

P.S. Sorry for those stupid stars, HN kept eating my highlights. Any way to avoid that?

[1]https://gist.github.com/661564

Indent your "code" with a few spaces.

    int **p; /* I used 4 spaces in front of "int" */

Ah, thanks. I was hoping there was an inline way, but I guess this will have to do.

um, why? It seems perfectly reasonable to me that examples written in C could be troublesome to someone who doesn't know C.

I don't think anyone can forget pointers though, except in Winnie the Pooh way.

Also, anyone learning data structures should know pointers or at least references as a prerequisite. You can't reason about efficiency in data structures knowing only the high level comfort of Python.

I think it's a reasonable caveat and don't find its inclusion undermining the OPs main thrust.

I've read Skiena's book(first part) and CLRS(about 15 chapters) and I think CLRS has much more to offer. The number of algorithms, rigorous proofs, and explanation that CLRS offers are not comparable with Skiena's. I would suggest Skiena's for start but for a more thorough understanding a switch to CRLS is essential.

I've read both books, and I think that they're aimed towards different audiences. CLRS is aimed towards computer scientists. It offers a fairly rigorous treatment of algorithms, mathematically proving correctness and performance. The Algorithm Design Manual, on the other hand, is aimed at programmers who are willing to take claims of performance and correctness at face value if it leaves room to discuss further optimization and compositions of algorithms into solutions for problems.

EDIT: Though, that's not to say I wholly endorse CLRS. I think Knuth's The Art Of Computer Programming is more detailed and more mathematically rigorous than CLRS. Unfortunately TAoCP is multiple volumes, while CLRS manages to be a single (substantial) volume.

I can't agree more with your judgement. I've read all these three books and the fact is just like what you mentioned. CLRS and TAoCP use a lot of space to prove the algorithms correct(especially TAoCP, it even uses different ways to prove one algorithm) and that makes me feel dizzy. Perhaps I'm just a programmer not a computer scientist.

But I have to say that use some time to read CLRS and TAoCP is worthwhile. It will help u know more about algorithms and avoid the condition that just know how but not know why.

I agree with your analysis. From my review of Skiena (http://www.mccaughan.org.uk/g/books/alg-design.html): "Put differently, this is a book for algorithmic engineers rather than for algorithmic scientists." And: "You really wouldn't want this to be your only algorithms book. It doesn't have enough in it, it doesn't go deeply enough into anything, and a certain amount of the bracing mathematical rigour that the book so conspicuously lacks is ... well, good for the soul, I suppose. So go buy Cormen, Leiserson & Rivest. Then, unless you're already an expert algorist, buy this one too."

I read Skiena's book as preparation for interviews after having gone through a course using CLRS the year before, and I definitely feel like that is the best way to do it. I feel like reading Skiena got me back to mostly the same place I was last year after being waist-deep in CLRS, but I do feel that a more thorough examination of algorithms is needed to really grasp a lot of the nuances. it's perfect for dusting off the cobwebs though!

Does Skiena's book contain solutions to the problems? I love reading Cormen but iirc there are no solutions to the problems. Programming Pearls is awesome too... there are solutions to many of the problems (but not all). Ironically the most helpful book I've read is Programming Interviews Exposed. This book contains solutions that are explained very thoroughly.

In a way - I read Programming Interviews Exposed, and it definitely helped to brush up on implementation details, but Skiena offers more of a cookbook approach to tackling algorithmically hard problems. The second half is full of generalized problems, as well as the potential approaches to solving them using the concepts introduced earlier. While this might not be as used on an interview (since the problems may be a little too involved), I think it's definitely much more valuable for actually solving problems.

Solutions to selected exercises can be found at:

http://www2.algorithm.cs.sunysb.edu:8080/mediawiki/index.php...

Also, the course page has some interesting stuff as well (links to assignments, lectures, etc.):

http://www.cs.sunysb.edu/~skiena/373/

And videos, here: http://www.cs.sunysb.edu/~algorith/video-lectures/

Which other algorithms books has the author read?

Good question. I perused Skiena's Algorithm Design Manual, but it's way to fluffy. If you enjoy hand-waving, it's a nice read. But if you are either after the theory or after an implementation, I've read better books.

Sedgewick's Algorithms is good for implementations in imperative languages. Okasaki's Purely Functional Data Structures is a nice introduction to some algorithms and data structures suitable in a purely functional setting. He also addresses laziness.

And finally for the theory, Schrijver's "Combinatorial Optimization: Polyhedra and Efficiency" tells you more about P and the boundary to NP than you ever wanted to know.

Those are just a few that I enjoyed, and I can't claim they are the best.

For example Structure and Interpretation of Computer Programs is definitely worth a read, but it won't help you with algorithms directly.

I think it's funny that people still think walking people through algorithms on a whiteboard is a good way to hire programmers.

Ability to communicate your ideas is an important skill. Why do you disagree?

Walking trees on a whiteboard is a poor test of this ability. I'd much rather hear how somebody would decompose a real world problem into workable abstractions. A knack for designing clean architectures counts much more than algorithmic cleverness in 9 out of 10 actual programming jobs.

I hope it is not excessively elitist to think that programmers should aim to do both. Also, the two skills are not independent.

I honestly think they are to a large extent. Many architects are not mathematicians. And vice-versa.

Well, you'll be surprised how many candidates can't correctly write a function to reverse a single-linked list.

They're probably nervous because you've asked them to solve a weird problem they've never had to solve in the real world. Have you actually written, in shipping code, a single-linked list or an elementary algorithm to operate on one?

Unless you want them to implement a compiler or something, I think you'll learn a lot more about somebody's programming abilities by asking them to turn a list of use cases into a class diagram or write out a few SQL queries given for a given set of tables.

"A compiler or something" huh? Let's see. Would you hire someone who couldn't reverse a linked list, if you wanted to develop...

Google Chrome?

Adobe Photoshop?

Crysis 2?

An IPad?

A self-driving car?

Not all programming is boring business stuff with SQL and class diagrams. And even "boring" apps may be more tricky than they look: Microsoft Excel had its own bytecode interpreter, which definitely qualifies as "a compiler or something" :-)

>Have you actually written, in shipping code, a single-linked list or an elementary algorithm to operate on one?

Yes, I have. Admittedly, I had to do it much more often when STL was a toy.

But this is not the reason for this question, this is simple coding exercise, if a candidate can't do it without bugs in 10 minutes, there is nothing to talk about. Of course jobs not requiring writing C++, Java, C#, or Python code need different set of questions.

Great book! I enjoyed it as well.

It provides an excellent middle-ground. It's not as hard-core as Cormen's "Introduction to Algorithms", which might be a good thing for some people (like me). I find that for myself, I can retain more information when i have a real world application to attach it to and this book does a great job providing those.

This is a very good book. Worth the money. Skiena has a companion website with a lot of good info too, http://www.algorist.com/

I loved the Stones quote. The book does have some bugs, if something doesn't look right, check the website errata.

I read a different book to learn algorithms, 'Algorithm Design' by Kleinberg and Tardos, and I think its a fantastic book, with lots of sample material that actually makes you think. I actually may try this book to see how it compares.

+1 for Kleinberg-Tardos. I had already read Cormen before, and dabbled in TAOCP before I found Kleinberg-Tardos, and found it the most interesting (while remaining rigorous) of the three. I loved the structure of the book as well - focusing on real world problems and their algorithmic solutions, rather than a reference index of algos.

To be honest, I found Skiena's book a bit too introductory. I'm doing my preparation for interviews right now and I think I'm going to try to use TAOCP as my algorithms book. For the programming part I'm not sure if any book is going to help me. I tend to think that reading books rarely helps with programming -- only programming does.

The chapter on dynamic programming alone is worth the price of this book. Seriously, if you have trouble with DP, I can recommend no better way to learn it than going through Skiena's chapter on it. That catalogue of problems at the end is spectacularly thorough and useful too.

I own this book. Recommended. It's much gentler (not necessarily easier) than most algorithms books.

Doesn't seem to be available as an ebook, a strangely common problem for “hard” CS texts.

After you buy the hard copy (this is one of the books which I really think it is worth having the hard copy) you can have a look here: http://library.nu/docs/-----/The%20Algorithm%20Design%20Manu...

Skiena is an awesome professor too and teaches in SUNY StonyBrook but the sad part is he never teaches SB's algorithm course. Its an amazing book and recommend everyone interested in algorithms to read it.

He does teach the undergraduate algorithms course.

Weird, this is the second time I've stumbled upon some impressive SUNY professor. Doug Lea, who wrote dlmalloc (a very popular C malloc implementation) is a professor at SUNY Oswego. But I've heard absolutely nothing about their CS program aside from that they have these two professors.

I agree, I bought this book a while ago and it's been one of my best purchases so far. A really great resource.

Reply on news.ycombinator.com