Algorithms [pdf] | Hacker News Reader

Algorithms [pdf]

cs.berkeley.edu

429 pointssonabinu92 comments

I'd tried studying from both CLRS and this text (S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani) some years back.

I had a visceral reaction against CLRS when I saw the standard pseudo-code the book uses. But as I tried implementing some algorithms in C, I found that the algorithms were so precise and detailed that there was no better way to represent it (apart from giving the C code directly).

I've heard claims that CLRS' pseudo-code could be presented in a higher level manner - but it defeats the purpose of an Algorithms text. Algorithms should be correct, fast and consume the least memory possible - this requires you to think about low level memory management, cost of comparisons etc.

However, the density and detail of CLRS forced me to look for other books which presents the topic in a better manner. Vazirani is an excellent choice in this regard. The language is clear and easy to understand, and it gives a better high-level picture than CLRS. I remember reading Chain Matrix Multiplication (page 184, 6.5) in Vazirani and being overwhelmed by the simplicity of the presentation compared to the dry formalisms used in CLRS.

From my experience, I recommend using CLRS as an aid for rigorous study and Vazirani for less rigorous, but very effective learning. Also take a look at Sedgewick's Algorithms in Java series - http://www.cs.princeton.edu/~rs/ (he has C and C++ series, but Java is what I've used). It is more detailed than Vazirani but at the same time more approachable than CLRS.

Though I agree to most of what you said, for learning algorithms you need not think about low level memory management.

I had used CLRS many times to explain algorithms to non-CS students and collaborators ( who almost always preferred dynamically typed scripting languages like python and to be honest were scared of ints and floats ). At the same-time some of them were very good in algorithm design, and came up with clever (algorithmic) ways to solve the problem at hand much more efficiently.

I had this experience when I was studying about Red-Black Trees. These are data structures made to make data access efficient. I'd argue that in such cases, it is important to limit the number of memory swaps and comparisons you make to keep the algorithm efficient.

But your argument does hold true when one is dealing with things like sorting or graph traversal algorithms. There the concepts are most important and you can do well without worrying about the low level details.

For those who don't know: "CLRS" is "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. http://en.wikipedia.org/wiki/Introduction_to_Algorithms

Another good algorithms text is Skiena's Algorithm Design Manual. It's not as rigorous as CLRS (it doesn't spend as much time on proving correctness mathematically), but as an implementer of algorithms, I find Skiena to be more useful on a day-to-day basis than CLRS. Skiena talks about caveats and pitfalls that come up when attempting to implement the algorithm on real hardware (e.g. cache-locality issues, high constant factors, etc.) that CLRS skims over.

Another vote for Skiena; CLRS for reference, Skiena for how to think about solving problems with algorithms.

For me, Skiena had the added bonus of being an enjoyable read which isn't always the case for algorithm books. I highly recommend it.

Another excellent algorithms book that never seems to get any attention is Udi Manber's "Introduction to Algorithms: A Creative Approach". Unlike the standard "algorithm catalog" books, where the standard algorithms are merely presented, it really gives you an idea of how one could come up with them in the first place, focusing on arguments by mathematical induction which then naturally translate into recursion/iteration. It's really invaluable for being able to come up with your own algorithms, when a non-standard problem hits you.

The slight downside is that sometimes the given algorithms are not quite as worked out in detail as in some other textbooks. Yet it's probably the algorithms book that has taught me the most.

I came here to make exactly the same recommendation about Udi Manber's book.

When designing an algorithm, you ought to make sure that it actually works. At some point, then, you're going to have to prove it. Which for most people is hard, in part because most algorithms books present the proofs as a fait accompli. They just show up, fully formed.

But Manber argues, and demonstrates convincingly in his book, that the design and the proof both become easier if you do them together. The design guides the proof, the proof the design.

He's right. Since reading the book, I don't do it any other way.

The book, tragically, costs about $110. But if you care about this stuff, it's worth it.

The pseudo language used in CLRS has been updated and made a little more readable in 3rd edition.

Yet another good book is Algorithm Design by Jon Kleinberg, Éva Tardos. What I like most about this book is that it contains tons of interesting, real-world examples and exercises that make the theory so much more fun.

Are you kidding me? The Vazirani/Dasgupta book is a joke compared to CLRS.

I learned algorithms from CLRS (as most students have), and it is bar-none, the best data structures/algorithms book on the market. The explanations are clear, detailed and rigorous.

The Vazirani/Dasgupta book does not go into as much detail. You don't believe me that this book is bad? Read some of the Amazon reviews: http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/product-rev...

I don't see where we are disagreeing here - Vazirani/Dasgupta is not as detailed/rigorous as CLRS and that is precisely the point. The detail of CLRS comes at the cost of readability.

I'm not denying that I enjoyed learning from CLRS - but I recollect having to take more effort to parse its detailed pseudo-code than what a higher level of abstraction would've taken.

This is where a book with less detail like Vazirani can help. I would never recommend relying on a single text for studying anything - least of all Algorithms. Each of these complement the others in a nice way and being able to look at the same concept from the perspective of different authors always help.

> The Vazirani/Dasgupta book does not go into as much detail. You don't believe me that this book is bad? Read some of the Amazon reviews: http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/product-rev....

You've pointed to the 3 one-star reviews instead of the 17 five-star reviews of the book. Was that a mistake? Joking aside, those reviews seem to be from people who've tried to use Vazirani as their sole Algorithms text. Having seen CLRS first, I've always approached Vazirani as a complement to CLRS and that worked.

So... who's read it? sonabinu? Have you actually used this book enough to recommend it?

The fact that it's freely available online doesn't make it worth reading. If someone is actually recommending it, I'd like to know why they prefer this over, say "The Algorithm Design Manual". Just posting a link tells me nothing. I hope the people that say they're going to try reading this can give a detailed review in a few weeks' time - or even a few hours' - I'd be much more content diving into a chapter of this if I knew someone else thought it worthwhile.

Edit: I see jasim has read it :)

