Computer Science Problems

[Robert Klemme]

Hello --



Start by looking at know University sites -- you'll often come across some.
).

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.

Cheers

robert

 

[Chris Hulan]

Hi all,

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:

1. Is there a definitive book/web site/resource on this and other
computer science 'problems'? (Whether Ruby, C, C++, Java, Perl based).
2. Do people have favorite 'Data Structure and Algorithm' books?
3. 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 Berci's non-complicated solution, but would never had known it
was a 'famous computer science problem'.

cheers,

Some links:
Algorithms and Data Structures Research & Reference Material --
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/
Dictionary of Algorithms and Data Structures -- http://www.nist.gov/dads/
Structure and Interpretation of Computer Programs --
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-1.html
How to Design Programs -- http://www.htdp.org/

cheers

 

[James Gray]

Algorithms and Data Structures Research & Reference Material --
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/
Dictionary of Algorithms and Data Structures -- http://www.nist.gov/dads/

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.

James Edward Gray II

 

[Chad Perrin]

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.

 

[James Gray]

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.

James Edward Gray II

 

[Christopher Dicely]

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/

 

[Rick DeNatale]

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/

Once more into the breach dear friends!

http://groups.google.com/group/comp...k=gst&q=algorithm+books+ruby#67382c9359422e2f

 

[Robert Klemme]

Once more into the breach dear friends!

http://groups.google.com/group/comp...k=gst&q=algorithm+books+ruby#67382c9359422e2f

For example, I'm pretty sure that these two snippets will have
different timing profiles

a = Array.new(300)
a[200] = 1

and

a = Array.new(190)
a[200] = 1

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.

Kind regards

robert

 

[Joe]

If you're looking for some interesting problems, and ways to solve
them this book is pretty good (it's similar to Ruby Quiz style
problems):
http://www.amazon.com/Programming-C...=sr_1_1?ie=UTF8&s=books&qid=1202686974&sr=1-1

This is a website that lets you submit source code, and it will be
tested for you.
http://acm.uva.es/problemset/

Joe

 

[Victor Reyes]

[Note: parts of this message were removed to make it a legal post.]

If challenge is what you REALLY want, look no further than the ultimate
authority in computer algorithms:
(The Art of Computer Programming
Series)<http://www.amazon.com/Art-Computer-...bs_sr_1?ie=UTF8&s=books&qid=1202740125&sr=8-1>By:
Donald E. Knuth.

Victor

If you're looking for some interesting problems, and ways to solve
them this book is pretty good (it's similar to Ruby Quiz style
problems):

http://www.amazon.com/Programming-C...=sr_1_1?ie=UTF8&s=books&qid=1202686974&sr=1-1

This is a website that lets you submit source code, and it will be
tested for you.
http://acm.uva.es/problemset/

Joe

 

[Benjamin Kudria]

If you're looking for some interesting problems, and ways to solve
them this book is pretty good (it's similar to Ruby Quiz style
problems):
http://www.amazon.com/Programming-C...=sr_1_1?ie=UTF8&s=books&qid=1202686974&sr=1-1

Skiena is *my* CS professor!
His new algorithms books is quite good. He's distributed printer's
darft copies to the students in the class.

-Ben Kudria

 

[Jeremy McAnally]

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

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/

--
http://www.jeremymcanally.com/

My books:
Ruby in Practice
http://www.manning.com/mcanally/

My free Ruby e-book
http://www.humblelittlerubybook.com/

My blogs:
http://www.mrneighborly.com/
http://www.rubyinpractice.com/

 

[James Gray]

Skiena is *my* CS professor!
His new algorithms books is quite good. He's distributed printer's
darft copies to the students in the class.

What's the title?

James Edward Gray II