What book to use to learn Algorithms and Data Structures ?

views:

303

answers:

+8 Q:

What book to use to learn Algorithms and Data Structures ?

I want to learn Algorithms and become fluent in them. My goal is to land a job as a Software Development Engineer at either Google or Microsoft. I've been recommended to use the book "Introduction to Algorithms" by Cormen.

But I feel like the book is not for beginners.

Can anyone recommend a book on Algoritms that I can find easier ? one that after reading can help me read and understand Intro to Alg. ?

+6 A:

The book by Dasgupta, Papadimitriou, and Vazirani is pretty good, and much more approachable than Cormen et al. I don't know how the online pre-print compares with the published edition, since I've only read it on paper.

Novelocrat 2010-07-06 03:06:04

i think this book is indeed more approachable. thanks Novelocrat. !

Attilah 2010-07-06 04:01:01

Read this from cover-to-cover; great book (and free!), but the last three chapters are difficult - chapter 8 contains some faulty proofs, and chapter 10 is so *completely* incomprehensible that I get the strong impression the authors themselves don't actually understand it

BlueRaja - Danny Pflughoeft 2010-07-06 18:57:05

@BlueRaja - Danny Pflughoeft: Uh, Umesh Vazirani is one of the pioneers in Quantum computation/complexity; I'm sure they understand it perfectly well. I skimmed through it and it looks fine compared to other usual presentations of quantum computation; what's wrong with it? [Except the part that discusses physics, but you're supposed to ignore that and focus on the computation :p]

ShreevatsaR 2010-07-06 20:16:46

@ShreevatsaR: Then this must be a case of (the *extremely* common occurrence of) the expert being unable to teach his subject to others. Despite a strong background in mathematics and computer science, and a moderate background in quantum mechanics, I am completely unable to comprehend that chapter. If I can't understand it with my background, what chance does the beginner have? *(Is chapter 10 the only chapter Vazirani wrote? Because the others are really good)*

BlueRaja - Danny Pflughoeft 2010-07-06 20:35:32

@BlueRaja - Danny Pflughoeft: I suspect your background in quantum mechanics is interfering. I have none, and I just read the chapter (thanks!) and found it quite clear. Of course, I wasn't trying to understand the physics (nor were they trying to explain), but took it as axiomatic that the state is a linear combination, that making measurements changes the system in the way described, that certain "gates" are elementary operations, etc. (In fact that's what I liked here, that they cut down on the physics distraction… I'd have liked *even* fewer mentions of Nature.) I finally get Shor's algo!

ShreevatsaR 2010-07-06 22:00:13

Note: I skipped 10.5.3, which they say you can safely skip -- but I tried reading it and it *is* fairly confusing unlike the rest of the chapter, since they start talking of "phases" without ever having defined them before. Also, on p. 325, it took me some time to figure out that "two quantum registers, both initially 0" meant a superposition with 1 on |0,0> and 0's on the rest. Apart from that, it was fine. Presumably they improved the clarity in the print version... anyway, quantum computation can be confusing because its primitives are not like those of any 'computer' we know.

ShreevatsaR 2010-07-06 22:01:44

+4 A:

Some suggestions, of other well-known books:

Algorithm Design by Jon Kleinberg and Éva Tardos
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (draft version available online!)
The Algorithm Design Manual by Steven Skiena

I think all of these may be more accessible (at least in terms of sheer volume per content!) than the CLRS book (Cormen et al). CLRS is a book for beginners in some sense (it's used as an introductory programming textbook in several universities for students fresh out of high school), but because of having more detail and proofs than necessary (IMHO), it has too many pages, and it's easy to get lost in the detail.

Whichever book you pick, it's not a trivial subject, so you have to put in some effort, but it's pretty easy and fun once you get the ideas right. Good luck!

ShreevatsaR 2010-07-06 03:06:31

it requires some mathematical notations that are somehow driving me off. because I don't have a strong mathematical background.

Attilah 2010-07-06 03:35:40

Then I recommend Skiena's book or the other two... they are less proof-oriented, and require less mathematical sophistication, but are still just as strong on the algorithmic ideas.

ShreevatsaR 2010-07-06 03:44:31

thanks. I've narrowed the choices down to "The Algorithm Design Manual" and "Algorithms" by Dasgupta. I'll see which one I can read faster and gain a little fluency in the subject.

Attilah 2010-07-06 04:03:21

If you're struggling with the mathematics, you might want to work on these areas too. It would help to be familiar with proof by induction, permutations and combinations, sums and series, etc... These are not only necessary to understand analysis of algorithms, but they're also good training to for your brain to think into algorithms.

Kena 2010-07-06 15:12:27

For a good grounding in the mathematics of algorithms, you might look at Ed Scheinerman's book [Mathematics: A Discrete Introduction](http://www.ams.jhu.edu/~ers/mdi/) or Graham, Knuth, and Patashnik's [Concrete Mathematics](http://www-cs-faculty.stanford.edu/~uno/gkp.html).

Novelocrat 2010-07-06 18:23:28

+2 A:

If you feel "Introduction to Algorithms" is a bit hard, there is this course Introduction to Algorithms with videos on OCW.

Also, there is this course named Programming Abstraction from Stanford (also with videos) that focuses less on theoretical aspects.

Po 2010-07-06 03:14:48

+2 A:

While I have no direct knowledge of what it takes to get hired at Google/M$, I can tell you that when my students do go and get jobs there, they've also been able to crack interview questions that required if not math skills, but solid foundations in things like dynamic programming, network flows and the like. so whichever book you use, makes sure you understand the concepts. From that perspective, the Kleinberg/Tardos book,w hich ordinarily would be considered an advanced book, does a good job of explaining "how to think about ", and that's why I use it in my classes.

Suresh 2010-07-06 05:19:47

The Tomes of Delphi: Algorithms and Data Structures by Julian Bucknall.

www.lulu.com/content/435417

Marjan Venema 2010-07-06 06:54:12

Lulu is doing maintenance. The book on amazon: http://www.amazon.com/Julian-Bucknall/e/B001K8RGZS

Marjan Venema 2010-07-06 06:54:34

ansaurus

tags:

views:

answers:

What book to use to learn Algorithms and Data Structures ?

related questions