YoVDO

Dynamic Algorithms for LIS and Distance to Monotonicity

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

Tags

Advanced Algorithms Courses Data Structures Courses

Course Description

Overview

Explore dynamic algorithms for Longest Increasing Subsequence (LIS) and Distance to Monotonicity in this informative conference talk. Delve into problem definitions, Patience Sorting, and the dynamic setting before examining previous work and new results. Learn about runtime improvements, grid packing techniques, and an enhanced algorithm for LIS. Gain valuable insights into these fundamental computer science concepts and their practical applications in algorithmic problem-solving.

Syllabus

Intro
Problem Definition
Patience Sorting
Dynamic Setting
Previous Work
Our Results
Improving the runtime
Grid Packing
Improved Algorithm for LIS


Taught by

Association for Computing Machinery (ACM)

Related Courses

Advanced Algorithms and Complexity
University of California, San Diego via Coursera NP-Complete Problems
University of California, San Diego via edX Efficient Zero Knowledge Proof from Interactive Proofs
Simons Institute via YouTube Near-Optimal Decremental SSSP in Dense Weighted Digraphs
IEEE via YouTube Unit Capacity Maxflow in Almost m - 4/3 Time
IEEE via YouTube