Slashdot Mirror
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?"
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.
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.
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!).
Wikipedia has a nice collection of data structures. Maybe that's what you're looking for?
r es
http://en.wikipedia.org/wiki/List_of_data_structu
"It's too bad that stupidity isn't painful." - Anton LaVey
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.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
"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.
A few years ago, I took Chris Okasaki's "Advanced Data Structures" course at Columbia. Looking at the Wikipedia Data Structures article 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 (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 understands them at a very deep level.
Purely Functional Datastructures by Okasaki.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
> 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
"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.