Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Looking for an Algorithms and Data Structures Book

Reply
Thread Tools

Looking for an Algorithms and Data Structures Book

 
 
John McCabe
Guest
Posts: n/a
 
      10-24-2005
Hi

I'm looking for something equivalent to the Data Structures and
Algorithms in Ada 95 books by Biedler and Feldman etc, but based
towards efficient C++ implementations.

Does anyone know of such a thing and could recommend one?

I'm particularly interested in coverage of binary search trees,
especially Red-Black, Splay and AVL, as well as hashing tables and
graphs.

Any suggestions gratefully appreciated.

John
 
Reply With Quote
 
 
 
 
mlimber
Guest
Posts: n/a
 
      10-24-2005
John McCabe wrote:
> Hi
>
> I'm looking for something equivalent to the Data Structures and
> Algorithms in Ada 95 books by Biedler and Feldman etc, but based
> towards efficient C++ implementations.
>
> Does anyone know of such a thing and could recommend one?
>
> I'm particularly interested in coverage of binary search trees,
> especially Red-Black, Splay and AVL, as well as hashing tables and
> graphs.
>
> Any suggestions gratefully appreciated.
>
> John


I have a slightly dated book called _Data Structures, Algorithms, and
Object-oriented Programming_ by Heileman that covers those topics in
C++. There may be a new edition for all I know.

Cheers! --M

 
Reply With Quote
 
 
 
 
n2xssvv g02gfr12930
Guest
Posts: n/a
 
      10-24-2005
John McCabe wrote:
> Hi
>
> I'm looking for something equivalent to the Data Structures and
> Algorithms in Ada 95 books by Biedler and Feldman etc, but based
> towards efficient C++ implementations.
>
> Does anyone know of such a thing and could recommend one?
>
> I'm particularly interested in coverage of binary search trees,
> especially Red-Black, Splay and AVL, as well as hashing tables and
> graphs.
>
> Any suggestions gratefully appreciated.
>
> John

John

Most STL Map implementations are done using Red-Black trees.
Unfortunately, the C++ code is for a template version, which
only adds to the difficulty in understanding the code. But as
the STL code is robust, this should be a good start. Perhaps
stepping into some code that uses STL Map will help to highlight
the relevant sections of code. Hope this helps.

STL = Standard Template Library

JFJB
 
Reply With Quote
 
John McCabe
Guest
Posts: n/a
 
      10-24-2005
"mlimber" <(E-Mail Removed)> wrote:

>John McCabe wrote:


>> I'm looking for something equivalent to the Data Structures and
>> Algorithms in Ada 95 books by Biedler and Feldman etc, but based
>> towards efficient C++ implementations.


<..snip..>

>I have a slightly dated book called _Data Structures, Algorithms, and
>Object-oriented Programming_ by Heileman that covers those topics in
>C++. There may be a new edition for all I know.


thanks for that suggestion. I can't find much detail on that book, but
I've emailed the author to see if he can let me know more about it.
Things like the link to ToC on his web page don't work, and Amazon
hasn't got much info.

It sounds interesting, but obviously I'd still appreciate any other
suggestions.

 
Reply With Quote
 
John McCabe
Guest
Posts: n/a
 
      10-24-2005
n2xssvv g02gfr12930 <(E-Mail Removed)> wrote:

>Most STL Map implementations are done using Red-Black trees.
>Unfortunately, the C++ code is for a template version, which
>only adds to the difficulty in understanding the code. But as
>the STL code is robust, this should be a good start. Perhaps
>stepping into some code that uses STL Map will help to highlight
>the relevant sections of code. Hope this helps.


Thanks for that suggestion. I guess I'm more interested in the theory
behind them all at the moment, and I'm particularly interested in
applicability for particular problems. I read an article on
performance of BSTs recently which was very good and useful
information, but didn't address any of the other techniques in enough
detail.

Thanks again though.


 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      10-24-2005
John McCabe wrote:
> Thanks for that suggestion. I guess I'm more interested in the theory
> behind them all at the moment, and I'm particularly interested in
> applicability for particular problems.



Good for you. The stock answer around here is "use
std::whatever_container<>". G-d knows, I've said that enough myself.
But rolling your own is a wonderful way to understand the theory behind
those std::containers, as well as understanding the pitfalls, and
exactly *why* you want to use the std:: versions (so you don't have to
debug them ).

I applaud you for wanting to learn the theory, as well as the
implementation. With that kind of attitude, you'll go far...
 
Reply With Quote
 
n2xssvv g02gfr12930
Guest
Posts: n/a
 
      10-25-2005
John McCabe wrote:
> n2xssvv g02gfr12930 <(E-Mail Removed)> wrote:
>
>
>>Most STL Map implementations are done using Red-Black trees.
>>Unfortunately, the C++ code is for a template version, which
>>only adds to the difficulty in understanding the code. But as
>>the STL code is robust, this should be a good start. Perhaps
>>stepping into some code that uses STL Map will help to highlight
>>the relevant sections of code. Hope this helps.

