Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Nearly Optimal Static Las Vegas Succinct Dictionary

Association for Computing Machinery (ACM) via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore the concept of nearly optimal static Las Vegas succinct dictionaries in this 25-minute conference talk. Delve into the dictionary problem, membership in the Word RAM model, and Patrascu's data structure. Examine data structures with fractional length, succinct dictionary data structures, and the implications of allocating more space for bad inputs. Investigate "random-looking" inputs and the use of two data structures for each bucket. Conclude by discussing open problems in the field. For a more in-depth exploration, access the one-hour version of the talk available on YouTube.

Syllabus

Intro
Dictionary problem
Membership
Word RAM
Patrascu's data structure
Data structures with fractional length
Succinct dictionary data structure
More space on bad inputs
"Random-looking" inputs
Two data structures for each bucket
Open problems

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Nearly Optimal Static Las Vegas Succinct Dictionary

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.