Algorithms [pdf]

http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf

by sonabinu • 14 years ago

429 92 14 years ago

cs.berkeley.edu

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

BlackJack• 14 years ago

“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.

stephencanon2• 14 years ago

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

theshadow2• 14 years ago

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.

denzil_correa5• 14 years ago

> 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.

dlo• 14 years ago

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!

wallflower• 14 years ago

We also really like Steven Skiena's lecture vault.

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

Permit2• 14 years ago

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.

kitsune_• 14 years ago

I really enjoyed Skiena's book.

sravfeyn• 14 years ago

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?

andreasvc• 14 years ago

Tried www.abebooks.com ?

sunilnimmagadda• 14 years ago

Available on flipkart for 356 INR

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

sonabinu3• 14 years ago

Check out www.betterworldbooks.com Shipping is free

danso2• 14 years ago

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?)

mikedmiked• 14 years ago

> why scribd?

Scribd went through Y combinator.

theorique• 14 years ago

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

TeMPOraL• 14 years ago

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

danso2• 14 years ago

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.

mdpye• 14 years ago

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...

nkurz• 14 years ago

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?

glesica• 14 years ago

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

_delirium• 14 years ago

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.

krickle• 14 years ago

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

Permit2• 14 years ago

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.

theshadow2• 14 years ago

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.

jasim7• 14 years ago

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.

jlarocco2• 14 years ago

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.

kmfrk• 14 years ago

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

pretz• 14 years ago

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...

indy• 14 years ago

Are the answers to the exercises available?

krzyk• 14 years ago

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?

Jabbles• 14 years ago

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 :)

Me1000• 14 years ago

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.

sonabinu3• 14 years ago

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

jsolson3• 14 years ago

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.

khwang• 14 years ago

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!)

joshAg• 14 years ago

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.

jasim7• 14 years ago

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.

ibuildthings• 14 years ago

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.

jasim7• 14 years ago

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.

ghubbard• 14 years ago

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

quanticle• 14 years ago

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.

tptacek• 14 years ago

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

oggy• 14 years ago

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.

tmoertel• 14 years ago

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.

super_mario• 14 years ago

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

syaramak• 14 years ago

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.

mikevm• 14 years ago

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...

jasim7• 14 years ago

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.

vph2• 14 years ago

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.

jasim7• 14 years ago

+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.

mamcx• 14 years ago

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

vph2• 14 years ago

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.

cotsog• 14 years ago

Web page with links to individual chapters:

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

napolux• 14 years ago

Can you suggest me a free text on genetics algorithms?

sonabinu3• 14 years ago

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

jjhageman• 14 years ago

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

me2i81• 14 years ago

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

walrus• 14 years ago

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.

mitchi• 14 years ago

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

macstr1k3r2• 14 years ago

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.

jasim7• 14 years ago

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.

macstr1k3r2• 14 years ago

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

ginko• 14 years ago

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.

ahelwer• 14 years ago

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

eshvk• 14 years ago

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.

intellegacy3• 14 years ago

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?

jasim7• 14 years ago

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.

intellegacy3• 14 years ago

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.

maaku2• 14 years ago

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.

intellegacy3• 14 years ago

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)?

ableal• 14 years ago

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.

ReshNesh2• 14 years ago

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

jlarocco2• 14 years ago

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.

ReshNesh2• 14 years ago

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

almost2• 14 years ago

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...

almost2• 14 years ago

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...

33a• 14 years ago

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?

peterhajas• 14 years ago

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

vitalique• 14 years ago

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

mepcotterell• 14 years ago

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

Algorithms [pdf]

Related Stories