-
November 3rd, 2014, 01:06 PM
#1
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 satises 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?
-
November 4th, 2014, 02:41 AM
#2
Re: arrays of bits
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).
Last edited by razzle; November 4th, 2014 at 05:03 AM.
-
November 4th, 2014, 08:42 AM
#3
Re: arrays of bits
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?
-
November 4th, 2014, 11:43 AM
#4
Re: arrays of bits
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).
Last edited by razzle; November 4th, 2014 at 11:46 AM.
-
November 4th, 2014, 04:07 PM
#5
Re: arrays of bits
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).
-
November 4th, 2014, 09:39 PM
#6
Re: arrays of bits
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).
-
November 5th, 2014, 03:01 AM
#7
Re: arrays of bits
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.
-
November 5th, 2014, 10:29 AM
#8
Re: arrays of bits
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.
-
November 5th, 2014, 04:05 PM
#9
Re: arrays of bits
Thank you razzle; point taken
-
November 5th, 2014, 04:06 PM
#10
Re: arrays of bits
@OReubens can you please be more specific? i do not get your point.
-
November 5th, 2014, 06:04 PM
#11
Re: arrays of bits
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.
-
November 6th, 2014, 01:00 AM
#12
Re: arrays of bits
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.
Last edited by razzle; November 6th, 2014 at 11:48 AM.
-
November 6th, 2014, 11:01 AM
#13
Re: arrays of bits
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
-
November 6th, 2014, 02:43 PM
#14
Re: arrays of bits
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
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.
-
November 6th, 2014, 04:40 PM
#15
Re: arrays of bits
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
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|