This book was used for my algorithms class last year. I never buy textbooks because I never really find them useful (especially CS books). This book, however, I thought did a great job of explaining how things work and was a pretty easy read. I even found myself reading ahead and reading content we didn't cover in class.

If algorithms are interesting to you, I certainly wouldn't turn you away from it.

I am doing my MS in Software Engineering and currently reading it.

This book was used for an algorithms class for which I was the TA. My experience suggests that students who lack sufficient grounding in discrete math will have trouble with some concepts as the book speeds past them without giving any supplementary explanation.

That said, if I were teaching algorithms in a classroom setting I'd probably still use this book and supplement it with lectures where it falls short on deep details.

If you're looking for a book to pick up on your own it all depends on your math background. You might find yourself using Google frequently to clarify things, or you might be just fine.

I took a class that used this book at Berkeley. I think it's kind of like a wikipedia article in a book--it's clear and easy to read (well, easier than most other textbooks!)

I took the course with papdomitrou (one of the authors), and he didn't supplement the book at all (his lectures were literally just the book in spoken word form, down to the jokes). I really liked the book and lecture, though, since I thought it did a great job explaining the material at a good level for an intro algorithms course high enough that you aren't bogged down in formalism and esoteric math, but deep enough that you still understand the algorithms well enough to recognize where to apply them in the real world.

I had the pleasure of taking the class based around this book from Christos Papadimitriou while at UC Berkeley. It is indeed a concise and excellent book. If you see it in person you'll be surprised how short it is compared to most textbooks. I must confess, though, that some of the exercises can be absolutely maddening.

Dead tree link for those interested: http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/00735234...

Yes, this is one of the best algorithms textbooks due to a few reasons:

* It emphasizes rigor without much formalism.

* Rich number of non-trivial exercises.

* Conciseness of description of algorithms and strategies.

If you look for a textbook with algorithms translatable to C/C++/Java codes line by line, this is not one of them.

+1. CLRS is best for algorithms that are directly translatable to code. IIRC, Sedgewick doesn't use pseudo-code and instead uses Java code in his Java series.

Any suggestion for the topic, more entry level for people that can't read math notation (ie newbies?), perhaps in python?

I don't have a good recommendation for your needs. However, there are a few books that might be close:

1. Programming Pearls by Jon Benley. 2. Programming Challenges by Steven Skiena. 3. Algorithmic puzzles by Levitin.

The first two are mostly programming focus. I have not read the 3rd book, but I have a good idea what it is about (based on other books by Levitin); it should be good.