>
>
> Thanks for that suggestion. I guess I'm more interested in the theory
> behind them all at the moment, and I'm particularly interested in
> applicability for particular problems. I read an article on
> performance of BSTs recently which was very good and useful
> information, but didn't address any of the other techniques in enough
> detail.
>
> Thanks again though.
>
>

This link gives an animated demonstration as well as some theory.

http://www.geocities.com/SiliconVall.../1854/Rbt.html

I've actually got the "Introduction to Algorithms" book referenced
and I'd recommend it if you're interested in the often unseen
algorithms used to solve a variety of problems.
It's heart warming to know that I'm not the only one interested in
understanding what's really going on and why, and it was from
looking at the STL code that I became interested in Red Black
trees. More to the point I decided to develop my own C++ code
to implement a Red Black tree, both for hard coded data and as
a template version. I found it satisfying, but it hasn't helped
career wise yet as far as I can tell.

JFJB
 
Reply With Quote
 
n2xssvv g02gfr12930
Guest
Posts: n/a
 
      10-25-2005
n2xssvv g02gfr12930 wrote:
> John McCabe wrote:
>
>> n2xssvv g02gfr12930 <(E-Mail Removed)> wrote:
>>
>>
>>> Most STL Map implementations are done using Red-Black trees.
>>> Unfortunately, the C++ code is for a template version, which
>>> only adds to the difficulty in understanding the code. But as
>>> the STL code is robust, this should be a good start. Perhaps
>>> stepping into some code that uses STL Map will help to highlight
>>> the relevant sections of code. Hope this helps.

>>
>>
>>
>> Thanks for that suggestion. I guess I'm more interested in the theory
>> behind them all at the moment, and I'm particularly interested in
>> applicability for particular problems. I read an article on
>> performance of BSTs recently which was very good and useful
>> information, but didn't address any of the other techniques in enough
>> detail.
>>
>> Thanks again though.
>>
>>

> This link gives an animated demonstration as well as some theory.
>
> http://www.geocities.com/SiliconVall.../1854/Rbt.html
>
> I've actually got the "Introduction to Algorithms" book referenced
> and I'd recommend it if you're interested in the often unseen
> algorithms used to solve a variety of problems.
> It's heart warming to know that I'm not the only one interested in
> understanding what's really going on and why, and it was from
> looking at the STL code that I became interested in Red Black
> trees. More to the point I decided to develop my own C++ code
> to implement a Red Black tree, both for hard coded data and as
> a template version. I found it satisfying, but it hasn't helped
> career wise yet as far as I can tell.
>
> JFJB

You could also try this link to see the steps involved for adding
and deleting nodes from a Red Black tree.

http://www.ece.uc.edu/~franco/C321/h.../redblack.html

JFJB
 
Reply With Quote
 
John McCabe
Guest
Posts: n/a
 
      10-25-2005
n2xssvv g02gfr12930 <(E-Mail Removed)> wrote:


>This link gives an animated demonstration as well as some theory.
>
>http://www.geocities.com/SiliconVall.../1854/Rbt.html
>
>I've actually got the "Introduction to Algorithms" book referenced
>and I'd recommend it if you're interested in the often unseen
>algorithms used to solve a variety of problems.
>It's heart warming to know that I'm not the only one interested in
>understanding what's really going on and why, and it was from
>looking at the STL code that I became interested in Red Black
>trees. More to the point I decided to develop my own C++ code
>to implement a Red Black tree, both for hard coded data and as
>a template version. I found it satisfying, but it hasn't helped
>career wise yet as far as I can tell.


Thanks for that information, and the information on the book.

I've checked it out on Amazon and it looks very interesting, however
it doesn't list AVL trees in the table of contents.

I think I may be looking for something I can't afford Probably
Knuth's multi-volume epic!

I read the article "Performance Analysis of BSTs in System Software"
and based on that it looks like, for our application, an AVL tree
would be best, closely followed by a Splay tree so whatever book I go
for needs to at least cover those. Red Black trees would also be a
bonus really. Also the hash table stuff needs to be there as well, and
I spotted something about (I think) directed graphs that I'd like to
read more on.

But thanks again for taking the time to provide me with those links
and info.

Does anyone know anything about this book:

Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching
Pts. 1-4 by Robert Sedgewick
 
Reply With Quote
 
John McCabe
Guest
Posts: n/a
 
      10-25-2005
John McCabe <(E-Mail Removed)> wrote:

>I spotted something about (I think) directed graphs that I'd like to
>read more on.


Actually, that might be skip lists I was talking about!

Does anyone have experience of:

Data Structures and Algorithms in C++

by either...

Goodrich, Tamassia and Mount (http://cpp.datastructures.net/)

or

Drozdek


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Spacing and timing for comparing algorithms and data-structures Alec Taylor Python 0 03-02-2012 04:55 AM
Questions on Using Python to Teach Data Structures and Algorithms efrat Python 2 09-28-2006 11:42 AM
Data Structures and Algorithms in Java kiamkhai@oum.edu.my Java 3 01-14-2006 08:28 PM
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Needed Instructor's Manual for Data Structures and Algorithms in C++ needed!!! Thomas Nick C++ 0 06-13-2005 01:58 AM



Advertisments