Advanced Data Structures?

mdf356 asks: "It's been 5 years since I left graduate school and started designing and writing software for a living. After 5 years of writing operating systems code, I feel like I've forgotten some of the more advanced data structures I used to know. The next time an interesting problem arises, I'd like to have more in my toolbox than hashes, linked lists, heaps and various binary and n-way trees. I'd like something short and sweet, more in the line of the standard C book. Algorithm Design by Kleinberg and Tardos looks likely to be too basic, but I haven't read it (I'd like to avoid paying $90 for something that won't meet my needs). CLR is far too large and almost exclusively covers basic territory. Tarjan's Data Structures book looks like it has potential, but seems focused on network algorithms, which are unlikely to be applicable to the kernel programming I do. What are some good reference books on more advanced data structures and algorithms, particularly ones with potential applicability to an operating systems kernel?"

Canonical Terms of Academia

[eldavojohn]

Tarjan's Data Structures book looks like it has potential, but seems focused on network algorithms, which are unlikely to be applicable to the kernel programming I do.

You'd be surprised. Some of the very basic network algorithms are kind of universal. Because, let's face it, some operating systems revolve around message passing.

CLR is far too large and almost exclusively covers basic territory.

Well, let's be fair, when you get to advanced data structures, it's kind of up to you to really do all the imagining that makes them great. Don't dismiss CLR too quickly, as the book has a lot of great concepts that, if you're serious about algorithms and data structures, are quite useful as a starting toolbox.

Honestly though, when I went through college, the very last thing they tried to shove down my throat wasn't advanced data structures but instead Design Patterns [amazon.com]. I'm not talking about algorithm design but instead just designs in general. This book might not do it in C but the ideas are pretty language independent. It's your 'cookbook' of designs laid out in class diagrams and sometimes more documentation is provided. Anyways, what I would actually suggest is that you combine a book that covers C structures with book and what you would have is a way for you to make a set of complex classes that emulate a proxy. Or you have an adapter class that is a "advanced data structure." I guess what I'm trying to say is that I don't see the point of paying attention to advanced data structures when it's really the way these data structures interact that is complex and important.

The big problem is that, in order to make design patterns work for you, you have to go through a lot of documentation and diagrams. Take this for example, you're writing an OS code and there's a part of the operating system that's going to be changing frequently depending on processor (I don't know a lot about OS development), let's say the scheduler. So what do you do? Do you just willy-nilly throw the scheduler and start going? Well, what would be best is that if you encapsulated the scheduler inside a package or library so that it could easily be exchanged for another one. You try to keep it small and modularize the classes and data structures that change from those that don't. Then, a new processor comes out that might demand a new scheduler and you open up this mini-project, edit/debug it and roll it out as something that just replaces the classes and libraries on all your deployed versions. Sounds like common sense, right? Well, for some it is and for some it isn't but to me this interaction is a complication of data structures and I think that the answer you're looking for isn't necessarily a book called "advanced data structures" just a few that explain how they work.

Re:

[tedgyz]

Well, let's be fair, when you get to advanced data structures, it's kind of up to you to really do all the imagining that makes them great. Don't dismiss CLR too quickly, as the book has a lot of great concepts that, if you're serious about algorithms and data structures, are quite useful as a starting toolbox.

Good point. While it doesn't cover everything, it is hardly an "Introduction". I've been programming for 20 years (including kernels). This book fits the 80/20 rule - covering 80% of what I've need

Re:

[s31523]

Honestly though, when I went through college, the very last thing they tried to shove down my throat wasn't advanced data structures but instead Design Patterns.

I didn't get this too much in college, and got a little in grad school, but I went on to some self discovery afterwards and I gotta tell ya, Design Patterns are a must when it comes to doing OO design. Design patterns can be used in any structured design method as well, it just takes some creativity... I use this online link [dofactory.com], which is really co

Re:Canonical Terms of Academia

[Profound]

>> This book might not do it in C but the ideas are pretty language independent.

Design patterns is a book about Object Oriented design, aimed at the C++/Java level of abstraction. In low level languages it is clumbsy to write them, and in higher ones, unnecessary.

Re:

[bill_kress]

...and in higher ones, unnecessary.

What an interesting statement.

Seriously? No design patterns are useful in "higher level" languages?

Could you please elaborate?

