## General

This seminar will offer a glimpse at current frontiers in data structures
research. The main activity will be in-depth examination of recent articles
from leading algorithms and data structures venues, such as SODA, ICALP,
and ESA.

This is a seminar course, so there won't be any formal lectures.
However, everyone is encouraged to watch (most of) the taped lectures from
Eric Demaine's course at MIT
(http://courses.csail.mit.edu/6.851/spring12); you can skip Lectures 2, 5, 6 and 22.

## Assessment

There will be two pieces of assessment, due at the end of each teaching period (16.10 and 04.12).

### Assignment 1

The first assignment (**due 16.10**) is to summarize a broad topic in data structures,
providing an introductory overview and list of key references and results. You can use Demaine's
lectures as a guide to these topics, but you're expected to do more than just rewrite the course
notes.

Some possible topics are: Persistence, Succinct Data Structues, Graphs, Computational Geometry,
Hashing, External Memory Data Structures, and Data Structures for Integers. Note this is not by any
means an exhaustive list. Note also that some of these areas are very broad, so you're allowed to
pick narrower subtopics where reasonable.

Your eight to 10 page summary will be peer-reviewed by two other students (put another way,
you will review the summaries of two other students, and provide feedback).

**Selection of topics.** You will spend the first two weeks deciding on your topic. You
should **email your preferred topic to us by 16.09**. If necessary we will then meet on 18.09
to resolve any collisions. Some overlap between students may be allowed (maximum two students
on one topic), but students must write separate reports, and should work on difference aspects
of the topic.

### Assignment 2

The second assignment (**due 04.12**) is to read, digest, and understand a recent piece of data
structures research. This should be an article from a recent conference or journal.
Here is a list of suggested articles to choose from, however you're free
to choose something not on the list, provided you run it past us first.

Assessment will be based on a 30 minute presentation you will give on the paper
you selected (including time for questions). The date of the presentations will be
**04.12**, possibly in a different venue to C220 (TBA). You must **nominate the
article you will present no later than 13.11**. In your presentation you should
provide necessary background and motivation for the topic, and then communicate the
key ideas and results of the article. You should try to make your presentation accessible
to everyone in the course.

Use of visual aids, such as slides or the
blackboard, is allowed. You are also free to gather results beyond those presented
in the article to aid your presentation (e.g. by implementing the data structures
and running experiments), but this is not a strict requirement.

### Suggested Approach

Though not compulsory (or even necessary), it might be a good idea to pick your broad
topic so that it helps you with your article. Spend the first couple of weeks purusing
Demaine's lectures and settling on a topic. At the same time, examine the articles and
try to find a handful that fit into one of the broad areas you find interesting.

## Talk Schedule

**27.11.**

**12:15-13:45**

Juho Stenudd

Confluent persistence revisited
Sebastien Collette, John Iacono, and Stefan Langerman
SODA, 2012

Junlong Xiang

On the weak prefix-search problem.
Paolo Ferragina
Theor. Comput. Sci. 483: 75-84 (2013)

**14:15-15:45**

Jussi Kokkala

On Cartesian Trees and Range Minimum Queries
Erik D. Demaine, Gad M. Landau, Oren Weimann
ICALP 2009

Aleksi Hartikainen

Top-k document retrieval in compact space and near optimal time
Gonzalo Navarro, Sharma V. Thankachan
ISAAC, 2013

Heikki Aitakangas

Practical perfect hashing in nearly optimal space
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani
Information Systems, 2013

**4.12.**

**12:15-13:45**

Timo Koivisto

Set-Difference Range Queries
Joseph A. Simons, David Eppstein and Michael Goodrich
CCCG, 2013

Peter Hedman

Maximizing parallelism in the construction of BVHs, octrees and k-d trees
Tero Karras
Proc. High Performance Graphics, 2012

Jani Rahkola

Succinct data structures for representing equivalence classes
Moshe Lewenstein, Ian Munro and Venkatesh Raman
ISAAC, 2013

**14:15-15:45**

Matthew Pierce

Theory and practice of monotone minimal perfect hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna
Journal of Experimental Algorithmics, 2008

Daniel Valenzuela

Fingerprints in compressed strings
Philip Bille, Patrick Hagge Cording, Inge Li Gortz, Benjamin Sach, Hjalte Wedel Vildhoj and Soren Vind
WADS, 2013

Dominik Kempa

Inducing Suffix and LCP Arrays in External Memory
Timo Bingmann, Johannes Fischer and Vitaly Osipov
ALENEX 2013

Qijia Zeng

Tight bounds for sliding Bloom filters
Moni Naor, Eylon Yogev
arXiv, April 2013