Past Meetup

Searching with Dice: Skip lists and Randomized Binary search trees

This Meetup is past

32 people went

Campus Nord UPC

C/ Jordi Girona 29 · Barcelona

How to find us

Sala d'actes de la FIB Edifici B6

Location image of event venue

Details

• What we'll do
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.

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

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 [masked].

• 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.