Re:

[korpique]

Say iterators. In Perl (and Python IIRC) they're implemented by the virtual machine long as your data structure provides methods. The pattern's there but pretty mutilated by the fact that it's use is forced by the machine that runs your code. Delegates are useless if you have dynamic multiple inheritance like in Lingo; I think Perl at least used to have that too with mutilating @ISA array. Likewise in Javascript etc, although lacking classes you'd have to map each method separately, ugly, but delegatable t

Different patterns for different machinery

[korpique]

Anyway, the Design Patterns book contains patterns for problems imminent in the class of languages it concentrates in. In different language classes different problems arise. Higher patterns than those in that book would be more poignant to a larger set of languages.

Re:

[bill_kress]

Okay, so because 3 patterns are somewhat implemented by the system, how is it not useful to know the names for those and the other dozens?

Design patterns are almost all obvious to a decent programmer--you probably invented them before you ever heard of them. Knowing design patterns means that you and I can discuss Iterators without redefining what they mean each time we talk to someone new.

How is that need replaced by these new languages?

Also, you say the need for "Design Patterns" is eliminated??? Every s

Re:

[try_anything]

It all depends on what you mean by design patterns. Sometimes people describe design patterns as recurring patterns in programs. However, judging by the design patterns they catalogue, what they mean in practice is recurring patterns in source code. Aspects of program structure that do not have to be laboriously and repetitively specified do not qualify as design patterns. "Named memory cell that contains a value" is not a design pattern, despite its ubiquity, because most languages allow it to be expre

Re:

[Profound]

For a good overview of this, see http://www.norvig.com/design-patterns/ [norvig.com]

16 of 23 patterns have a qualitatively simpler implementation in Lisp

-Visitor is unnecessary in Multi-dispatch polymorphism (as mentioned in the book it is a hand written implementation)
-To be cheeky singleton is unnecessary when you have globals :)

Re:

[bill_kress]

So to say a pattern has a simpler implementation in another language means that you don't need to know it, understand it, understand when to use it and how?

The patterns aren't about how to implement something--they are all trivial to implement, I've yet to see one that I didn't create and implement myself before the books were even concieved of.

The big things about design patterns are that you have a common name for a pattern and some code smells to look for that indicate the need for a pattern. Because yo

Re:

[jgrahn]

Design patterns is a book about Object Oriented design, aimed at the C++/Java level of abstraction.

Well, it's about generalization, loose coupling and that kind of stuff. Lots of polymorphism. Orthogonal to algorithm work, and not always something you want to invest programming time and CPU cycles info.

Re:

[Nicolay77]

I totally agree with you.

The things commonly known as "Design Patterns" are really just several implementations of one of the two real patterns: The Human Compiler at Work. You have to do that stuff by hand because your language is not powerful enough.

The other real pattern, is macros (as in lisp macros). That is, extend your language to do that stuff for you.

Re:

[nulix]

Honestly though, when I went through college, the very last thing they tried to shove down my throat wasn't advanced data structures but instead Design Patterns

Design Patterns might not be what he's looking for. Design Patterns (in my experience) tend to map well to OO concepts and/or are described in OO concepts, kernel programming, however, does not fit well with the OO concept. I think he might be better of sticking to advanced data structures and algorithms rather than patterns if he wants to appl

data structures books

[Binder]

Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) by Robert Sedgewick

The Art of Computer Programming, by Donald E. Knuth

Two seminal works on the subject. It really depends on your needs however. Nearly anything you would need can be built off of the subjects in those books, but for more specialized datastructures you will probably have to move to specialized books.

Re:

[xtracto]

The Art of Computer Programming, by Donald E. Knuth

I highly recommend this book (all of its volumes). From what the original poster wrote I believe that is what he is looking for.

There is a limit of precooked data structures that you will find in books but reading Knuth works (anyone of them) will make allow you to develop a highly abstract thinking that will allow you to create the *right* structure for your work. I would also recommend his "Concrete Mathematics" book.

Re:

[oSand]

Knuth writes very well, but MIX? Fuck that.

Re:

[Mark of THE CITY]

What would you substitute, flowcharts or some high-level language? I learned data structures in part from Wirth's book, which used Pascal; it worked well for me.

Re:

[phonics]

