(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