Introduction to Algorithms 6.046J/18.401J/SMA5503Fixed-universe successor problemSolutions to fixed-universe successor problemO(lg lg u)?!(1) Starting point: Bit vector(2) Split universe into widgetsSlide 7Slide 8Slide 9Slide 10Revelation(3) RecursionSlide 13Slide 14ImprovementsRecursive calls in successorReducing recursive calls in successor(4) Improved successorSlide 19Recursive calls in insert(5) Improved insertSlide 22DeletionIntroduction to Algorithms6.046J/18.401J/SMA5503Lecture 14Prof. Erik DemaineIntroduction to AlgorithmsOctober 30, 2002 L12.2© 2002 by Erik D. DemaineFixed-universesuccessor problemGoal: Maintain a dynamic subset S of size nof the universe U = {0, 1, …, u – 1} of size usubject 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 AlgorithmsOctober 30, 2002 L12.3© 2002 by Erik D. DemaineSolutions to fixed-universe successor problemGoal: Maintain a dynamic subset S of size nof the universe U = {0, 1, …, u – 1} of size usubject 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(nc), then O(lg lg n) time per operation-- exponential speedup!Introduction to AlgorithmsOctober 30, 2002 L12.4© 2002 by Erik D. DemaineO(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)uIntroduction to AlgorithmsOctober 30, 2002 L12.5© 2002 by Erik D. Demaine(1) Starting point: Bit vectorBit vector v stores, for each x  U,1 if x  S0 if x  Svx =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 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Introduction to AlgorithmsOctober 30, 2002 L12.6© 2002 by Erik D. Demaine(2) Split universe into widgetsExample: u = 16, 4u.0 1 0 00 1 2 30 0 0 04 5 6 710 1 08 9 10 110 0 0 112 13 14 15W0W1W2W3Carve universe of size u into widgetsuW0, W1, …, W1ueach of sizeu.Introduction to AlgorithmsOctober 30, 2002 L12.7© 2002 by Erik D. Demaine(2) Split universe into widgetsW0 represents 0, 1, …, 1u U;W1 represents12 u U;u,1u, …,Wi represents1)1(  ui U;ui,1ui, …,::W representsu – 1  U.uu ,1 uu, …,1uCarve universe of size u into widgetsuW0, W1, …, W1ueach of sizeu.Introduction to AlgorithmsOctober 30, 2002 L12.8© 2002 by Erik D. Demaine(2) Split universe into widgetsDefine high(x)  0 and low(x)  0so 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 xand low(x) is the index of x within that widget.u+ low(x).x = 9high(x) = 2low(x) = 11 0 0 10 1 0 00 1 2 30 0 0 04 5 6 70 1 1 08 9 10 110 0 0 112 13 14 15W0W1W2W3Introduction to AlgorithmsOctober 30, 2002 L12.9© 2002 by Erik D. Demaine(2) Split universe into widgetsINSERT(x)insert x into widget Whigh(x) at position low(x).mark Whigh(x) as nonempty.Running time T(n) = O(1).Introduction to AlgorithmsOctober 30, 2002 L12.10© 2002 by Erik D. Demaine(2) Split universe into widgetsSUCCESSOR(x)look for successor of x within widget Whigh(x)starting after position low(x).if successor found then return it else find smallest i > high(x)for which Wi is nonempty. return smallest element in Wi O( )uO( )uO( )uRunning time T(u) = O( ).uIntroduction to AlgorithmsOctober 30, 2002 L12.11© 2002 by Erik D. DemaineRevelationSUCCESSOR(x)look for successor of x within widget Whigh(x)starting after position low(x).if successor found then return it else find smallest i > high(x)for which Wi is nonempty. return smallest element in Wi recursivesuccessorrecursivesuccessorrecursivesuccessorIntroduction to AlgorithmsOctober 30, 2002 L12.12© 2002 by Erik D. Demaine(3) RecursionRepresent universe by widget of size u.Recursively split each widget W of size |W|into sub[W][Wsubwidgets sub[W][0], sub[W][1], …,Wsummary[W]Wsub[W][0]Wsub[W][1]Wsub[W][ ]W…1WStore a summary widget summary[W] of size representing which subwidgets are nonempty.W1W.] each of sizeWIntroduction to AlgorithmsOctober 30, 2002 L12.13© 2002 by Erik D. Demaine(3) RecursionINSERT(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) .uDefine high(x)  0 and low(x)  0so that x = high(x)W+ low(x).Introduction to AlgorithmsOctober 30, 2002 L12.14© 2002 by Erik D. Demaine(3) RecursionSUCCESSOR(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 iRunning time T(u) = 3 T( ) + O(1) T’(lg u) = 3 T’((lg u) / 2) + O(1)= O((lg u) lg 3) .uW+ jW+ jT( )uT( )uT( )uIntroduction to AlgorithmsOctober 30, 2002 L12.15© 2002 by Erik D. DemaineImprovements• 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)uNeed to reduce INSERT and SUCCESSORdown to 1 recursive call each.We’re closer to this goal than it may seem!Introduction to AlgorithmsOctober 30, 2002 L12.16© 2002 by Erik D. DemaineRecursive calls in successorIf 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 AlgorithmsOctober 30, 2002 L12.17© 2002 by Erik D. DemaineReducing recursive callsin successorIf 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)]