Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 13 Prof. Erik Demaine Introduction to Algorithms Day 23 L12.2? 2001 by Erik D. Demaine Fixed-universe successor problem Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u –1}of size u subject to these operations: ? INSERT(x ∈ U \ S): Add x to S. ? DELETE(x ∈ S): Remove x from S. ? SUCCESSOR(x ∈ U): Find the next element in S larger than any element x of the universe U. ? PREDECESSOR(x ∈ U): Find the previous element in S smaller than x. Introduction to Algorithms Day 23 L12.3? 2001 by Erik D. Demaine Solutions to fixed-universe successor problem Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u –1}of size u subject to INSERT, DELETE, SUCCESSOR, PREDECESSOR. ? Balanced search trees can implement operations in O(lg n) time, without fixed-universe assumption. ? In 1975, Peter van Emde Boas solved this problem in O(lg lg u) time per operation. ? If u is only polynomial in n, that is, u = O(n c ), then O(lg lg n) time per operation-- exponential speedup! Introduction to Algorithms Day 23 L12.4? 2001 by Erik D. Demaine O(lg lg u)?! Where could a bound of O(lg lg u) arise? ? Binary search over O(lg u) things ? T(u) = T( ) + O(1) T’(lg u) = T’((lg u)/2) + O(1) = O(lg lg u) u Introduction to Algorithms Day 23 L12.5? 2001 by Erik D. Demaine (1) Starting point: Bit vector Bit vector v stores, for each x ∈ U, 1 if x ∈ S 0 if x ? S v x = Insert/Delete run in O(1) time. Successor/Predecessor run in O(u) worst-case time. Example: u = 16; n = 4; S = {1, 9, 10, 15}. 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Introduction to Algorithms Day 23 L12.6? 2001 by Erik D. Demaine (2) Split universe into widgets Example: u = 16, 4=u . 0 1 0 0 0123 0 0 0 0 4567 10 1 0 8 9 10 11 0 0 0 1 12 13 14 15 W 0 W 1 W 2 W 3 Carve universe of size u into widgets u W 0 , W 1 , …, W 1?u each of size u . Introduction to Algorithms Day 23 L12.7? 2001 by Erik D. Demaine (2) Split universe into widgets W 0 represents 0, 1, …, 1?u ∈ U; W 1 represents 12 ?u ∈ U; u , 1+u , …, W i represents 1)1( ?+ ui ∈ U; ui , 1+ui , …, : : W represents u – 1 ∈ U. uu ? , 1+? uu , …, 1?u Carve universe of size u into widgets u W 0 , W 1 , …, W 1?u each of size u . Introduction to Algorithms Day 23 L12.8? 2001 by Erik D. Demaine (2) Split universe into widgets Define high(x) ≥ 0 and low(x) ≥ 0 so that x = high(x) That is, if we write x ∈ U in binary, high(x) is the high-order half of the bits, and low(x) is the low-order half of the bits. For x ∈ U, high(x) is index of widget containing x and low(x) is the index of x within that widget. u + low(x). x = 9 high(x) = 2 low(x) = 1 1 0 0 1 0 1 0 0 0123 0 0 0 0 4567 0 1 1 0 8 9 10 11 0 0 0 1 12 13 14 15 W 0 W 1 W 2 W 3 Introduction to Algorithms Day 23 L12.9? 2001 by Erik D. Demaine (2) Split universe into widgets INSERT(x) insert x into widget W high(x) at position low(x). mark W high(x) as nonempty. Running time T(n) = O(1). Introduction to Algorithms Day 23 L12.10? 2001 by Erik D. Demaine (2) Split universe into widgets SUCCESSOR(x) look for successor of x within widget W high(x) starting after position low(x). if successor found then return it else find smallest i > high(x) for which W i is nonempty. return smallest element in W i O( ) u O( ) u O( ) u Running time T(u) = O( ). u Introduction to Algorithms Day 23 L12.11? 2001 by Erik D. Demaine Revelation SUCCESSOR(x) look for successor of x within widget W high(x) starting after position low(x). if successor found then return it else find smallest i > high(x) for which W i is nonempty. return smallest element in W i recursive successor recursive successor recursive successor Introduction to Algorithms Day 23 L12.12? 2001 by Erik D. Demaine (3) Recursion Represent universe by widget of size u. Recursively split each widget W of size |W| into sub[W][ W subwidgets sub[W][0], sub[W][1], …, W summary[W] W sub[W][0] W sub[W][1] W sub[W][ ] W … 1?W Store a summary widget summary[W] of size representing which subwidgets are nonempty. W 1?W .] each of size W Introduction to Algorithms Day 23 L12.13? 2001 by Erik D. Demaine (3) Recursion INSERT(x, W) if sub[W][high(x)] is empty then INSERT(high(x), summary[W]) INSERT(low(x), sub[W][high(x)]) Running time T(u) = 2 T( ) + O(1) T’(lg u)= 2 T’((lg u) / 2) + O(1) = O(lg u) . u Define high(x) ≥ 0 and low(x) ≥ 0 so that x = high(x) W + low(x). Introduction to Algorithms Day 23 L12.14? 2001 by Erik D. Demaine (3) Recursion SUCCESSOR(x, W) j ← SUCCESSOR(low(x), sub[W][high(x)]) if j < ∞ then return high(x) else i ← SUCCESSOR(high(x), summary[W]) j ← SUCCESSOR(– ∞, sub[W][i]) return i Running time T(u) = 3 T( ) + O(1) T’(lg u)= 3 T’((lg u) / 2) + O(1) = O((lg u) lg 3 ) . u W + j W + j T( ) u T( ) u T( ) u Introduction to Algorithms Day 23 L12.15? 2001 by Erik D. Demaine Improvements ? 2 calls: T(u) = 2 T( ) + O(1) = O(lg n) u ? 3 calls: T(u) = 3 T( ) + O(1) = O((lg u) lg 3 ) u ? 1 call: T(u) = 1 T( ) + O(1) = O(lg lg n) u Need to reduce INSERT and SUCCESSOR down to 1 recursive call each. We’re closer to this goal than it may seem! Introduction to Algorithms Day 23 L12.16? 2001 by Erik D. Demaine Recursive calls in successor If x has a successor within sub[W][high(x)], then there is only 1 recursive call to SUCCESSOR. Otherwise, there are 3 recursive calls: ? SUCCESSOR(low(x), sub[W][high(x)]) discovers that sub[W][high(x)] hasn’t successor. ? SUCCESSOR(high(x), summary[W]) finds next nonempty subwidget sub[W][i]. ? SUCCESSOR(– ∞, sub[W][i]) finds smallest element in subwidget sub[W][i]. Introduction to Algorithms Day 23 L12.17? 2001 by Erik D. Demaine Reducing recursive calls in successor If x has no successor within sub[W][high(x)], there are 3 recursive calls: ? SUCCESSOR(low(x), sub[W][high(x)]) discovers that sub[W][high(x)] hasn’t successor. ? Could be determined using the maximum value in the subwidget sub[W][high(x)]. ? SUCCESSOR(high(x), summary[W]) finds next nonempty subwidget sub[W][i]. ? SUCCESSOR(– ∞, sub[W][i]) finds minimum element in subwidget sub[W][i]. Introduction to Algorithms Day 23 L12.18? 2001 by Erik D. Demaine (4) Improved successor INSERT(x, W) if sub[W][high(x)] is empty then INSERT(high(x), summary[W]) INSERT(low(x), sub[W][high(x)]) if x < min[W] then min[W] ← x if x > max[W] then max[W] ← x Running time T(u) = 2 T( ) + O(1) T’(lg u)= 2 T’((lg u) / 2) + O(1) = O(lg u) . u new (augmentation) Introduction to Algorithms Day 23 L12.19? 2001 by Erik D. Demaine (4) Improved successor SUCCESSOR(x, W) if low(x) < max[sub[W][high(x)]] then j ← SUCCESSOR(low(x), sub[W][high(x)]) return high(x) else i ← SUCCESSOR(high(x), summary[W]) j ← min[sub[W][i]] return i Running time T(u) = 1 T( ) + O(1) = O(lg lg u) . u T( ) u T( ) u W + j W + j Introduction to Algorithms Day 23 L12.20? 2001 by Erik D. Demaine Recursive calls in insert If sub[W][high(x)] is already in summary[W], then there is only 1 recursive call to INSERT. Otherwise, there are 2 recursive calls: ? INSERT(high(x), summary[W]) ? INSERT(low(x), sub[W][high(x)]) Idea:We know that sub[W][high(x)]) is empty. Avoid second recursive call by specially storing a widget containing just 1 element. Specifically, do not store min recursively. Introduction to Algorithms Day 23 L12.21? 2001 by Erik D. Demaine (5) Improved insert INSERT(x, W) if x < min[W] then exchange x ? min[W] if sub[W][high(x)] is nonempty, that is, min[sub[W][high(x)] ≠ NIL then INSERT(low(x), sub[W][high(x)]) else min[sub[W][high(x)]] ← low(x) INSERT(high(x), summary[W]) if x > max[W] then max[W] ← x Running time T(u) = 1 T( ) + O(1) = O(lg lg u) . u Introduction to Algorithms Day 23 L12.22? 2001 by Erik D. Demaine (5) Improved insert SUCCESSOR(x, W) if x < min[W] then return min[W] if low(x) < max[sub[W][high(x)]] then j ← SUCCESSOR(low(x), sub[W][high(x)]) return high(x) else i ← SUCCESSOR(high(x), summary[W]) j ← min[sub[W][i]] return i Running time T(u) = 1 T( ) + O(1) = O(lg lg u) . u T( ) u T( ) u W + j W + j new Introduction to Algorithms Day 23 L12.23? 2001 by Erik D. Demaine Deletion DELETE(x, W) if min[W]= NIL or x < min[W] then return if x = min[W] then i ← min[summary[W]] x ← i min[W] ← x DELETE(low(x), sub[W][high(x)]) if sub[W][high(x)] is now empty, that is, min[sub[W][high(x)] = NIL then DELETE(high(x), summary[W]) (in this case, the first recursive call was cheap) + min[sub[W][i]] W