arrays of bits

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?

Quote:

---

Originally Posted by sanchez_masherano

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).

Quote:

---

Originally Posted by razzle

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?

Quote:

---

Originally Posted by sanchez_masherano

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).

Quote:

---

Originally Posted by razzle

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).

Quote:

---

Originally Posted by razzle

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/

Code:

---

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

---

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

Quote:

---

Originally Posted by sanchez_masherano

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.

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.

Thank you razzle; point taken

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

Quote:

---

Originally Posted by sanchez_masherano

@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.

Quote:

---

Originally Posted by S@rK0Y

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.

Quote:

---

Originally Posted by S@rK0Y

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

Quote:

---

Originally Posted by sanchez_masherano

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:

Code:

---

#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 :D

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.

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

Quote:

---

Originally Posted by 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

---

hardware-independent algos don't exist in our furious & crafty World :rolleyes: You can develop quite portable thing, but performance will be very shy.

Quote:

---

Originally Posted by S@rK0Y

hardware-independent algos don't exist in our furious & crafty World :rolleyes: You can develop quite portable thing, but performance will be very shy.

---

At an algorithm forum a certain ability to reason in the abstract is expected,

http://en.wikipedia.org/wiki/Abstraction

Otherwise you risk coming across as a rambling nutcase and no one will listen. Especially if you also use opaque almost incomprehensible language.

Quote:

---

Originally Posted by razzle

At an algorithm forum a certain ability to reason in the abstract is expected,

http://en.wikipedia.org/wiki/Abstraction

Otherwise you risk coming across as a rambling nutcase and no one will listen. Especially if you also use opaque almost incomprehensible language.

---

programmer must understand the limits of abstraction clearly, otherwise it's impossible to develop efficient algorithms. i think you can recall an example or two, where algos of equal mathematical complexity run at very different speeds. ;)

Quote:

---

Originally Posted by S@rK0Y

programmer must understand the limits of abstraction clearly, otherwise it's impossible to develop efficient algorithms.

---

No need to worry. Most programmers understand that computational complexity and runtime speed are efficiency measures at different levels of abstraction, and although there is a correlation between them, one doesn't translate directly into the other.

With that set aside I hope you may now be able to give a more to the point reply to sanchez_masherano's post #15. Good luck.

Quote:

---

Originally Posted by razzle

No need to worry. Most programmers understand that computational complexity and runtime speed are efficiency measures at different levels of abstraction, and although there is a correlation between them, one doesn't translate directly into the other.

With that set aside I hope you may now be able to give a more to the point reply to sanchez_masherano's post #15. Good luck.

---

i don't know hardware-independent algos :rolleyes: even java codes, js, php.. are only theoretically portable things. :D

Quote:

---

Originally Posted by S@rK0Y

i don't know hardware-independent algos :rolleyes: even java codes, js, php.. are only theoretically portable things. :D

---

It's considered bad manners to hijack other people's threads.

Quote:

---

Originally Posted by razzle

It's considered bad manners to hijack other people's threads.

---

yes, it's bad, but something says me that Topic Starter has solved his question :rolleyes: + i don't know what else can be said on topic. i think it may be only the cadging to write a code from scratch. ;) anyway, i'm done -- there's been rather curious algo i wanna complete. :D