Papers we love Barcelona is back and we already have a list of amazing talks for the next months. The events will alternate between noon at the University and evenings at some company to be sure that everyone can attend and bridge t

he gap between academia and the industry.

This month’s talk is going to be:

Searching with Dices: a survey on randomized data structures by Conrado Martinez (https://www.cs.upc.edu/~conrado/).

Slides of the talk: https://drive.google.com/file/d/0B2Eb2dCEJBHQNHNGcDhLNjAwZ3Bnck1tU3JaR1lRcHM1U1pv/view

The usefulness of randomization in the design of algorithms has been known for a long time (Rabin’s primality test or Karger’s algorithm). Randomized algorithms usually yield algorithms which are simple, elegant, with guaranteed expected performance and practical.

Not many people know about why they work (theoretical basis) or how to analyze these algorithms. In this talk Conrado Martinez will explain two well-know data structures: Skip-lists (https://en.wikipedia.org/wiki/Skip_list) and Randomized binary search trees (https://en.wikipedia.org/wiki/Treap#Randomized_binary_search_tree). We will grasp the basic idea of those data structures and the speaker will provide us the tools for analyzing those kind of data structures.

The two papers of this event are:
– Skip

lists: http://www.epaperpress.com/sortsearch/download/skiplist.pdf
– Randomized Binary Search Trees: https://cis.temple.edu/~wolfgang/cis551/martinez.pdf

This is an event organized by the UPC ACM Student Chapter for more information https://upc.acm.org . If you need anything you can contact us at student.chapter@upc.acm.org.

• What to bring
You don’t need to bring anything especial for this meetup.

• Important to know
Reading the papers is not a must but you should come in an open minded mood 🙂

We have a code of conduct (https://github.com/papers-we-love/barcelona/blob/master/code-of-conduct.md) and everyone HAS to follow it. The rules are very simple: Be an adult, don’t be a jerk.


Leave a Reply

Your email address will not be published. Required fields are marked *