Data Structures Inc.
I just finished teaching the graduate algorithms course (finals and grading still to go). I had an ambivalence towards data structures and did not really teach any interesting material: students know balanced search trees & heaps, I did teach hashing, but is that data structures? I did not teach skip lists, suffix trees, LCA, van Emde Boas, self-adjusting DS, persistence, fusion trees , ... Question is, are such data structures core to a graduate algorithms course? Any advice will be welcome for the future.
On a related note, someone asked me recently if I know of a good book on advanced data structures. I can point to a wonderful set of lecture notes from Erik Demaine's class. Together with Mihai's BAM future notes, we may get a good picture of the area of data structures.
On a related note, someone asked me recently if I know of a good book on advanced data structures. I can point to a wonderful set of lecture notes from Erik Demaine's class. Together with Mihai's BAM future notes, we may get a good picture of the area of data structures.
posted by metoo at 3:52 PM
7 Comments:
This comment has been removed by the author.
Have you seen the book "Advance Data Structures" by Peter Braß? There is a public release on his homepage at http://www-cs.ccny.cuny.edu/~peter/
Hashing is data structures, yes. When I cover it in the graduate data structures class, I try to include something about the worst case query times for hash chaining and open addressing, schemes for improved worst cases such as robin hood hashing, and a little bit about controlling the amount of randomness you need in the hash functions to make the algorithms work.
See the link on my name for my syllabi. Other topics I've included are amortized analysis, priority queues, binary search data structures, multilevel data structures, geometric range search problems, least common ancestors, van Emde Boas trees, persistence, and union-find.
I'd be interested to see what comments you get here since I'm teaching the course again next quarter. I've had a difficult time selecting a textbook for the course (Tarjan's little book is good but hard to find and covers only an idiosyncratic subset of topics, CLRS misses too many important data structures); I'll take a look at Brass's one as well in hopes that it's better.
Hi David: I like the syllabus for the Data Structures course (f.c: forgot about that beautiful stuff), am curious what subset one will retain for an Algorithms course.
Hi Melvin: Thanks for the ref to the "Advance Data Structures" book.
-- metoo
>> Question is, are such data structures core to a graduate algorithms course?
In my opinion, they are not core to a graduate course, but I think they fit well an advanced algorithms course.
If there's no such advanced course, and you are willing to present them, another good alternative is to give the students the chance of researching and presenting such algorithms as a final project by the end of the course.
PS: I would love to read a book with all these topics (skip lists, suffix trees, LCA, van Emde Boas, self-adjusting DS, persistence, fusion trees, etc)! :-)
Hi Edward, Why do you think these data structures are not core to a graduate algorithms course? I am sorta struggling with that Q ..
-- Metoo
kurt mehlhorn's books might be relevant here...
Post a Comment
<< Home