Online List Labeling - Breaking the Log^2 N Barrier
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a groundbreaking lecture on the online list labeling problem, a fundamental concept in data structures. Delve into the challenge of storing a dynamically-changing set of n items in an array of m slots while maintaining sorted order. Learn about the historical O(log^2 n) upper bound for item movements per insertion/deletion and the existing gap between upper and lower bounds for randomized algorithms. Discover a new randomized data structure that achieves an expected O(log^{3/2} n) items moved per operation, breaking the long-standing log^2 n barrier. Gain insights into the collaborative research behind this advancement in dynamic graphs and algorithm design.
Syllabus
Online List Labeling: Breaking the log^2 n Barrier
Taught by
Simons Institute
Related Courses
Natural Language ProcessingColumbia University via Coursera Intro to Algorithms
Udacity Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera Paradigms of Computer Programming
Université catholique de Louvain via edX Data Structures and Algorithm Design Part I | 数据结构与算法设计(上)
Tsinghua University via edX