I second the Sedgewick books. I still need to get through the second one (graphs) but it has great diagrams and thorough explanations without being as strictly rigorous as something like Knuth. However, I do have to say that the writing is still confusing in parts, and the source code (I got the C++ edition) is sometimes a little too terse but is very much like operating systems code.

If you want design patterns, the seminal book is Gamma, Helm, Johnson, and Vlissides text "Design Patterns: Elements of Reusa

Re:

[muridae]

Third vote for Sedgewick's Algorithms in C++. I picked up the 2nd edition (I think) hard back for under 10$ some years back. It has been more useful then any of the books that have been required reading while I've worked on my CS degree.

Re:

[gidds]

Yep, Sedgewick is well, well worth seeing. I'd never heard of it when I stumbled upon it in a bookshop: it was half an hour or so before I looked up and realised where I was, then I bought it on the spot. Unlike most similar books, I found it interesting to read! Not because it dumbs down or adds jokes, but because it makes the material itself interesting. It has enough detail to demonstrate the point, but not so much that it's hard to read -- so it's not a copy-and-paste sourcebook, but more like a cou

Re:

[RoloDMonkey]

I have to completely agree with this. I don't use Knuth much because he is heavy on the math, but Sedgewick pared all that down and said use this if you are doing this, and use this other thing if your going to be doing this.

Even if you aren't using C, I recommend "Expert C Programming: Deep C Secrets" by Peter van der Linden. It is simply the best programming book I have ever read. Clear, funny, and full of explanations of all those things that aren't explained in classes or other books that have you

If you can use C++ I recommend the STL

[Progman3K]

No need to keep re-coding hasing lists when you have access to generic algorithms.

Are you trying to code a linked-list, or are you trying to solve a problem?

Re:

[Progman3K]

D'oh! I meant 'HASHING'

Dang kybard!
*Yes, that's a Dilbert reference*

Re:

[91degrees]

STL is great, but it's a bit of a resource hog. And kernel programmers are real misers (not to mention control freaks) when it comes to resources.

Re:

[slcdb]

C++ in a kernel? Sweet mother of God! Please don't do it! :D

Re:

[joto]

C++ in a kernel? Sweet mother of God! Please don't do it! :D

Why not? It's not like you have to use STL, MFC, multiple inheritance, and covariance just because you happen to use C++. C++ offers several advantages over C, and which features you decide to use, and where, is up to you. C is not perfect. There's little reason to stick to it, except tradition. C++ certainly isn't perfect either, but it has some advantages over C.

Unix succeded pretty much because it was one of the first OS-kernels that was not

Re:

[Henry V .009]

I'd recommend taking a look at the book Efficient C++ for a set of benchmarks comparing the STL to handwritten code.

Re:

[mdf356]

I'm looking for more tools. I know of the fundamentals of basic data structures, but some problems come up requiring fast operations that don't fit any of the basic structures. I'm hoping to avoid reinventing the wheel if I don't need to. Thanks, Matt

Re:

[cheezit]

In many cases, pairing basic data structures can give you the behaviors you want, without introducing a complex and obscure structure. For instance, if you need a structure with stack push/pop, enforced uniqueness, and that you can search in constant time, pairing a stack and a map gives you those behaviors with constant insert time. The insert/remove time may be double what it would be if you were to use a single structure, but as it is constant it will be efficient over large data sets.

As far as structu

Okasaki book

[philgross]

A few years ago, I took Chris Okasaki's "Advanced Data Structures" course at Columbia. Looking at the Wikipedia Data Structures article [wikipedia.org] others have mentioned, it's pretty good, but doesn't include, e.g. Pairing Heaps, which have excellent real-world performance. You might want to check out Chris's book Purely Functional Data Structures [amazon.com] (ISBN 0521663504). Even though you're not working with a functional language, it's a good catalog of some recent data structures, and from what I saw in the class, he unde

Link lists?

[tedgyz]

You use linked lists in your kernel?!?

Re:Link lists?

[aligature]

Linked lists are not necessarily a poor choice for a data structure. The cost of adding and removing elements from a balanced binary tree is completely wasted when you only need to add or remove from the beginning or end of a list. A linked list is a perfect data structure for a fifo or deque. All data structures have their advantages and disadvantages; your choice should depend entirely on your requirements.

Re:

[tedgyz]

