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