arrays of bits

[sanchez_masherano]

hi i have the following problem:

Suppose we want to maintain an array X[1::n] of bits, which are all initially zero, subject to the
following operations.
 LOOKUP(i): Given an index i, return X[i]
 BLACKEN(i): Given an index i < n, set X[i]
 NEXTWHITE(i): Given an index i, return the smallest index j  i such that X[j ] = 0.
(Because we never change X[n], such an index always exists.)
If we use the array X[1::n] itself as the only data structure, it is trivial to implement LOOKUP
and BLACKEN in O(1) time and NEXTWHITE in O(n) time. But you can do better! Describe
data structures that support LOOKUP in O(1) worst-case time and the other two operations in
the following time bounds. (We want a dierent data structure for each set of time bounds, not
one data structure that satises all bounds simultaneously!)
(a) The worst-case time for both BLACKEN and NEXTWHITE is O(log n).
(b) The amortized time for both BLACKEN and NEXTWHITE is O(log n). In addition, the
worst-case time for BLACKEN is O(1).
(c) The amortized time for BLACKEN is O(log n), and the worst-case time for NEXTWHITE
is O(1).
(d) The worst-case time for BLACKEN is O(1), and the amortized time for NEXTWHITE is
O((n). [Hint: There is no WHITEN.]

I am thinking of using union find data structure but im not sure on how to proceed. Any help?

[razzle]

NEXTWHITE(i): Given an index i, return the smallest index j i such that X[j ] = 0.

In the definition of NEXTWHITE(i) it should be "j>i" right?

I'll assume that and make a suggestion for the (a) question.

In addition to the X[1::n] array you need a binary search tree where all indexes corresponding to a 0 in X are stored in sorted order. Lets call it BST. Initially BST holds all indexes between 1 and n (because all index positions of X are initially set to 0).

Now for LOCKUP(i) you use X. That takes O(1).

For BLACKEN(i) you set the corresponding bit in X which takes O(1), but you also remove the i index from BST (because it no longer corresponds to a 0) and that takes O(log n). All in all that's O(log n).

Finally for NEXTWHITE(i) you make a search in BST for the smallest index bigger than i. That will be j and it takes O(log n) to find it. (If i is in BST, j is its next bigger neighbour. If i is not in BST, j is where i should be if it were in BST).

So with BST in addition to X you get LOCKUP in O(1) and BLACKEN and NEXTWHITE in O(log n) which was requested in (a).

[sanchez_masherano]

In the definition of NEXTWHITE(i) it should be "j>i" right?

I'll assume that and make a suggestion for the (a) question.

In addition to the X[1::n] array you need a binary search tree where all indexes corresponding to a 0 in X are stored in sorted order. Lets call it BST. Initially BST holds all indexes between 1 and n (because all index positions of X are initially set to 0).

Now for LOCKUP(i) you use X. That takes O(1).

For BLACKEN(i) you set the corresponding bit in X which takes O(1), but you also remove the i index from BST (because it no longer corresponds to a 0) and that takes O(log n). All in all that's O(log n).

Finally for NEXTWHITE(i) you make a search in BST for the smallest index bigger than i. That will be j and it takes O(log n) to find it. (If i is in BST, j is its next bigger neighbour. If i is not in BST, j is where i should be if it were in BST).

So with BST in addition to X you get LOCKUP in O(1) and BLACKEN and NEXTWHITE in O(log n) which was requested in (a).

@razzle, thank you, indeed your assumption was right; but what about the cost of constructiing the BST? isnt more than logn?

[razzle]

but what about the cost of constructiing the BST? isnt more than logn?

There will be an initial cost. Both X and BST must be constructed/intialized. Building the BST will be an O(n * log n) operation (entering n items into a binary tree at a cost of O(log n) each).

But what happens once at the beginning is usually disregarded (if it's not exactly that one is interested in).

[sanchez_masherano]

There will be an initial cost. Both X and BST must be constructed/intialized. Building the BST will be an O(n * log n) operation (entering n items into a binary tree at a cost of O(log n) each).

But what happens once at the beginning is usually disregarded (if it's not exactly that one is interested in).

Thank you razzle. any clue on c) and d)?. i managed to do b).

[S@rK0Y]

In the definition of NEXTWHITE(i) it should be "j>i" right?

