Computer Science Problems

[markonlinux]

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,

 

[Clifford Heath]

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_complete> would be a good start.

 

[Thomas Adam]

Hello --

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.princeton.edu/~rs/

-- Thomas Adam

 

[Ken Bloom]

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/problemlist/ 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

 

[James Gray]

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]

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]

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.

 

[James Gray]

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-Des...=sr_1_4?ie=UTF8&s=books&qid=1202261989&sr=1-4

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]

Dry? Heretic! What is not to love about Mix assembler?

Assembler. Thanks for making my point.

James Edward Gray II

 

[Rob Biedenharn]

Assembler. Thanks for making my point.

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://agileconsultingllc.com
(e-mail address removed)

 

[David Moreno]

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.

 

[fedzor]

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

 

[Rob Biedenharn]

Cormen is my CS Professor!

-------------------------------------------------------|
~ Ari
seydar: it's like a crazy love triangle of Kernel commands and C code

Leiserson was my algorithms Prof and Cormen was my TA. (I had Rivest
for my AI Prof. ;-)

(this was before they published their own book, of course)

-Rob

Rob_Biedenharn [at] alum.MIT.edu http://agileconsultingllc.com
(e-mail address removed)

 

[Clifford Heath]

"This problem actually turns out to be famous in computer science.
It's called the Knapsack Problem.
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.

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?

 

[Ken Bloom]

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:

http://www.nada.kth.se/~viggo/problemlist/ is probably as close as you
come to a full compendium of NP-Hard optimization problems, and their
approximation algorithms, etc

--Ken

 

[markonlinux]

Hi Clifford,

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?

1. was my main focus, but I am really appreciating answers to 2. and
3. 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!) ;-)

Keep suggestions coming everyone ;-)


cheers,

 

[markonlinux]

I'll post again:

http://www.nada.kth.se/~viggo/problemlist/is probably as close as you
come to a full compendium of NP-Hard optimization problems, and their
approximation algorithms, etc

--Ken

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

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


cheers,

 

[Clifford Heath]

I'll post again:

Nice one Ken, sorry I missed that the first time.
Definitely a keeper.

Clifford Heath.

 

[Martin DeMello]

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?

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.

martin

 

[James Gray]

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!

James Edward Gray II