Name: Searching with Dice: Skip lists and Randomized Binary search trees
Start: 2018-02-28T12:00:00+01:00
End: 2018-02-28T14:00:00+01:00
Location: Campus Nord UPC

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

Jordi Montes

Papers We Love - Barcelona

Technology

Data Science

Open Source

Software Development

Computer Science

Machine Learning

Researchers

Mathematics

Academics

Searching with Dice: Skip lists and Randomized Binary search trees

Campus Nord UPC

Share

Papers We Love - Barcelona

Searching with Dice: Skip lists and Randomized Binary search trees

Papers We Love - Barcelona

Details

Members are also interested in