I'll assume that and make a suggestion for the (a) question.

In addition to the X[1::n] array you need a binary search tree where all indexes corresponding to a 0 in X are stored in sorted order. Lets call it BST. Initially BST holds all indexes between 1 and n (because all index positions of X are initially set to 0).

Now for LOCKUP(i) you use X. That takes O(1).

For BLACKEN(i) you set the corresponding bit in X which takes O(1), but you also remove the i index from BST (because it no longer corresponds to a 0) and that takes O(log n). All in all that's O(log n).

Finally for NEXTWHITE(i) you make a search in BST for the smallest index bigger than i. That will be j and it takes O(log n) to find it. (If i is in BST, j is its next bigger neighbour. If i is not in BST, j is where i should be if it were in BST).

So with BST in addition to X you get LOCKUP in O(1) and BLACKEN and NEXTWHITE in O(log n) which was requested in (a).

Razzle, not sure what structure you do mean. if 'tis array, then term "remove" ain't good -- array gonna contain "0"s & "1"s as well. i think better off to deal w/

NODE{
NODE *parent;
NODE *left;
NODE *right;
_i64   index;
}node;

So, 'remove' exists & takes O(1).

[razzle]

Thank you razzle. any clue on c) and d)?. i managed to do b).

You're wellcome. I'm sure you'll manage the rest too

Just a final comment. For my suggestion to be correct then BST must be self-balancing otherwise the worst case will be O(n) rather than O(log n). So it's assumed BST isn't just any binary tree but a Red-Black Tree or an AVL Tree for example.

[OReubens]

C) a linked list of free items, with the array pointing to the free list item once it's blackened.
D) that's the initial proposed solution. an array of bits, and you search for the next white bit.

[sanchez_masherano]

Thank you razzle; point taken

[sanchez_masherano]

@OReubens can you please be more specific? i do not get your point.

[S@rK0Y]

@OReubens can you please be more specific? i do not get your point.

tree ain't good enough to provide random access to items(nodes) for O(1). So to provide fast operations need to use memory-gobbling strategy:

1. Tree must be gotten to provide fast SEARCH, REMOVE, INSERT.
2. Array is used for fast RANDOM ACCESS to all nodes in BST.

[razzle]

So to provide fast operations need to use memory-gobbling strategy:

Yes and that's why my suggestion for (a) is based on two data structures used in conjunction, namely the array X and the self-balancing binary search tree BST.

Together they provide the asked for complexities for LOOKUP, BLACKEN and NEXTWHITE.

[sanchez_masherano]

tree ain't good enough to provide random access to items(nodes) for O(1). So to provide fast operations need to use memory-gobbling strategy:

1. Tree must be gotten to provide fast SEARCH, REMOVE, INSERT.
2. Array is used for fast RANDOM ACCESS to all nodes in BST.

hi S@rK0Y, i am bit lost here, can you please be more specific? i am kind of new in this;so i would really appreciate if you can be clearer

[S@rK0Y]

hi S@rK0Y, i am bit lost here, can you please be more specific? i am kind of new in this;so i would really appreciate if you can be clearer

well, let's try to run example. let's we have a tree of 3 nodes (root, left, right), our node looks like:

#include <stdio.h>
struct NODE{
NODE *left;
NODE *right;
int index;
}node;
NODE root, left, right; 
void initialize_arr(NODE *root, NODE **arr){
   if(root==NULL)return;
   arr[root->index]=root;
   if(root->left !=NULL)initialize_arr(root->left, arr);
   if(root->left !=NULL)initialize_arr(root->right, arr);
  return;
}
int main(int argc, char **argv)
{
      root.left = &left;
root.right = &right;
NODE *rnd_access_arr[3];
initialize_arr(&root, rnd_access_arr);
   return 0;
}

So, now you must build functions to deal w/ BST & ye'll get desirable result

ops of SEARCH, REMOVE, INSERT the node are running as BST funcs. RANDOM ACCESS to node gets through rnd_access_arr. Meanwhile, keep in mind: memory-gobbling strategy is good, only if ye have enough memory, otherwise your app gets in the very curse of I/O bottleneck.

[sanchez_masherano]

yes but what is the required algorithm before the implemenation, the algorithm should be independant of the language or the application and it should run as specified in the problem statement