*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
1

**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!

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

**List of Topics**

**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 Tree**s
-- (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.