5. Dynamic Optimality I

preview_player
Показать описание
MIT 6.851 Advanced Data Structures, Spring 2012
Instructor: Erik Demaine

Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm

License: Creative Commons BY-NC-SA
  1. MIT OpenCourseWare
  2. dynamic optimality
  3. binary search trees
  4. analytic bounds
  5. splay trees
  6. geometric view
Рекомендации по теме
5. Dynamic Optimality 1:22:44

5. Dynamic Optimality I

6. Dynamic Optimality 1:23:31

6. Dynamic Optimality II

Dynamic optimality I 1:22:21

Dynamic optimality I - Advanced data structures

4.6 Optimal Binary 0:30:19

4.6 Optimal Binary Search Tree (Successful Search Only) - Dynamic Programming

4 Principle of 0:14:52

4 Principle of Optimality - Dynamic Programming introduction

Dynamic Programming: Optimal 0:09:12

Dynamic Programming: Optimal Binary Search Trees Part 5

5 Simple Steps 0:21:27

5 Simple Steps for Solving Dynamic Programming Problems

Principle of Optimality 0:09:26

Principle of Optimality - Dynamic Programming

Optimal Control (CMU 1:13:36

Optimal Control (CMU 16-745) 2025 Lecture 2: Equilibria, Stability, and Discrete-Time Dynamics

Lecture 8 | 0:43:40

Lecture 8 | Search 5: A* Optimality, Cycle Checking

3.3 Optimal Merge 0:09:33

3.3 Optimal Merge Pattern - Greedy Method

ESA.5.7 Settling the 0:24:23

ESA.5.7 Settling the Relationship Between Wilber's Bounds for Dynamic Optimality

Problems Without Optimal 0:04:37

Problems Without Optimal Substructure - Dynamic Programming

Dynamic Programming: Optimal 0:07:59

Dynamic Programming: Optimal Binary Search Trees Part 1

Hands-On Reinforcement Learning 0:04:33

Hands-On Reinforcement Learning with R | 5: Dynamic Programming for Optimal Policies

Unlocking Prostate Health: 0:00:58

Unlocking Prostate Health: Transformative 5 Daily Exercises for Optimal Wellness| Health Journey

Optimal Binary Search 0:10:55

Optimal Binary Search Tree

Dynamic Programming V: 0:28:43

Dynamic Programming V: Optimal Allocation Problem.

The optimal speaking 0:00:24

The optimal speaking volume

4.6.2 [New] Optimal 0:57:00

4.6.2 [New] Optimal Binary Search Tree Successful and Unsuccessful Probability - Dynamic Programming

Optimal Binary Search 0:16:05

Optimal Binary Search Trees: Splay Trees (6/6) | Advanced Algorithms - Lecture 10

Principle of optimality, 0:10:54

Principle of optimality, Memoization and Tabulation method in dynamic programming with example

4.3 Matrix Chain 0:23:00

4.3 Matrix Chain Multiplication - Dynamic Programming

4.5 0/1 Knapsack 0:28:24

4.5 0/1 Knapsack - Two Methods - Dynamic Programming

Комментарии
Автор

1:05 - 1:58 central question: is there one "best" BST?
1:58 - 9:30 BST model of computation (more restricted than pointer machine model)
9:30 - 11:23 sequential access property
11:23 - 13:40 dynamic finger property
13:40 - 16:12 entropy property (it is static optimum for BST)
16:12 - 19:38 working set property
19:38 - 24:50 unified property
24:50 - 28:40 dynamic optimality
29:00 - 34:05 conjectured dynamic optimum: splay trees
34:05 - 1:12:17 geometric view
1:12:17 - 1:22:40 greedy algorithm, split trees

PS: he is using "space" instead of "keys" (or key-space) on the axis. for example k3 is smaller than k4.

aleksagordic
Автор

At 30:32, it should be rotate x, rotate x.  Rotating y when y is the root of the tree is undefined.  :/

hyralt
Автор

Here my brain started hurting a bit. I'm confused with the online greedy online algorithm: at each step you have a BST, and key to look up. On the one hand to do it in BST computation model you have to visit all nodes from the root to the node with the key. OTOH you have a geometric view that prescribes which nodes should be visited during this step to make an arboreally satisfied set. How on earth are they going to be the same?

PaulGraphov
Автор

Using 'space' for the other axis is confusing. Why don't you simply write keys?

SaadTaameOfficial