I was implying that he would be using fixed-sized arrays. :-)

Re:

[revlayle]

Well, that's hardly a linked list then, is it?

Re:

[tedgyz]

To fully clarify my satire - I was feining shock that an "advanced" structure like linked-list exists in the kernel.

Re:

[mdf356]

We do a lot with fixed size arrays, yes. But sometimes the elements are chained together with indices.

The great thing about programming for the virtual memory manager is that arrays that take up a few TB aren't wasteful of anythig except effective address space. :-)

Cheers,
Matt

Re:

[jack_csk]

Why are you surprised? He just forgot to tell you that he's working in Redmond, WA.

Re:

[tedgyz]

But it would be debatable if any true "kernel" development occurs in Redmond. Most kernels I know don't bind in MediaPlayer. :-)

Re:

[AlastairMurray]

It has been years since I actually looked at the code, but certainly back in the 2.4.x days the Linux kernel scheduler made use of linked lists (along side some clever pointer arithmetic that made for interesting reading.)

Re:

[supermank17]

There are situations where linked-lists are useful in the kernel. I certainly remember using them occasionally back in my OS class from days gone by, and I also remember seeing them in Linux kernel code.

Re:

[Patrik_AKA_RedX]

Not just linked lists. Even ... GOTO's.

Just kidding... You can stop having a hearth attack...

Re:

[Sancho]

Go read some kernel code sometime. There are many more GOTO statements than you think.

Re:

[tedgyz]

Go read some kernel code sometime. There are many more GOTO statements than you think.

The horror! The horror!

In the object-oriented, application world, if-then-else is the new GOTO. Most if's I see today could be replaced with inheritance.

Re:

[lgw]

GOTO is still the right way to exit multiply-nested loops, if there's no clean way to use RETURN instead.

Re:

[thesnide]

It's actually quite useful to have a proper exception handling scenario, in order to release things nicely. In a language like C you don't have a destructors, so you have to implement yourself.

Using GOTO can be useful to "linearise" the execution flow such as in :

