Comment by kenjackson | Hacker News Reader

Comment by kenjackson | Hacker News Reader

Parent Full thread

While I agree with virtually of what you said, the following statement I do disagree with: You don't need a book; you need a project. (in reference to laerning algo and data structures).

There are too many non-trivial algorithms that you are just likely to not rediscover. Many are the result of some of the best minds in various fields over decades. Dynamic programming isn't something that will likely just show up in your code w/o knowing about it (it may, but probably among the more skilled). Balanced trees almost certainly won't. Heck, even standard binary trees probably aren't obvious to someone who hasn't thought about the problem.

And definitely not things like the Fast Fourier Transform or stability of Gaussian elimination, etc...

I'd at least recommend spending a weekend reading a pragmatic algorithms book like Sedgewick, http://algs4.cs.princeton.edu/home/Algs4Flyer.pdf.

Have a project that you're working on too, but don't do it without also learning algorithms and data structures more formally. Otherwise you'll end up finding a lot of poor solutions for problems that have known good solutions.

I'll second the recommendation for Sedgewick's book. The pictures in there are so good that you hardly even need the words, and I successfully learned algorithms from it.

The other algorithms book I would recommend is Steven Skiena's "Algorithm Design Manual", which has less depth than Sedgewick or Cormen et al., but is very well written and has a chapter that's a field guide to most algorithmic problems you commonly run into, and how to solve them. Looking through this algorithmic bestiary is well worth the time. The rest of the book is also good.

I have a smart co-worker who also likes Skiena's Algorithm Design Manual. I found that book to fluffy, though. But then I enjoy books like "Combinatorial Optimization - Polyhedra and Efficiency" by Alexander Schrijver.

(Not a beginner's book, but it has anything you ever wanted to know about P and NP.)

Yes I agree that there are algorithms that I would have never known about without hitting the books, I came across this recently. I was trying to solve one of ITA software hiring puzzles(Just for fun somebody mentioned it in SO) the "instant search" puzzle, I could never find a solution to the problem I spent days playing with it until I decided to give up, a few months later I found out about "Suffix trees" from wikipedia and found an implementation in Java, I'm still trying to understand about how it works but I used it in the ITA puzzle and the thing actually works and its freaking FAST!.

Was "not knowing" that algorithm preventing you from doing anything before you actually found it? If your goal is to learn for learning sake, then fine go buy some books and learn. If on the other hand, you are trying to build stuff, then by all means start building stuff and learn what you need along the way.

What if the goal is getting hired at ITA Software?

Any suggestions on a book describing algorithms useful for the ITA-style problems? I looked at those problems a while back (just out of curiosity, not to get a job) and realized that I didn't really know how to solve those optimization / approximate-solution-to-NP-complete problems. Is there an AI text, maybe, that would fill this gap in my knowledge?

There are too many non-trivial algorithms that you are just likely to not rediscover.

I agree, but would also (respectfully) ask, "So what?"

OP needs to learn to crawl, then walk, then run. And he seems like a great candidate to do all 3.

Even so, even if he works 30 years having a ball delivering great product to satisfied customers, he may never encounter "Fast Fourier Transform" or "stability of Gaussian elimination".

I think of "advanced" subjects like dynamic programming, functional programming, and even algorithms and low-level code like mountaineers think about Mount Fuji: A coward never climbs it. A fool climbs it more than once.

I haven't written a b-tree traversal in 10 years and hope I never do again. I'd rather stand on the shoulders of new giants and get other cool stuff done.

OP's not there yet. Give him time.

Also, he needs a reason to learn this stuff. "Because I need it for this project" is a better reason then "Because everybody else is doing it and I think I need to, too".

"Because I need it for this thing I'm doing" is the only motivation that ever works for me. That said, taking that weekend to read the book to know what might actually be available for that thing you're doing is also a good thing to do periodically.

Let me echo VivTech. You dont need to memorize all the algorithms and variants, but you do need to know what is there, so that sometime later when you need a solution, you know where to look. Also you need to dive deeply into some aspect such as sort or lists so that you get a good feel for big O notation and analysis. You may never implement a sort or tree algorithm, but is good to know which one to pick when you need it.

I've never had to use FFT, but sorts, trees, and graph traversal are pretty common.

My introduction to algorithms oh so many moons ago was Sedgewick when it was a single volume in C(?). I found it easy to read and use.

The problem is that there are a lot of projects you can go into as a cargo cult programmer, do an OK job, and come out more or less still a cargo cult programmer - you can build a pretty good web site by iterating on tutorials and copy-and-pasted snippets.

If you follow the guidance of, say, SICP, there're "projects" geared to expand your abilities.

So, I agree, but look for the right project - don't learn a framework, learn to do something.

>> There are too many non-trivial algorithms that you are just likely to not rediscover.

> I agree, but would also (respectfully) ask, "So what?"

Well, if you're trying to sort big arrays with bubblesort, you may have to wait a long time...

http://warp.povusers.org/grrr/bubblesort_eng.html

>Teaching bubble sort as some kind of "basic sorting algorithm" has real-life negative consequences. This is a real-life example: this is a piece of code in the gnu flex program:

    /* We sort the states in sns so we
     * can compare it to oldsns quickly.
     * We use bubble because there probably
     * aren't very many states.
     */
    bubble (sns, numstates);

>There's absolutely no rational reason why bubble sort was used here instead of insertion sort. Bubble sort can only be slower, and it's not in any way easier to implement.

Actually for small values of n, an n^2 sort can be quicker than an nlogn sort, depending on how it is implemented.

Yeah, hence insertion sort (the best n^2 sorter) is used to speed up quick-sort. It's insane to think of using bubble sort for the same task. (And for n=2, you don't need a sorting algorithm.)

I don't know about the OP or anyone else, but I've always found it easier to learn about a fundamental algorithm when I've got a real problem to use it on, in a real project that's in front of me. The problem isn't one of rediscovery, it's knowing that a solution exists in the first place.

http://en.wikipedia.org/wiki/List_of_algorithms

This site is probably has a more extensive list, but it seems to be down right now: http://www.itl.nist.gov/div897/sqg/dads/

Google's cache of it is only 2 days old, so it's probably temporary.

I would argue, both. Pick up a project you find interesting to drive the directions of your learning, and supplement it with book-learning as you go.

For instance, if you wanted to do some game programming for iOS/Android, pick up books that focus on algorithms appropriate to that context, not just a general book of algorithms.

That particular book is listed as being released on March 21 2011. Is there something I'm missing or are you recommending his earlier books on Algorithms in C?

Any of his algorithms books. I believe he has C, Java, and Pascal. But unless you need the book right now, I'd be inclined to wait a few weeks to get this latest edition.

Reply on news.ycombinator.com