Is there a definitive book/web site/resource on this and other
Start by looking at know University sites – you’ll often come across some.
).
Do people have favorite ‘Data Structure and Algorithm’ books?
Robert Sedgewick’s books are great, if not a little heavy-going:
I can recommend them as well - although I still wait for Algorithms in
C++ Parts 6-8. Publishing date has been postponed a few times. He
seems to be too busy.
On Wed, Feb 06, 2008 at 10:47:51AM +0900, James G. wrote:
A Ruby algorithms book would be really nice to have. (I have a Perl
book like that I’ve used a fair bit.)
I’d love to find a Ruby algorithms book, myself.
re: Perl . . .
Are you talking about Mastering Algorithms with Perl, by Macdonald,
Orwant, and Hietaniemi? I haven’t really had a chance to read it in any
depth, but it looks like a great way to get a basic introduction for
someone who knows Perl, and build a foundation for some of the more
complex and in-depth algorithms books.
The problem I keep seeing with the links posted in this thread is that
you pretty much need to know the name of what you want to even find
it. I don’t always know that when I’m algorithm hunting.
On Wed, Feb 06, 2008 at 10:47:51AM +0900, James G. wrote:
A Ruby algorithms book would be really nice to have. (I have a Perl
book like that I’ve used a fair bit.)
I’d love to find a Ruby algorithms book, myself.
Yeah, I’ve even considered submitting a proposal for one of these to a
publisher. It would be a lot of work though, for sure.
re: Perl . . .
Are you talking about Mastering Algorithms with Perl, by Macdonald,
Orwant, and Hietaniemi?
Yes.
I haven’t really had a chance to read it in any
depth, but it looks like a great way to get a basic introduction for
someone who knows Perl, and build a foundation for some of the more
complex and in-depth algorithms books.
It’s pretty good.
At times it gets a little into the download-this-library-to-do-the-
work-for-you mode. While that’s often the way you should handle that
kind of thing, I want an algorithm book to teach me instead.
It’s definitely good about raising your familiarity overall though.
The examples are also usually pretty easy to translate to Ruby.
Since Ruby arrays are dynamically sized, the second needs to
reallocate and copy the contents.
So in these cases certain array stores might actually be O(n) where n
is the length of the array rather than O(1).
This is actually not true: you need to compare apples with apples. You
cannot assign a C array beyond its boundaries (well, you can -
sometimes). So you would have to compare assignments within the
preallocated size. Same reasonings apply to the size in memory. Fact
is, you can use Ruby Arrays like C Arrays but most of the time you
don’t.
The fact that Ruby is interpreted and a completely different language
than C does not invalidate complexity theory. Keep in mind that O(n) is
just an approximation really meaning “the effort grows asymptotically
linear for n larger than a certain threshold” - or, slightly different,
“the effort is O(n*X+C)” with X and C being constants. Eventually
runtime will be determined by the number of input parameters and
duplication of this number will duplicate runtime.
So even though Ruby exposes different runtime characteristics it can be
still used to study algorithms (actually I believe it is well suited
because the clutterfree syntax eases focusing on the algorithmic part)
and complexity theory.
Of course, this does not free us from measuring and performance tuning.
Often some implementations in Ruby are faster because the use library
code implemented in C although in theory they should be slower.
You have one point though: often these ported books do not use features
of the target language well and the code presented tends to look
strange.
That book is terrible. It should be titled “Data Structures and
Algorithms with Object Oriented Design Patterns in C++ or Java That
Happen to Be Written in Ruby”.
It doesn’t use any Ruby or functional idioms. It looks like he paid a
minimum wage code monkey to translate the book into a lot of languages
(or used some automated means).
–Jeremy
On Sat, Feb 9, 2008 at 5:01 PM, Christopher D. [email protected]
wrote:
On Wed, Feb 06, 2008 at 10:47:51AM +0900, James G. wrote:
A Ruby algorithms book would be really nice to have. (I have a Perl
book like that I’ve used a fair bit.)
I’d love to find a Ruby algorithms book, myself.
Interestingly, I just ran into this online book, Data Structures and
Algorithms
with Object-Oriented Design Patterns in Ruby, at http://www.brpreiss.com/books/opus8/