Since algorithms are always a hot topic here at HN, I'd like to point out to those interested two online courses that are going to start at Coursera soon, both are continuations to previous courses and both are starting in about two weeks (come December): 'Algorithms, Part II' - by Robert Sedgewick & Kevin Wayne of Princeton themselves [1], and 'Algorithms: Design and Analysis, Part 2' - by Tim Roughgarden of Stanford [2]. Online courses tend to be by far not as rigorous as books are, but I took first part of Prof. Roughgarden's course and it was very enjoyable on all sides.

[1] https://www.coursera.org/course/algs4partII [2] https://www.coursera.org/course/algo2

We also really like Steven Skiena's lecture vault.

http://www.cs.sunysb.edu/~algorith/video-lectures/

He's also got a really great set of videos on Computational Finance. I haven't seen the Discrete Mathematics or Computational Biology videos, but I imagine he does a good job there as well.

I believe all of these videos are also available on his YouTube channel by the way.

I really enjoyed Skiena's book.

A bit off topic, but can anyone recommend a Data Structures book (as a precursor to Algorithms?)

Or am I incorrect in thinking the two are discrete concepts unable to be separated?

A data structure deals with the way you store data. A singly linked list for example is a data structure. All you need to understand about it is that every node except the terminal ones points to one other node. The traversal of this structure can be called an algorithm, albeit a simple one.

Manipulation of the linked list often requires a traversal. Also, inserting data between nodes also require a little juggling of the node pointers. These are all what you can call 'algorithms'. Data structures can exist and be learnt somewhat independently of their underlying algorithms, but it is rarely useful like that.

There are however pure algorithms that do not care much about the underlying data structure - insertion sort is an example. Most data structures though aren't very much useful when separated from their fundamental algorithms.

Hope that answers your question.

Thanks. My confusion stemmed from not actually taking Data Structures yet, along with the fact that some colleges call their second course 'Algorithms', while including a junior-senior year 'Algorithms' course as well.

It's hard to understand the how (data structure) without the why (algorithms).

I found Sedgewick's Algorithms to have quite good coverage of data structures, however.

Thank you. I've seen that book actually, as Professor Sedgewick has a Coursera Algorithms course. Would you say it's appropriate for a second course (following Intro to CS)?

It's appropriate for anyone that knows the basics of programming.

I believe I once had a short book by CMU's Daniel Sleator and a co-author where they explained some examples showing how different data structures could change the complexity/run-time of algorithms.

Can't find either my copy or online references.

I never noticed this until now: how does the scribd script work on HN? Does it automatically suck in the PDF after it's been posted? I didn't realize that clicking on [scribd] takes you to an actual scribd page (I just thought it was the convention that people used to indicate that the link goes to a PDF).

