Schedule for Complexity of Data Structures

Course Plan

Date	Materials covered
Apr 2	Should tables be sorted? [Y81]
Apr 4	No lecture. Read [B98, pp 182-185] or [D97, chap 9.1].
Apr 9	Hashing
Apr 11	Hashing. [RM, 8.4.1-8.4.3]
Apr 16	Theorem III.2.6 in [M84]. Theorem 6 in [BMRV00]. Theorem 3 in [P01].
Apr 18	Lectures 8 and 11 from [F00].
Apr 23	Section 3 of [BF99]. Supplement: section 17.2 of [J01]
Apr 25	Section 3 of [BF99].
Apr 30	Lecture 12 of [F00]. [A95]
May 2	Section 3 of [H97]
May 7,9	No lectures!
May 14	Skip lists (handout)
May 16	Anna Östlin (Brics, Denmark) speaks on One-Probe Search (in Swedish). Slides. [ÖP02]
May 21	cancelled due to unsolvable scheduling problems
May 23	Priority Queues on the RAM [H97]. See also [AH97, section 3] and [CLR, chap 28]
May 28	Ranked dictionaries and list indexing. [D89]

Apr 9	EitherNotes for Lecture I, ex. 1-3 or [B98, ex. VI.6.8]
Apr 16	Ex 5.
June 20	First dead-line for assignments (dvi, ps, pdf)
August 20	Second dead-line for assignments (dvi, ps, pdf)

Note: Some of you already did Ex 5 from my notes. You needn't do it again for the assignment, it counts.

A95: Arne Andersson. Sublogarithmic searching without multiplication. FOCS 95.
AH97: Susanne Albers and Torben Hagerup. Improved Parallel Integer Sorting without Concurrent Writing. SODA 1992.
B98: Béla Bollobás. Modern Graph Theory. Springer 1998.
BF99: Paul Beame and Faith Fich, Optimal Bounds for the Predecessor Problem, STOC 1999.
BMRV00: H Buhrman, P B Miltersen, J Radhakrishnan, S Venkathesh. Are bitvectors optimal? STOC 2000.
CLR: Cormen, Leiserson, and Rivest. Introduction to Algorithms.
D89: Paul F. Dietz. Optimal algorithms for list indexing and subset rank. WADS 1998.
D97: Reinhard Diestel. Graph Theory. Springer 1997.
F00: Faith Fich. Lecture notes for CSC 2429S.
J01: Stasys Jukna. Extremal Combinatorics. Springer 2001.
H97: Torben Hagerup. Sorting and searching on the Word RAM.
M84: Kurt Mehlhorn. Sorting and Searching. Springer 1984.
P01: R Pagh. On the cell probe complexity of membership and perfect hashing. STOC 2000.
ÖP02: A. Östlin and R. Pagh. One-Probe Search. ICALP 2002.
RM: Motwani and Raghavan. Randomized Algorithms. Cambridge 1995.
T96: Mikkel Thorup. On RAM priority queues. SODA 1996.
Y81: A C Yao. Should tables be sorted? Journal of the ACM, 1981.