YoVDO

Nearly Optimal Static Las Vegas Succinct Dictionary

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Data Structures Courses Randomized Algorithms Courses Space Complexity Courses

Course Description

Overview

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)

Related Courses

Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera Unpredictable? Randomness, Chance and Free Will
National University of Singapore via Coursera Biology Meets Programming: Bioinformatics for Beginners
University of California, San Diego via Coursera Finding Hidden Messages in DNA (Bioinformatics I)
University of California, San Diego via Coursera Algorithms for Big Data
Indian Institute of Technology Madras via Swayam