Also, why scribd? (API I'm guessing?)

> why scribd?

Scribd went through Y combinator.

Looks like just a direct link to the UC Berkeley site - no scribd at all.

The [scribd] part of the title is the link to scribd.

Yeah sorry, should've been clearer. The [scribd] bit is actually its own link, which I found out by accidentally clicking on it instead of the rest of the link title.

It works like this: http://www.scribd.com/vacuum?url=http://www.cs.berkeley.edu/...

By which I mean, it just appends the posted URL as a scribd url parameter, it doesn't actually "scribe" it...

What does "scribe" mean in this context?

When I click on the link, it redirects me to http://www.scribd.com/doc/969071/All#full. At a glance, view-source appears to grab each page from http://scribdassets.com. I think Scribd is clearly serving the material from their own site. Is there a different mode for cases where they have permission from the copyright owner?

I don't understand why you would ever want to ruin a perfectly good PDF by letting Scribd anywhere near it...

I used to like being able to read PDFs in the browser, which Scribd let you do, but now the browsers I use (Chrome and Safari) both have in-browser PDF reading that seems to work more smoothly than Scribd for me, so I've switched to the opposite preference. I do occasionally click on it for PDFs that I expect to be large (such as this one) where I just want to skim a few pages without downloading the whole thing.

I always vote up posters that de-scribd pdfs in the comments.

I would also recommend Jeff Erickson's (UIUC) book on algorithms freely available here ( http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/ ). It is very well written challenging material.

Web page with links to individual chapters:

http://www.cs.berkeley.edu/~vazirani/algorithms.html

Seems to cover less than CLRS. I find that most algorithm books cover the same general (beginner to intermediate) set of topics as CLRS does. I was hoping to find something that goes beyond the stuff covered in CLRS but not as far as the level of TAOCP. Any recommendations will be appreciated.

It'd depend on what you're looking for. Sedgewick covers some areas better than either CLRS or Vazirani. For example, I remember relying on Sedgewick for B-Tree since neither text covered them. Sedgewick also has an entire text for Graphs, so I presume he goes into lot more detail than others can.

If you are considering coding competitions like TopCoder, you should look at Skiena's Algorithm Design Manual. It covers a lot of ground that is not covered by CLRS or the like.

But I think between Skiena, Sedgewick, CLRS, Vazirani and TAOCP, you have fundamental algorithms and data structures covered. If you are looking to go into detail on specialized topics like say AI, these texts wont help much.

To be honest, I think there's only so many generic algorithms around.

If you've read a book or two on the basics, your best bet is to look for books on a specific topics, like computational geometry, evolutionary algorithms, or parallel algorithms.

Looked at the title and thought 'better than Vazirani!?'. Found it out to be Vazirani. It's an incredible book. I was (still am) looking for a print Indian Edition of the book. Is there anyone who can sell it off in India :), second-hand?

Tried www.abebooks.com ?

Available on flipkart for 356 INR

http://www.flipkart.com/algorithms-0070636613/p/itmczynvb7p2...

Check out www.betterworldbooks.com Shipping is free

Looks like it handles all important topics for sequential algorithms quite well. It even discusses quantum algorithms in the last chapter.

What I really could need though is a reference book for parallel algorithms. Especially shared memory PRAM algorithms for OpenCL, OpenMP & co. Most current books only assign a chapter at most to this. I guess the main problem here is that parallel algorithms are still very much in their infancy compared to their sequential counterparts.

The use cases are much different. Once you get outside of the standard parallel sort/scan/reduce/map functions you can find in Thrust[1], you get into algorithms that have an entire enormous book[2] explaining the idea behind them.

That gap is closing slowly as a lot of old algorithms are being remixed into highly parallel versions. This is noticeable in string pattern matching applications, driven by the need to analyze tons of DNA.

More people would benefit from knowing how exactly to code efficiently on the GPU before jumping right in to writing algorithms on it; it's easy to lose multiples of throughput if you don't know what you're doing. As always it's becoming easier for programmers though; if you're new to the idea of GPU programming I really recommend checking out Microsoft's C++ AMP[3], which shipped with VS 2012. Removes a lot of the headaches of programming with CUDA and OpenCL. I've had a chance to play around with it, and it's excellent.

[1] http://thrust.github.com/

[2] http://books.google.ca/books/about/Computational_Electrodyna...

[3] http://msdn.microsoft.com/en-us/library/hh265137.aspx

Just bought this on Amazon, looks great but I still prefer dead trees for tech books. Awesome that they've released it for free online though, very cool!

Amazon Link (no affiliate): http://www.amazon.com/gp/aw/d/0073523402/ref=mp_s_a_2?pi=SL7...

Whoops, seems I posted the mobile link, here's the desktop site link: http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/00735234...

And here's the uk one: http://www.amazon.co.uk/Algorithms-Sanjoy-Dasgupta/dp/007352...

I'm planning on starting this book any day now. I've already skimmed through the pages and have came to the conclusion that the lack of code(not pseudo code) will be a problem for me.

So the question to those who have already read this is: Is there a blog or a site or something of that sort that has covered this book and posted code samples or something like that.

I think that it pays to implement the code yourself. Even though you think you understand a concept, you haven't tested it till you write the code. IMO, there is no better way to learn algorithms than implementing, tweaking, profiling and trying to visualize them.

I need some basic examples smething in the order of "tips on implementing algorithms"

Are the answers to the exercises available?

Exactly, without answers (or an instructor) exercises are pointless. It really makes me mad when I see a book that doesn't give also the answers, how should I know that I did the exercise correctly?

From the table of contents, it just looks like the standard stuff you'd see in an undergraduate class (with an odd-ball bonus section on quantum computing). What makes this better than standard texts like CLRS that cover the same subject matter, and in more detail?

Interesting, a chapter on quantum algorithms. I've often wondered whether there might be room for novel research in this field if quantum computing became more practical.

I'll definitely give this chapter a read. Thanks for posting it.

This was the book I used for my Algorithms class, along with CLRS. I much (much!) preferred this one for its brevity and clarity.

I like the pseudocode, but it's a bit distracting that some of it is italicized, though.

Looks interesting. Is it possible to get a PDF without signing up to scribd? Thanks

Already done. The title has two links.

The first part goes here to the PDF directly: http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf

The second part, "[scribd]", goes to scribd.

Oh, thanks for that. I didn't notice and obviously clicked the wrong link...

TFS. I plan to read this cover-to-cover in the next 10 days

“Some books are to be tasted, others to be swallowed, and some few to be chewed and digested: that is, some books are to be read only in parts, others to be read, but not curiously, and some few to be read wholly, and with diligence and attention.” - Francis Bacon.

This one should be chewed and digested. It's not a race - work slowly and diligently, and start exploring the boundaries of the topics covered, and you'll get much more out of it.

Yes; reading the book cover-to-cover in ten days sounds like a fantastic way to waste ten days learning nothing.

> Yes; reading the book cover-to-cover in ten days sounds like a fantastic way to waste ten days learning nothing.

Depends on the book and who is reading it. The OP is pursuing PhD and has computing background http://news.ycombinator.com/item?id=4783710

This text is covering selected undergrad topics barring the chapter on quantum algorithms(I am not sure what it is).

The chapter on quantum algorithms covers them at a level suitable for an undergraduate course (it's certainly covered in the undergrad courses at Berkeley, and hews pretty close to what we covered at Brown when I was an undergrad as well).

It's possible that he/she is already familiar with the material but is reading it as review, in which case 10 days sounds more than reasonable.

True. As tsahyt puts it,

> it's always good to review things one has already learned. For me this usually leads to insights I haven't had before and a deeper understanding. Learnings seems to be an iterative process.

This is my primary motivation.

> This one should be chewed and digested. It's not a race - work slowly and diligently, and start exploring the boundaries of the topics covered, and you'll get much more out of it.

Thanks for the advice. Just in case, I am a Masters in CS and currently into my PhD.

There's probably not much new for you then. Pretty much everything in this book is covered in my Master Curriculum at least. The chapter on Quantum Algorithms looks interesting though. Quantum Computing is a bit of a mystery to me anyways.

However, it's always good to review things one has already learned. For me this usually leads to insights I haven't had before and a deeper understanding. Learnings seems to be an iterative process.

I just want to review stuff. It never hurts to go back to the basics and refresh things. I like to have a solid base on Data Structures, Algorithms and Probability. I even sign up for under graduate online courses if and when possible. Udacity makes my job quite simple.

Commented on this above, but the best favor I ever did myself in terms of online learning was to watch Gilbert Strang's (MIT) linear algebra lectures from iTunes U.

Thanks. They are on my radar as well - downloading them right away.

I'd agree that basically all of the material in this text is covered in an undergraduate and master's CS curriculum, but that doesn't mean you won't learn anything by going through it.

For example, I wouldn't say I really understood linear algebra until I went back and watched Gilbert Strang's lectures on iTunes U after my MS[0]. Which is, of course, somewhat awkward, as I encountered many problems which required using it during my studies, but the only course I had on it was my freshmen Calc II class.

Basically I'd made it through years of schooling being able to make use of a tool without actually understanding the tool. If you'd asked me to solve any problem that required insight into LA rather than just application of common mechanical primitives, I probably did quite poorly.

[0]: These lectures are fantastic by the way; they served as a good jumping off point for a bunch of other post-education math study for me.

Gilbert Strang's lectures are indeed very good. I've got a textbook on Linear Algebra written by him as well which is very good too.

As I said, reviewing material will probably lead to insights you haven't had before. If you've got spare time it's always a good idea to read a book on a topic like algorithms or a math book in order to get a deeper understanding, even if the book is just repeating things you already learned.

Wow, that's ambitious, but I never put it past a Ph.D. to do something like this. Let us know if you actually succeed!

Can you suggest me a free text on genetics algorithms?

You could try Applied Genetic programming and machine learning. I think it is available online in pdf format.

You might want to check out http://www.cleveralgorithms.com/. There is a link to a free pdf version of the book.

http://www.gp-field-guide.org.uk/

http://cs.gmu.edu/~sean/book/metaheuristics/ is good. Genetic algorithms fall in a class of algorithms called metaheuristics. This book is about metaheuristics.

If you're just interested in genetic algorithms, those are covered in chapter 3.

Genetic algorithms are pretty easy. a wikipedia read should suffice.

f(n) = O(g(n)) irritates me, but I know that people like to express Big-O that way for convenience.

Reply on news.ycombinator.com