[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Computer Science Problems

markonlinux

2/5/2008 11:31:00 PM

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,

--
Mark
32 Answers

Clifford Heath

2/5/2008 11:43:00 PM

0

markonlinux@gmail.com wrote:
> 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"

<http://en.wikipedia.org/wiki/Np_co... would be a good start.

Thomas Adam

2/5/2008 11:50:00 PM

0

Hello --

On 05/02/2008, markonlinux@gmail.com <markonlinux@gmail.com> wrote:
> 1. 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.
).
> 2. Do people have favorite 'Data Structure and Algorithm' books?

Robert Sedgewick's books are great, if not a little heavy-going:

http://www.cs.princeto...

-- Thomas Adam

Ken Bloom

2/6/2008 12:33:00 AM

0

On Tue, 05 Feb 2008 15:31:17 -0800, markonlinux wrote:

> 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).

http://www.nada.kth.se/~viggo/pr... discusses optimization
problems in NP

> 2. 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.

--Ken

--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...

James Gray

2/6/2008 1:05:00 AM

0

On Feb 5, 2008, at 6:39 PM, Ken Bloom wrote:

> Donald Knuth, _The Art of Computer Programming_ is like the bible for
> computer scientists.

But be warned, it's as dry as you would expect a computer science
reference book to be. :)

James Edward Gray II

Matt Lawrence

2/6/2008 1:10:00 AM

0

On Wed, 6 Feb 2008, James Gray wrote:

> On Feb 5, 2008, at 6:39 PM, Ken Bloom wrote:
>
>> Donald Knuth, _The Art of Computer Programming_ is like the bible for
>> computer scientists.
>
> 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?

-- Matt
It's not what I know that counts.
It's what I can remember in time to use.

Tim Hunter

2/6/2008 1:16:00 AM

0

markonlinux@gmail.com wrote:
> 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 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 Thomas and Andy Hunt.

You could do a lot worse than these two classics. Find them at your
favorite online bookseller.


--
RMagick: http://rmagick.ruby...
RMagick 2: http://rmagick.ruby...rmagick2.html

James Gray

2/6/2008 1:48:00 AM

0

On Feb 5, 2008, at 5:34 PM, markonlinux@gmail.com wrote:

> 1. Is there a definitive book/web site/resource on this and other
> computer science 'problems'? (Whether Ruby, C, C++, Java, Perl based)

I have this book on my shelf:

http://www.amazon.com/Algorithm-Design-Manual-Steve-Skiena/dp/0387948600/ref=sr_1_4?ie=UTF8&s=books&qid=1202261989&...

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.)

James Edward Gray II

James Gray

2/6/2008 1:49:00 AM

0

On Feb 5, 2008, at 7:10 PM, Matt Lawrence wrote:

> On Wed, 6 Feb 2008, James Gray wrote:
>
>> On Feb 5, 2008, at 6:39 PM, Ken Bloom wrote:
>>
>>> Donald Knuth, _The Art of Computer Programming_ is like the bible
>>> for
>>> computer scientists.
>>
>> 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. :D

James Edward Gray II

Rob Biedenharn

2/6/2008 2:18:00 AM

0

On Feb 5, 2008, at 8:49 PM, James Gray wrote:

> On Feb 5, 2008, at 7:10 PM, Matt Lawrence wrote:
>
>> On Wed, 6 Feb 2008, James Gray wrote:
>>
>>> On Feb 5, 2008, at 6:39 PM, Ken Bloom wrote:
>>>
>>>> Donald Knuth, _The Art of Computer Programming_ is like the bible
>>>> for
>>>> computer scientists.
>>>
>>> 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. :D
>
> James Edward Gray 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.

-Rob

Rob Biedenharn http://agileconsult...
Rob@AgileConsultingLLC.com

David Moreno

2/6/2008 2:59:00 AM

0

Ken Bloom wrote:
> 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. :)