Advanced Data Structures Seminar

Fall 2009

Instructor: Nir Shavit

 

Important information: Eight students showed up to the first meeting during which we selected the topics. Additional students wishing to join the seminar must send me email. Our 1st presentation will be on Sunday the 1st of November with a lecture on Cuckoo Hashing by Dima Shevelev. See you then.

Seminar Goals

This seminar  is intended to educate graduate students in understanding the relation between the theoretical and practical algorithmic aspects of designing data structures. Many students, when finally arriving in the workplace, see that the accepted norm is to avoid using ``sophisticated'' state of the art structures and instead use ``simpler'' structures, many times at the price of a performance decrease. Is this phenomena justified?

This seminar will attempt to give students a better understanding of the issues raised by such questions.

Seminar Methodology

The students will split into groups of 2 or 3 and prepare presentations on the selected topics. The students are required to deliver a presentation on the topic to the class. The class homepage will contain one reference pointer to the material on the topic, but it is the student's responsibility to search for related papers and know the related bibliography! 

Web Contents

Minhala page. Please register your email with Nir Shavit (see minhala page).

 

List of Topics

 

  1. Cuckoo Hashing (paper) (Dima Shevelev)

            Rasmus Pagh, Flemming Friche Rodler  Cuckoo Hashing (2001)  Lecture Notes in Computer Science.

2.      Skip-lists (Ron Visbord) Skip Lists: A Probabilistic Alternative to Balanced Trees (1990)  William Pugh Workshop on Algorithms and Data Structures

3.      Splay Trees  (Hadar Weiss) "Self-adjusting Binary Search Trees", Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686.

4.      Pairing Heaps --  (Adi Haviv) "On the efficiency of pairing heaps and related data structures", Michael L. Fredman, Journal of the ACM (JACM), 46(4), pages 473--501, 1999.

5.      Finger Search Trees (Elad Moshe) L. J. Guibas, E. M. McCreight, M. F. Plass, and J. R. Roberts. A new representation for linear lists. In Proc. 9th Annual ACM Symposium on Theory of Computing, pages 49--60, 1977 and Handbook Of Data Structures And Applications, Dinesh P. Mehta and Sartaj Sahni editors, Chapman & Hall/Crc Computer and Information Science Series 2004 pages Chapter 11.

6.      Bitonic Sorting Networks (XXXXXXX) Kenneth E. Batcher: On Bitonic Sorting Networks. ICPP (1) 1990: 376-379 and CLRS Chapter 27.

7.      Optimal Alphabetic Trees  -- (Rotem Shaul) A. Garsia and M. Wachs. A new algorithm for minimum cost binary trees. SIAM Journal on Computing, 6(4):622--642, 1977 or in the Handbook Of Data Structures And Applications, Dinesh P. Mehta and Sartaj Sahni editors, Chapman & Hall/Crc Computer and Information Science Series 2004 pages 14-13 to 14-16.

8.      Quadtreees  -- (Yuval Kesten) A. Klinger. Pattern and search statistics. In J.S. Rustagi, editor, Optimizing Methods in Statistics. Academic Press, 1971 or Samet Samet H. Applications of spatial data structures: computer graphics, image processing, and GIS. Reading, MA: Addison-Wesley, 1990. or the Handbook Of Data Structures And Applications, Dinesh P. Mehta and Sartaj Sahni editors, Chapman & Hall/Crc Computer and Information Science Series 2004 pages
19-1 to 19-26.

 

Last updated on the 19th of October 2007 by N.S.