Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 13 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 13 Prof. Erik Demaine
Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\S): Add x to s DELETE(X E S): Remove x from S SUCCESSOR( E U): Find the next element in S larger than any element x of the universe U PREDECESSOR(XE U): Find the previous element in s smaller than x c 2001 by erik D. Demaine Introduction to Algorithms Day 23 L12.2
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.2 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
Solutions to fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to Insert DELeTE, SUCCESSoR PrEdeCessor Balanced search trees can implement operations in O(g n)time, without fixed-universe assumption In 1975. peter van Emde boas solved this problem in odg lg u time per operation If u is only polynomial in n, that is, u=o(n), then o(g lg n) time per operation exponential speedup c 2001 by erik D. Demaine Introduction to Agorithms Day 23 L12.3
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.3 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(nc), then O(lg lg n) time per operation-- exponential speedup!
o(g lg u)? Where could a bound of o(g lg u) arise? Binary search over Odg u) things T)=7(a)+O(1) T(lgu)=T(lg)/2)+O(1) O(g lg c 2001 by erik D. Demaine Introduction to Algorithms Day 23 L12.4
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.4 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
(1 Starting point: Bit vector Bit vector y stores for eachxE U lifx∈S lO ifx g s Example:l=16;n=4;S={1,9,10,15} 0100000001100001 0123456789101112131415 Insert/Delete run in o(1)time Successor/Predecessor run in O(u) worst-case time c 2001 by erik D. Demaine Introduction to Agorithms Day 23 L12.5
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.5 (1) Starting point: Bit vector Bit vector v stores, for each x ∈ U, 1 if x ∈ S 0 if x ∉ S vx = 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
(2) Split universe into widgets Carve universe of size u into vu widgets W 021> Vu-1 each of Size vu Example: u=16,vu=4 W W W 0100000001100001 0123456789101112131415 c 2001 by erik D. Demaine Introduction to Ago orns Day 23 L12.6
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.6 (2) Split universe into widgets Example: u = 16, u = 4. 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 W0 W1 W2 W3 Carve universe of size u into widgets u W0, W1, …, W u −1 each of size u
(2) Split universe into widgets Carve universe of size u into vu widgets W 021> Vu-1 each of Size vu Wo represents0,1,…,-1∈U W, representSVu, Vu+1,.,2vu-lE U W, represents iv/u,i+12…,(+1)l-1∈U WG-i represents u-lu,l-Vl+1,…,u-1∈U c 2001 by erik D. Demaine Introduction to Algorithms Day 23 L12.7
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.7 (2) Split universe into widgets W0 represents 0, 1, …, u −1 ∈ U; W1 represents u, u +1, …, 2 u −1∈ U; Wi represents i u, i u +1, …, (i +1) u −1∈ U; : : W represents u − u , u − u +1 , …, u – 1 ∈ U. u −1 Carve universe of size u into widgets u W0, W1, …, W u −1 each of size u
(2) Split universe into widgets x=9 Define high(x)20 and low(x201001 so that x= high(x)u+ low(x) That is, if we write x E U in binary high(x) low(x) 2 high(x)is the high-order half of the bits and low(x)is the low-order half of the bits Forx e U, high(x) is index of widget containing x and low()is the index of x within that widget W 0100000001100001 0123456789101112131415 c 2001 by erik D. Demaine Introduction to Agorithms Day 23 L12.8
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.8 (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 W0 W1 W2 W3
(2) Split universe into widgets INSERT(X) insert x into widget Whigh() at position low(x) mark w high(x)as nonempty Running time r(n)=o(1) c 2001 by erik D. Demaine Introduction to Ago orns Day 23 L12.9
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.9 (2) Split universe into widgets INSERT(x) insert x into widget Whigh(x) at position low(x). mark Whigh(x) as nonempty. Running time T(n) = O(1)
(2)Split universe into widgets SUCCESSOR(x) look for successor of x within widget w wigh()( Ovu) starting after position low(x) if d successor found then return it else find smallest i> high(x) O(√l) for which W, is nonempty return smallest element in w }O(a) Running time T(u)=o(vu) c 2001 by erik D. Demaine Introduction to Algorithms Day23L12.10
© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.10 (2) Split universe into widgets SUCCESSOR(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( ) u O( ) u O( ) u Running time T(u) = O( ) u