Friday, December 05, 2008

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.

8 Comments:

Blogger Melvin said...

This comment has been removed by the author.

5:21 PM  
Blogger Melvin said...

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/

5:24 PM  
Anonymous D. Eppstein said...

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.

5:59 PM  
Anonymous Anonymous said...

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

8:57 PM  
Blogger edward said...

>> 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)! :-)

6:29 PM  
Anonymous Anonymous said...

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

8:49 PM  
Anonymous Anonymous said...

kurt mehlhorn's books might be relevant here...

12:26 PM  
Blogger deep said...

phd@deep (visitor)

http://www.gdeepak.com


Computer Science field has a bright future.

11:46 PM  

Post a Comment

<< Home