Looking for an Algorithms and Data Structures Book

[John McCabe]

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

[mlimber]

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

[n2xssvv g02gfr12930]

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

[John McCabe]

"mlimber" <ml*****@gmail.com> 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.

[John McCabe]

n2xssvv g02gfr12930 <n2*****************@ntlworld.com> 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.

[red floyd]

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

[n2xssvv g02gfr12930]

John McCabe wrote:

n2xssvv g02gfr12930 <n2*****************@ntlworld.com> 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

[n2xssvv g02gfr12930]

n2xssvv g02gfr12930 wrote:

John McCabe wrote:

n2xssvv g02gfr12930 <n2*****************@ntlworld.com> 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

[John McCabe]

n2xssvv g02gfr12930 <n2*****************@ntlworld.com> 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

[John McCabe]

John McCabe <jo**@nospam.assen.demon.co.uk.nospam> 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

[red floyd]

John McCabe wrote:

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

Not C++ specific, but Aho,Hopcroft,Ullman "The Design and Analysis of
Computer Algorithms" has a section on AVL trees.

[Mark P]

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

CLR, aka "Introduction to Algorithms" by Cormen, Leiserson, and Rivest,
is a very good book on algorithms and data structures. They opt for
pseudocode rather than C++ so you won't find any drop in components, but
they're very thorough and rigorous.

[Manfred]

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 know of 'Algorithms in C++' by Robert Sedgewick.
There is a hardcover edition and a Paperback
edition which includes:
"Parts 1-5: Fundamentals, Data Structures,
Sorting, Searching, and Graph Algorithms"
You'll find it on amazon if you search for the title.

Manfred

[mlimber]

John McCabe wrote:

n2xssvv g02gfr12930 <n2*****************@ntlworld.com> 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.

The book I previously mentioned (_Data Structures, Algorithms, and
Object-oriented Programming_ by Heileman) has chapters on lists, stacks
& queues, binary search trees, hashing, priority queues, balanced
search trees (namely, AVL, red-black, and splay trees), heaps, etc.
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

Not I.

Cheers! --M

[John McCabe]

Manfred <ne******@web.de> wrote:

I know of 'Algorithms in C++' by Robert Sedgewick.
There is a hardcover edition and a Paperback
edition which includes:
"Parts 1-5: Fundamentals, Data Structures,
Sorting, Searching, and Graph Algorithms"
You'll find it on amazon if you search for the title.

I found that one on Amazon. Do you have an opinion on it? From what
I've seen there appears to be significant differences in the Amazon
reviews which worry me a bit, especially as the book is going on
£60.00 on amazon.co.uk.

[John McCabe]

"mlimber" <ml*****@gmail.com> wrote:

The book I previously mentioned (_Data Structures, Algorithms, and
Object-oriented Programming_ by Heileman) has chapters on lists, stacks
& queues, binary search trees, hashing, priority queues, balanced
search trees (namely, AVL, red-black, and splay trees), heaps, etc.