int foo()
{
// Acquire resource A
A* a = allocate_a();
if (a == NULL) {
goto ERROR_A;
}

// Acquire resource B
B* b = allocate_b();
if (b == NU

Re:

[tedgyz]

I was being sarcastic.

Re:

[tedgyz]

It was sarcasm. Back in the day, kernels mostly used fixed-size arrays. I guess I'm showing my age.

KISS!

[Just Some Guy]

Tarjan's Data Structures book looks like it has potential, but seems focused on network algorithms, which are unlikely to be applicable to the kernel programming I do.

WTF? People who try to move cleverness in low-level critical code should be shot. Look, there's a time and a place for everything, but this is the wrong approach for the problemspace you're working in. You didn't say which kernel you're working with, but odds are extremely good that it already comes with a set of pre-defined macros or functions for handling data structures. Use them. They're much better tested and understood than the stuff you want to play with, and much less likely to make your codevelopers hate you.

I don't want to be a stick in the mud, but seriously, this just isn't the place to start experimenting.

Re:

[mdf356]

The issue comes when no existing data structure I can think of meets the performance requirements of some new feature. I'd like to not reinvent the wheel. Thanks, Matt

Re:KISS!

[Mr2cents]

Wikipedia has a nice collection of data structures. Maybe that's what you're looking for?

http://en.wikipedia.org/wiki/List_of_data_structur es [wikipedia.org]

Re:

[cmburns69]

The difference in the data structures is often like the age-old saying "It can be cheap, high quality, and fast. Choose two." For some problems, there can't be a data structure that has all the benefits and none of the tradeoffs...

Out of curiosity, what problem are you trying to solve that is not covered by an existing data structure?

What are you missing?

[thsths]

> I'd like to have more in my toolbox than hashes, linked lists, heaps and various binary and n-way trees.

You forgot arrays (very useful!), but maybe that is just too trivial. Anyway, what exactly are you missing? Most problems I know can be solved using these basic data-structures, or a combination thereof.

If you really want to, you can actually get by with just one data-structure:

Lisp uses only nested linked lists, that can be interpreted as binary trees.

Perl only really knows hashes. Arrays and lists

Re:

[mdf356]

The big-O time of operations is very important. With the large volume of data an OS has to keep track of, O(n) is unacceptable, and even O(lg n) is sometimes unacceptable for some routines. The kernel coders never get spoiled by convenient languages because we're still writing in C so we can completely control resource usage. Thanks, Matt

Re:

[kalirion]

In cases where O(lg n) is unacceptable, aren't you pretty much stuck with either an array or a hash-based structure?

Re:

[Anonymous Coward]

Yeah, you pretty much eliminate all tree structures, and hence all graphs structures, once you demand better than O(lg n) performance.

The only way to improve on this in slower data structures is to use radix-style keying to cheat, so that your lookup keys tell you exactly how to find the value you're looking for. But this isn't really an "advanced" data structure, just an optimization of a basic one. (In fact, a lot of "advanced" data structures are just such application-specific optimizations; radix keyin

Re:

[try_anything]

In cases where O(lg n) is unacceptable, aren't you pretty much stuck with either an array or a hash-based structure?

It depends on which operations have to be O(lg n). Operations that don't traverse the entire structure can be more efficient.

Re:

[0xABADC0DA]

I find it fascinating that a kernel developer would be concerned with O() rather than the actual runtime. I thought kernel developers in general just put an arbitrary upper bound so their "O(n^2) && n -lt 1024" was faster than the "O(log n)" for any n.

Now if what you are actually looking for is some fun how about embedding neko [nekovm.org] in the kernel, because while you can add some cool things like say tries (prefix trees) the real performance bottleneck is between apps and the kernel. Neko could safely ca

Re:What are you missing?

[Greyfox]

If you really want to, you can actually get by with just one data-structure:

And most programmers do. Read some code out in the industry and you'd think that 90% of the programmers out there never took a data structures class. Even if you're using a language like Java or C++ you really should know the implementation details of each so you can make informed decisions about the trade-offs in performance and maintainability. If you can't visualize the layout of your data and how you'll be accessing it, you really won't be able to pick the best structure for the job (Or roll your own if none of the usual ones fit.)

I can't think of a C project I've worked on where I didn't have to write a basic data structure like a stack or a linked list. On a couple of them the programmer passed data around as char data and used offsets to get at the data in them. On one, the programmer didn't even know about structs (Or null string termination.)

Having a "Convenient" language really isn't much of an excuse for not knowing this stuff. My data structures prof deliberatly chose an inconvenient language (BASIC) to show data structure implmentations. You can implement any structure in terms of array if you have to.

It'd be nice if more programmers would actually put some thought into their code before they go and start writing stuff. I wouldn't seek to discourage that...

byte-order independence

[fortunatus]

On a couple of them the programmer passed data around as char data and used offsets to get at the data in them.

Although mentioned in a negative light,

This technique is important when you have to move data between big-endian and little-endian processors. It lets you write portable I/O routines.

Re:What are you missing?

[mschaef]

"Lisp uses only nested linked lists, that can be interpreted as binary trees."

As much as people keep saying it, this is totally false... Common Lisp does not even have lists as an intrinsic type. What it does have are cons cells, several kinds of numbers, symbols, characters, strings, several kinds of vectors and arrays, hash tables, structures, instances, and lexical closures among other types native to the language.

Lists are to Lisp what Strings are to C: a convention built upon more basic structures. In the case of C, a string is a convention built up on null terminated arrays of characters. In the case of Lisp, a list is a series of chained together cons cells.

Re:

[Captain Segfault]

Common Lisp does not even have lists as an intrinsic type. What it does have are cons cells...

A list is typically just a value and another list. A cons cell *is* a list that just happens to support some extra operations.

Re:What are you missing?

[thsths]

> As much as people keep saying it, this is totally false... Common Lisp does not even have lists as an intrinsic type.

Funny how LISP stands for LISt Processing. And this thread is about data structures, not data types. The cons cell might be the central data type in LISP, but the nested list is the central data structure.

Just think about it. '(a b c) will be recognised as a 3 element list by any LISP programmer, and not as 2 cons cells plus 3 atoms (which would be equally correct). Now you can also construct binary trees with cons cells, but that is more complicated and therefore a bit rare.

Thomas

Re:What are you missing?

[mschaef]

"Just think about it. '(a b c) will be recognised as a 3 element list by any LISP programmer, and not as 2 cons cells plus 3 atoms (which would be equally correct). "

Actually no... it's 3 cons cells. The syntax (a b c) is shorthand for (a . (b . ( c . ()))). This kind of misunderstanding is precisely why any competent (key word) LISP programmer understands the difference between lists and cons cells I was referring to in my original post. The closest structure with only two cons cells is this (a b . c).

Now, As long as we're being pedantic, what you actually wrote, '(a b c), is shorthand for (quote (a b c)). The numbers of cons cells and atoms in that case is a 'exercise for the reader', but suffice it to say that both your numbers are wrong.

Re:

[mschaef]

"you just made yourself look like an ass."

Dude, I was arguing on Slashdot about the number and proper usage of data types in Lisp, of all things... I think looking like an ass was pretty much a part of the deal from the get go.

Re:

[HalWasRight]

I think looking like an ass was pretty much a part of the deal from the get go.

But you wear it so well!

Based on your argument C doesn't have arrays, just pointers with some syntactic sugar.

Re:

[mschaef]

"But you wear it so well! "

Well, we're all 'special' in our own unique ways. :-)

To be frank, I wouldn't have been quite so harsh (ass-like, if you wish) if he hadn't just happened to make one of mistakes that proved exactly my point about the difference between cons cells and lists.

"Based on your argument C doesn't have arrays, just pointers with some syntactic sugar."

I'd actually agree with that.... A bit of trivia: in C, what's the difference between a[b] and b[a]? ...... Nothing, they are semantically eq

Re:

[mschaef]

"But you haven't let that stop you."

So you posted to let me know that I was posting in spite of the fact that, as I posted, the original poster was no longer posting. Does that about sum it up?

Lewis & Denenberg

[pedantic bore]

"Data Structures and Their Algorithms" by Lewis and Denenberg.

Not an encyclopedia, like CLR(S) or Knuth, but rather a tutorial of many useful data structures and algorithms. Doesn't have the breadth of the "encyclopedic" books but what it covers, it covers very well.

The drawback of this book, from your perspective, is that it isn't C-specific. It's usually transparent how to translate the code into C (or anything similar) but you can't just paste it into your code.

Red-Black Trees Not Good Enough?

[tecnopa]

What type of "advanced data structures" are you alluding to? I cant imagine needing anything more complex than say, red-black trees , in kernel development.
And as someone already pointed out, use the predefined macros. Failing that you can always check out
http://lxr.linux.no/ [linux.no]
And to who ever made the comment about using lists in kernel source... *sigh* probably not worth it.

Re:

[mdf356]

For example, someone earlier reminded me of the Trie data structure. I haven't see it in 5 years so I'd forgotten about it. The existence and my forgetting of the Trie means there's other things I've forgotten or never learned that could be useful to solve some future problem.

There have been times when red-black trees are too expensive, because they have 2 pointers per node and I can't afford the memory overhead. It's amazing how much memory gets wasted when you add an 8 byte pointer to a 0x10 byte struc

Re:

[thsths]

> There have been times when red-black trees are too expensive, because they have 2 pointers per node and I can't afford the memory overhead. It's amazing how much memory gets wasted when you add an 8 byte pointer to a 0x10 byte structure that can have over 2^35 instances.

Too expensive is relative. You can optimise most of the overhead away, but you still have to store 0x10 byte per structure. Investing a lot of work just to reduce the memory usage by 30% is *usually* not worth it, although there are cer

Re:

[ThosLives]

Eh, that only works if you're traversing the list, not if you can possibly jump into the tree from a direct pointer to the object.

Of course, for things where you really only always just traverse the list, this would be fine...an interesting concept actually. Guess it's another instance of "use the correct tool for the task at hand."

Computer Algorithms / C++

[gregor_jk]

I was taught Computer Algorithms / C++ by Horowitz, Sahni and Rajasekaran( I believe they have a pseudocode version) and it was great. The seemed to be a perfect balance between the implementation and the ideas behind them.

"patterns"

[peter303]

"Patterns" is a taxonomy of class types which frequently recur in object-oriented programming such a C#, Java, and C++. Classes which capture data state are pretty straight forward to work out. But its less clear how to organize classes which are more functional or control in nature and components of large software systems. Thats where the identification and study of class patterns is useful. There have been a dozen books on the subject.

Data Structures and Algorithms

[kjhambrick]

Data Structures and Algorithms (ISBN 0201000237) by Aho, Ullman and Hopcroft is a classic that belongs on every programmer's bookshelf (hell, keep it on your desk!).

Re:

[myatmpinis1234]

We used this book in my data structures class. Not surprising since the prof was Aho. In one of our exams he asked us to design an algorithm to determine the longest path between two points in a graph. You have to be a real SOB to assign an NP-complete problem as your exam. He is quite a character. Anyway, I guess this is not relevant, but it brings me back to the good old days before corporate slavery.

Re:

[MarkusQ]

You have to be a real SOB to assign an NP-complete problem as your exam.

Be grateful he was asking you to design it and not execute it.

--MarkusQ

P.S. For that matter, it should be pretty easy to design an algorithm that does this, based around a wave front (work out from one end, kill all paths when they reach the other end, unless there is only one, which is the longest).

Re:

[HuguesT]

Your longest path algorithm won't work, you may have a cycle in your graph and your remaining path will never reach the endpoint. The algorithm will not terminate.

Re:

[MarkusQ]

Your longest path algorithm won't work, you may have a cycle in your graph and your remaining path will never reach the endpoint. The algorithm will not terminate.

My parenthetical comment was just a sketch; obviously (by the usual meaning of "longest path") you wouldn't ever use the same arc twice, so cycles don't matter.

--MarkusQ

Network algorithms

[coyote-san]

Network algorithms are useful in an astoundishing number of places, especially in those cases where all flows are either 0 or 1. You just need to expand you idea about what the networks and flows represent.

E.g., my professor used network algorithms when writing the software that matches medical schools and students. Each school prioritizes it's candidate students, each student prioritizes his schools. The program finds the best matches. He said it had taken many hours (12 hours?) to do originally, but with the network flow it was a few minutes on an old kaypro.

Another example was determining when teams are mathematically eliminated from playoffs. It sounds like a simple problem, but it isn't since a team could lose a game yet remain in the running because a different team lost its own game.

A decade ago these algorithms would be overkill for a kernel. Today... I can definitely see how these algorithms could make a difference in some places.

Re:

[edwdig]

Another example was determining when teams are mathematically eliminated from playoffs. It sounds like a simple problem, but it isn't since a team could lose a game yet remain in the running because a different team lost its own game.

Why is that hard? I was wondering how baseball magic numbers were calculated recently, and it only took me about 2 minutes to figure it out.

Magic Number = Games in Season - Wins by First Place team - Losses by 2nd place team + 1

As long as that is above zero, the 2nd place team

Re:

[Miniluv]

That only addresses a simple case where the higher ranked team of the two you're comparing goes. Now imagine you've got three divisions of which the winner advances. Then imagine those three divisions are in a league where the best record that didn't win a divisional title advances. It gets even more complicated when advancement isn't strictly based on record but instead a point system (like the NHL) where ties and certain types of losses still generate points.

We'll not even mention tie breaker rules that m

Amazon referer

[Beached]

I wonder how much he is making from refering the books on amazon (4% of X sales from slashdotting) ?

Good idea, wish I thought of it first.

Really advanced data structures...

[Bender0x7D1]

If you are looking for the best/craziest/most efficient data structures out there then you need to go through some of the computer science journals. It can be a royal pain to crawl through them looking for what you want, but that's where you will find all the "advanced" data structures. They also provide all of the information on how to use them, behavior, best uses and performance information on those structures, (including proofs if you care).

If you are just looking to refresh your memory, or learn a

Algorithms and Data Structures in C++

[tedgyz]

"Algorithms and Data Structures in C++", by Leendert Ammeraal, Wiley, 1996. [barnesandnoble.com] It is the only book I found that has good coverage of Tries.

Judy Arrays

[r00t]

They aren't really arrays, but rather trees. They are really nice. They are cache-friendly without needing to be tuned for a particular size of cache.

If you make a few macros or inline functions for them, then using them everywhere becomes practical.

A complete book online for free

[exp(pi*sqrt(163))]

Purely Functional Datastructures [cmu.edu] by Okasaki.

Tomes of delphi

[abradsn]

I've read many (around 15) data structures and algorythms books. Here is the best one that you will still be able to get in print: Tomes of delphi: algorithms and data structures Julian M Bucknall It covers advanced structures and walks you through improvements on algorythms. Basically it teaches you why and how some algorythms are most suited to various situations. Also, since it is in Pascal it is usually easier to port the code to more modern languages than C. The only drawback in this book is its b

The Handbook of Algorithms and Data Structures

[scc]

"The Handbook of Algorithms and Data Structures" (in Pascal and C) Second Edition, by G.H. Gonnet and R. Baeza-Yates, ISBN 0-201-41607. It's a compact reference and analysis of a pretty broad range of algorithms. I also strongly second some of the other suggestions above such as Sedgewick, and Aho, Hopcroft, and Ullman. "The Stanford GraphBase" by Knuth, ISBN 0-201-54275-7 is great, though focused obviously. Beyond the basics, you'll end up looking in very specific books, such as "Text Compression" by B

The Algorithm Design Manual

[cjitlal]

'The Algorithm Design Manual' by Steven Skiena at Stony Brook is a very pragamatic book for intermediate data structures and algorithms. This is a definitely aimed at the practitioner who must get something up and running, without having to worry about big-Oh notation etc. There's an online version of the book [toki.or.id] but it's just so good, I'd recommend that anyone who needs this information, snap up a copy. Skiena also maintains The Stony Brook Algorithm Repository [sunysb.edu] It's a treasure, as it includes implementat

Goodrich and Tamassia

[NNland]

Goodrich and Tamassia have a good general algorithms book. It's much shorter than CLRS, but it is also significantly more readable. They also have an "Algorithms in C++" and "Algorithms in Java" variants coauthored with others that have fairly substantial code samples.

Algorithm Design Manual

[psykocrime]

The Algorithm Design Manual [amazon.com] is pretty good.

Handbook of Algorithms and Data Structures

[functor0]

Try also the Handbook of Algorithms and Data Structures:

http://www.amazon.com/Handbook-Algorithms-Data-Str uctures-Pascal/dp/0201416077/sr=8-1/qid=1160102805 /ref=sr_1_1/102-2768899-0462565?ie=UTF8&s=books [amazon.com]

quit trying to be clever

[NateTech]

If you barely understand it and have to look it up in a book, you're doing the next guy to work on your code (and your organization) no favors.

Make stuff ONLY as complex as it NEEDS to be. That's the job of a good engineer.

If you're bored, perhaps you're struggling with the fact that 80% of what is done with computers today ONLY requires linked lists, hashes, and that dull "generic" stuff to get the job done.

No need to build the Golden Gate Bridge to span the 10 foot wide creek in your back yard. In fact,

MOD PARENT UP

[Traf-O-Data-Hater]

Agree entirely. Most of the code you'll encounter in your working career _will_ require the same "boring" structures, certainly in the business and financial sector. That's been my experience in 18 years of coding C, C++, C# and others. Yes I think Design Patterns are neat like everyone else and have used a few myself, but as the parent says you are not doing anyone else a favour if you've just included them for the sake of it, especially if you are retrofitting them into the bulk of existing code that happ

Book reviews

[alexo]

Look at the ACCU book reviews [accu.org], preferably by subject [accu.org] for books on Algorithms [accu.org] and Data structures [accu.org] (there's a lot of overlap).

Judy Arrays

[sgowkanapalli]

I have had enough of the hashes and B-trees.. Any thoughts on Judy arrays http://judy.sourceforge.net/ [sourceforge.net] I think it is an interesting concept.. There are some concerns about it at http://www.nothings.org/computer/judy/ [nothings.org] . I think the concept it good.. Do you think it is a feasible solution for a highly scalable data structure?

Flamebait or fact

[passionplay]

At the risk of sounding like I'm trying to start a flame war, let me be the first to say how stupid it sounds for an intelligent person that has not READ a book to call it TOO basic for something like kernel programming.

Sounds to me like you're looking for a cookbook. Not to learn. Programming is an art and a science. You have to learn how to walk before you run and run before you fly. You cannot become a kernel programmer just by learning only those things you THINK are needed to program a kernel.

That's li

Algorithm Design

[dyamkovoy]

I have the Kleinberg/Tardos book for one of my classes. You're right, it is pretty basic -- it does not really go into implementation, it is more about the theory behind certain algorithms and proving that they work. If you are looking more for different approaches to certain problems, and suggestions about implementing them, I would not suggest this book.