Looking for an Algorithms and Data Structures Book

Discussion in 'C++' started by John McCabe, Oct 24, 2005.

  1. John McCabe

    John McCabe Guest

    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 McCabe, Oct 24, 2005
    #1
    1. Advertising

  2. John McCabe

    mlimber Guest

    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
    mlimber, Oct 24, 2005
    #2
    1. Advertising

  3. 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
    n2xssvv g02gfr12930, Oct 24, 2005
    #3
  4. John McCabe

    John McCabe Guest

    "mlimber" <> 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, Oct 24, 2005
    #4
  5. John McCabe

    John McCabe Guest

    n2xssvv g02gfr12930 <> 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.
    John McCabe, Oct 24, 2005
    #5
  6. John McCabe

    red floyd Guest

    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...
    red floyd, Oct 25, 2005
    #6
  7. John McCabe wrote:
    > n2xssvv g02gfr12930 <> 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/SiliconValley/Network/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, Oct 25, 2005
    #7
  8. n2xssvv g02gfr12930 wrote:
    > John McCabe wrote:
    >
    >> n2xssvv g02gfr12930 <> 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/SiliconValley/Network/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/html/RedBlack/redblack.html

    JFJB
    n2xssvv g02gfr12930, Oct 25, 2005
    #8
  9. John McCabe

    John McCabe Guest

    n2xssvv g02gfr12930 <> wrote:


    >This link gives an animated demonstration as well as some theory.
    >
    >http://www.geocities.com/SiliconValley/Network/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, Oct 25, 2005
    #9
  10. John McCabe

    John McCabe Guest

    John McCabe <> 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
    John McCabe, Oct 25, 2005
    #10
  11. John McCabe

    red floyd Guest

    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.
    red floyd, Oct 25, 2005
    #11
  12. John McCabe

    Mark P Guest

    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.
    Mark P, Oct 26, 2005
    #12
  13. John McCabe

    Manfred Guest

    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
    Manfred, Oct 26, 2005
    #13
  14. John McCabe

    mlimber Guest

    John McCabe wrote:
    > n2xssvv g02gfr12930 <> wrote:
    >
    >
    > >This link gives an animated demonstration as well as some theory.
    > >
    > >http://www.geocities.com/SiliconValley/Network/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
    mlimber, Oct 26, 2005
    #14
  15. John McCabe

    John McCabe Guest

    Manfred <> 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, Oct 26, 2005
    #15
  16. John McCabe

    John McCabe Guest

    "mlimber" <> 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.
    John McCabe, Oct 26, 2005
    #16
  17. John McCabe

    Manfred Guest

    John McCabe wrote:
    > Manfred <> 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
    Manfred, Oct 26, 2005
    #17
  18. John McCabe

    John McCabe Guest

    Manfred <> 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 McCabe, Oct 27, 2005
    #18
  19. John McCabe wrote:
    > Manfred <> 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
    John Harrison, Oct 27, 2005
    #19
  20. John McCabe

    Manfred Guest

    John Harrison wrote:
    > John McCabe wrote:
    >
    >> Manfred <> 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
    Manfred, Oct 27, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    653
    Roedy Green
    Jan 14, 2006
  2. Thomas Nick
    Replies:
    0
    Views:
    1,858
    Thomas Nick
    Jun 13, 2005
  3. efrat
    Replies:
    2
    Views:
    375
    Bryan Olson
    Sep 28, 2006
  4. Alfonso Morra
    Replies:
    11
    Views:
    701
    Emmanuel Delahaye
    Sep 24, 2005
  5. Alec Taylor
    Replies:
    0
    Views:
    155
    Alec Taylor
    Mar 2, 2012
Loading...

Share This Page