Thanks for that. I've emailed Greg Heileman to ask if he can give me
more details on the table of contents as I can't find much on the net.
He has replied to my initial message, but not my follow-up, and not
with the details I need (yet) :-(

From what you've said, and what I *have* found on the net about it, it
sounds like it could be as close a match as it may be possible to get
to what I'm looking for.

[Manfred]

John McCabe wrote:

Manfred <ne******@web.de> wrote:

I know of 'Algorithms in C++' by Robert Sedgewick.
There is a hardcover edition and a Paperback
edition which includes:
"Parts 1-5: Fundamentals, Data Structures,
Sorting, Searching, and Graph Algorithms"
You'll find it on amazon if you search for the title.

I found that one on Amazon. Do you have an opinion on it? From what
I've seen there appears to be significant differences in the Amazon
reviews which worry me a bit, especially as the book is going on
£60.00 on amazon.co.uk.

A friend of mine told me about it and he was very
fond of it. But I just had a short look at it in a
bookstore and it seemed to be comprehensable with
good C++ code.
But you could perhaps have a look for it in your
local book store.

Manfred

[John McCabe]

Manfred <ne******@web.de> wrote:

A friend of mine told me about it and he was very
fond of it. But I just had a short look at it in a
bookstore and it seemed to be comprehensable with
good C++ code.
But you could perhaps have a look for it in your
local book store.

Thanks for that suggestion, but it's easier said than done. We have
two bookstores in the town I live in, both of which have around 10-15
books on computing in them! Even the bigger nearby towns don't have
bookstores that have anything except the most popular books, i.e. Java
and Web development stuff, with a bit of ASP.NET thrown in.

I guess some of the local university townsmight have something, so the
next time I'm near one of those I'll look.

Thanks again.

[John Harrison]

John McCabe wrote:

Manfred <ne******@web.de> wrote:

A friend of mine told me about it and he was very
fond of it. But I just had a short look at it in a
bookstore and it seemed to be comprehensable with
good C++ code.
But you could perhaps have a look for it in your
local book store.

Thanks for that suggestion, but it's easier said than done. We have
two bookstores in the town I live in, both of which have around 10-15
books on computing in them! Even the bigger nearby towns don't have
bookstores that have anything except the most popular books, i.e. Java
and Web development stuff, with a bit of ASP.NET thrown in.

I guess some of the local university townsmight have something, so the
next time I'm near one of those I'll look.

Thanks again.

I'd disagree about the good C++ code. In fact as C++ code goes it's
poor. But clearly that isn't the point of the book and the main thing is
that Sedgewick does explain the algorithms very well. It is a beginning
book and it isn't particularly formal, for most people those are advantages.

john

[Manfred]

John Harrison wrote:

John McCabe wrote:

Manfred <ne******@web.de> wrote:

A friend of mine told me about it and he was very fond of it. But I
just had a short look at it in a bookstore and it seemed to be
comprehensable with good C++ code.
But you could perhaps have a look for it in your local book store.

Thanks for that suggestion, but it's easier said than done. We have
two bookstores in the town I live in, both of which have around 10-15
books on computing in them! Even the bigger nearby towns don't have
bookstores that have anything except the most popular books, i.e. Java
and Web development stuff, with a bit of ASP.NET thrown in.

I guess some of the local university townsmight have something, so the
next time I'm near one of those I'll look.

Thanks again.

I'd disagree about the good C++ code. In fact as C++ code goes it's
poor. But clearly that isn't the point of the book and the main thing is
that Sedgewick does explain the algorithms very well. It is a beginning
book and it isn't particularly formal, for most people those are
advantages.

john

Thanks for clearing this up John. As I said
before, i didn't have time to have a closer look
at the book.

Manfred

[mlimber]

John McCabe wrote:

John McCabe <jo**@nospam.assen.demon.co.uk.nospam> 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

Nope, but you can at least peer inside Drozdek's book at Amazon:

http://www.amazon.com/gp/product/053...books&v=glance

All the reviews are positive (which can be deceptive), and it covers
AVL and splay trees and hashing.

M

[Neil Cerutti]

On 2005-10-26, John McCabe <jo**@nospam.assen.demon.co.uk.nospam> wrote:

Manfred <ne******@web.de> wrote:

I know of 'Algorithms in C++' by Robert Sedgewick.
There is a hardcover edition and a Paperback
edition which includes:
"Parts 1-5: Fundamentals, Data Structures,
Sorting, Searching, and Graph Algorithms"
You'll find it on amazon if you search for the title.

I found that one on Amazon. Do you have an opinion on it? From
what I've seen there appears to be significant differences in
the Amazon reviews which worry me a bit, especially as the book
is going on £60.00 on amazon.co.uk.

I haven't read much of it, but it is very densely written, dry,
and dull. It might be exactly what you're looking for. I wrote a
toy red-black tree container based on one chapter of the book.
I'd prefer writing that's a bit easier to decode, but it was good
enough for what I needed.

--
Neil Cerutti

[mlimber]

John McCabe wrote:

"mlimber" <ml*****@gmail.com> wrote:

The book I previously mentioned (_Data Structures, Algorithms, and
Object-oriented Programming_ by Heileman) has chapters on lists, stacks
& queues, binary search trees, hashing, priority queues, balanced
search trees (namely, AVL, red-black, and splay trees), heaps, etc.

Thanks for that. I've emailed Greg Heileman to ask if he can give me
more details on the table of contents as I can't find much on the net.
He has replied to my initial message, but not my follow-up, and not
with the details I need (yet) :-(

From what you've said, and what I *have* found on the net about it, it
sounds like it could be as close a match as it may be possible to get
to what I'm looking for.

Each item in my list is a chapter. Add to that four chapters of
introductory material, efficiency analysis, sets, and graphs, and
bada-bing, you have the table of contents.

Cheers! --M

[John McCabe]

"mlimber" <ml*****@gmail.com> wrote:

John McCabe wrote:

From what you've said, and what I *have* found on the net about it, it
sounds like it could be as close a match as it may be possible to get
to what I'm looking for.

Each item in my list is a chapter. Add to that four chapters of
introductory material, efficiency analysis, sets, and graphs, and
bada-bing, you have the table of contents.

Aha - thanks a lot for that. It looks like it's got what I want then.

One thing, do you remember if it mentions "skip lists"?

[Ninan]

I have read this book, Graph theory is in part 5. I have not read the
other books , so comparison will be a difficult thing. In general it
is a good book. C++ code is short and easy to follow. I would consider
it more C/C++ code. The explanation of the theory while straightforward
and easy to follow, some times gets a little long winded and can loose
track. But overall I would recommend this book

[mlimber]

John McCabe wrote:

"mlimber" <ml*****@gmail.com> wrote:

John McCabe wrote:

From what you've said, and what I *have* found on the net about it, it
sounds like it could be as close a match as it may be possible to get
to what I'm looking for.

Each item in my list is a chapter. Add to that four chapters of
introductory material, efficiency analysis, sets, and graphs, and
bada-bing, you have the table of contents.

Aha - thanks a lot for that. It looks like it's got what I want then.

One thing, do you remember if it mentions "skip lists"?

It does have a section on them.

Cheers! --M

[mlimber]

Ninan wrote:

I have read this book, Graph theory is in part 5. I have not read the
other books , so comparison will be a difficult thing. In general it
is a good book. C++ code is short and easy to follow. I would consider
it more C/C++ code. The explanation of the theory while straightforward
and easy to follow, some times gets a little long winded and can loose
track. But overall I would recommend this book

Which book are you talking about exactly? Please quote at least a
little context.

Cheers! --M

[Ninan]

i am talking about the Sedgewick book.

Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching
Pts. 1-4 by Robert Sedgewick

[Yellow Dog]

On Tue, 25 Oct 2005 21:52:00 +0100, John McCabe
<jo**@nospam.assen.demon.co.uk.nospam> wrote:

[SNIP]

Does anyone know anything about this book:

Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching
Pts. 1-4 by Robert Sedgewick

I have a copy of this book. I keep it at work. It has a number of
useful explanations about a number of algorithms. IIRC, it does cover
Red-Black trees, splay trees and graph theory. I also have the
following book:

Data Structures and Algorithms in C++ by Adam Drozdek, second edition.
ISBN 0 534-37597-9

This book covers binary trees in excruciating detail as well as
hashing theory and data compression.

It was published inn 2001, but I purchased my copy in a local
bookstore. The web site for the publisher is:
http://brookscole.com

You may be able to find out if there is a newer version.

Good luck,

ken
If it ain't broke....fix it anyway!