In part of James’ summary of Making Change (#154) on rubyquiz he
states:
"This problem actually turns out to be famous in computer science.
It’s called the Knapsack Problem. Once you know that you can apply the
techniques often used on that problem, the most popular of which is to
use a dynamic programming algorithm. "
My questions are:
Is there a definitive book/web site/resource on this and other
computer science ‘problems’? (Whether Ruby, C, C++, Java, Perl based).
Do people have favorite ‘Data Structure and Algorithm’ books?
Other Computer Science book recommendations?
I’d love to get to a point where I could look at the quiz description
and say “oh… that looks like the XXX problem” like some of you are
able to do. I attempted this quiz and had a solution along the lines
of Ilan B.'s non-complicated solution, but would never had known it
was a ‘famous computer science problem’.
Do people have favorite ‘Data Structure and Algorithm’ books?
A good, standard textbook in use today is Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, and Cliff Stein Introduction to
Algorithms
2nd Ed. MIT Press
Donald Knuth, The Art of Computer Programming is like the bible for
computer scientists.
Is there a definitive book/web site/resource on this and other
computer science ‘problems’? (Whether Ruby, C, C++, Java, Perl based).
Do people have favorite ‘Data Structure and Algorithm’ books?
Other Computer Science book recommendations?
I don’t think there’s any one book. The subject is too broad. However, I
learned a lot from Bentley’s Programming_Pearls and from The_Pragmatic_Programmer by our own Dave T. and Andy H…
You could do a lot worse than these two classics. Find them at your
favorite online bookseller.
In general, it’s a poor book to learn algorithms from. For example, I
was never able to comprehend its descriptions of dynamic programming
or simulated annealing.
However, the back half of the book is a reference guide to many famous
computer problems and it’s really great. It describes common
variations of the problem and how you might run into it. It also
covers common ways to attack it, usually giving more than one
approach. This is great for finding a famous problem.
I have yet to run into the perfect book to learn algorithms and data
structures from. I’ve had to use many, many sources. I really feel
like their should be a good algorithms book out there, but I just
haven’t found it yet.
A Ruby algorithms book would be really nice to have. (I have a Perl
book like that I’ve used a fair bit.)
But be warned, it’s as dry as you would expect a computer science
reference book to be.
Dry? Heretic! What is not to love about Mix assembler?
Assembler. Thanks for making my point.
James Edward G. II
Actually, it isn’t often straightforward to adapt the code in Knuth’s
book to an object-oriented language. I found this out during quiz #150 (AVL Tree Ping-Pong). The algorithms are very much down in the
pointer/stack details of making an algorithm… but it’s all the math
you’ll EVER want.
A good, standard textbook in use today is Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, and Cliff Stein Introduction to
Algorithms
2nd Ed. MIT Press
Cormen is my CS Professor!
-------------------------------------------------------|
~ Ari
seydar: it’s like a crazy love triangle of Kernel commands and C code
A good, standard textbook in use today is Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, and Cliff Stein Introduction to Algorithms
2nd Ed. MIT Press
I’ve been wanting to buy this one cheap on eBay, but most of them are
sold only by Indian people and they charge a ton for shipping.
On Wed, 06 Feb 2008 15:27:10 +1100, Clifford H. wrote:
Lots of good suggestions for algorithms books to answer your 2 & 3, but
note that I think I’m the only one who’s attempted to answer your first
question, and to point you to a list of the “known hard problems”, which
was also the subject of your last paragraph.
Does anyone else have better answers to question 1, which seems to be
Mark’s main question?
I’ll post again:
Dismissed site: www.nada.kth.se is probably as close as you
come to a full compendium of NP-Hard optimization problems, and their
approximation algorithms, etc
"This problem actually turns out to be famous in computer science.
It’s called the Knapsack Problem.
My questions are:
Is there a definitive book/web site/resource on this and other
computer science ‘problems’? (Whether Ruby, C, C++, Java, Perl based).
Do people have favorite ‘Data Structure and Algorithm’ books?
Other Computer Science book recommendations?
I’d love to get to a point where I could look at the quiz description
and say “oh… that looks like the XXX problem” like some of you are
able to do.
Lots of good suggestions for algorithms books to answer your 2 & 3, but
note that I think I’m the only one who’s attempted to answer your first
question, and to point you to a list of the “known hard problems”, which
was also the subject of your last paragraph.
Does anyone else have better answers to question 1, which seems to be
Mark’s main question?
Lots of good suggestions for algorithms books to answer your 2 & 3, but
note that I think I’m the only one who’s attempted to answer your first
question, and to point you to a list of the “known hard problems”, which
was also the subject of your last paragraph.
Does anyone else have better answers to question 1, which seems to be
Mark’s main question?
was my main focus, but I am really appreciating answers to 2. and
as well. So keep them coming
Thanks for the wikipedia link. It’s definitely a keeper. The book
James ‘has on his shelf’ lead me to this:
The Stony Brook Algorithm Repository
(http://www.cs.sunysb.edu/~algorith/)
which is also bookmarked!
I reckon I may buy the ‘Algorithm design manual’ based on James’
description of the second half (even though the best i can find is
$140 here in Oz!!). Am also looking into Sedgewicks set (or the Corman
book).
This (http://www.bioalgorithms.info/book/excerpt-ch6.pdf) was also a
VERY good find! Seems like a very ‘easy read’ algorithm book.
I’ll have to apply “The Change Problem Revisited” to Making Change
(#154) (if I can!)
Is there a definitive book/web site/resource on this and other
computer science ‘problems’? (Whether Ruby, C, C++, Java, Perl based).
Do people have favorite ‘Data Structure and Algorithm’ books?
Other Computer Science book recommendations?
Not a good first, or even second book, but Papadimitriou’s
“Combinatorial optimization: algorithms and complexity” is an
excellent book to work your way up to.
This (http://www.bioalgorithms.info/book/excerpt-ch6.pdf) was also a
VERY good find! Seems like a very ‘easy read’ algorithm book.
I’ll have to apply “The Change Problem Revisited” to Making Change
(#154) (if I can!)
This does look like a good find. Thanks for sharing!
like the XXX problem" like some of you are able to do.
Show quoted text -
Actually, I meant to acknowledge you Ken in my previous reply to
Clifford. I found the book excerpt halfway through writing the reply
so got sidetracked. Sorry about that
