dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 22

Thread: arrays of bits

  1. #1
    Join Date
    Oct 2014
    Posts
    10

    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 di erent 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?

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: arrays of bits

    Quote Originally Posted by sanchez_masherano View Post
    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.

  3. #3
    Join Date
    Oct 2014
    Posts
    10

    Re: arrays of bits

    Quote Originally Posted by razzle View Post
    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?

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: arrays of bits

    Quote Originally Posted by sanchez_masherano View Post
    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.

  5. #5
    Join Date
    Oct 2014
    Posts
    10

    Re: arrays of bits

    Quote Originally Posted by razzle View Post
    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).

  6. #6
    Join Date
    Feb 2013
    Posts
    58

    Re: arrays of bits

    Quote Originally Posted by razzle View Post
    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).

  7. #7
    Join Date
    Jul 2013
    Posts
    576

    Re: arrays of bits

    Quote Originally Posted by sanchez_masherano View Post
    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.

  8. #8
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    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.

  9. #9
    Join Date
    Oct 2014
    Posts
    10

    Re: arrays of bits

    Thank you razzle; point taken

  10. #10
    Join Date
    Oct 2014
    Posts
    10

    Re: arrays of bits

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

  11. #11
    Join Date
    Feb 2013
    Posts
    58

    Re: arrays of bits

    Quote Originally Posted by sanchez_masherano View Post
    @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.

  12. #12
    Join Date
    Jul 2013
    Posts
    576

    Re: arrays of bits

    Quote Originally Posted by S@rK0Y View Post
    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.

  13. #13
    Join Date
    Oct 2014
    Posts
    10

    Re: arrays of bits

    Quote Originally Posted by S@rK0Y View Post
    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

  14. #14
    Join Date
    Feb 2013
    Posts
    58

    Re: arrays of bits

    Quote Originally Posted by sanchez_masherano View Post
    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.

  15. #15
    Join Date
    Oct 2014
    Posts
    10

    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

Page 1 of 2 12 LastLast

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)