Chapter 11: Hash Tables

11.1.1. For finding the maximum element in the table you have to scan each slot once and update your maximum element accordingly.The worst case complexity would be O(m).

11.1.2. Initialize a bit vector of length |U| to all  0s. When storing key k set the kth bit and when deleting the unset the kth bit.

11.1.3. Each element in the table should be a pointer to the head of a linked list containing the satellite data. I though doubt for searching to be O(1).

11.1.4. Let us denote the huge array by T, we will also have a structure implemented as an array, S.

                        struct node{

                                    int key;

                                    int value;

} S;

The size of S equals the number of keys actually stored in T, so that S should be allocated at the dictionary’s maximum size. We can also use a linked list data structure so that we need not allocated space initially.

The idea of this scheme is that entries of T and S validate each other. If key k is actually stored in T , then T [k] contains the index, say j , of a valid entry in S, and S[ j ] contains the value k. So, we will have a following validation cycle:

S[T [k]].key = k, and T [S[ j ].key] = j

So, it means the stack S will not really be a stack since we are able to access any index not only the top element. So, for the namesake we can call it a simple array.

Implementing the following operations:

            SEARCH: Just check if for a given input key, the validating cycle is satisfied, if yes return the value.

            INSERT: Increment top[S] to point to the next index. Now make T[k] = top[S] and S[top[S]].key = new_key and S[top[S]].value = new_value_for_the_key.

            DELETE: To delete object x with key k, assuming that this object is in the dictionary, we need to break the validating cycle. The trick is to also ensure that we don’t leave a hole.in the stack, and we solve this problem by moving the top entry of the stack into the position that we are vacating and then fixing up that entry’s validating cycle. Try to come up with a step to implement this.

11.2.1.

11.2.3. Only insertion will be affected by this modification with complexity becoming O(n/m) from O(1).

11.2.4. Initialize all the values to a singly linked free list (flag set to false) with a head and tail pointer. On insert, use the memory pointed to by the head pointer and set the flag to true for the new element and increment the head pointer by one. On delete, set the flag to false and insert the newly freed memory at the tail of the linked list.

11.2.5. This is an application of pigeon-hole principle.

11.3.1. While searching for a key k, we’ll first check if the hash value matches if yes then only we’ll check if the keys actually match or not.

11.3.2. One easy approach would adding the values of each character to get a sum and then take a modulo 128. Another way would be using n-degree equation with each character value acting as a co-efficient for the n^th term.

Example: S[0]*xⁿ + S[1]*x^(n-1)+ …. + S[n-1], for better result substitute x = 33 or 37 or 39. This is the famous Horner’s method for finding a hash value.

11.4.2.

HASH-DELETE(T, k)

i ← 0

repeat j ← h(k, i)

if T[j] = k

then T[j] ← -1

return j

else i ← i + 1

until i = m or T[j] = NIL

error "element doesn’t exist"

           

HASH-INSERT(T, k)

i ← 0

repeat j ← h(k, i)

if T[j] = NIL or T[j] = -1

then T[j] ← k

return j

else i ← i + 1

until i = m

error "element doesn’t exist"

Chapter 10: Elementary Data Structure

I am not posting solution of all the questions. But if you've any doubt kindly post it as 

a comment I'll post the solution as soon as possible.

10.2.4. Let's first define our node structure.

            struct node{

              int value;

              struct node* next;

            }

         When we've a sentinal node we'll make our last node in the linked list to point to the sentinal node.                And whenever we need to search for a value we'll update the value of our sentinal node to that search value. This way we'll be sure of finding that value in the linked list. The code goes here:

         

         boolean ListSearch(node* head,int value,node* sentinal_node){

            if(!head){

                return false;

            }

            sentinal_node->value = value;

            while(head != null){

                if(head->value == value){

                      break;

                }

                head = head->next;

            }

            if(head == sentinal_node){

                return false;

            }

            return true;

       }

       

10.2.5. Impleting a dictionary using a linked list is very similar to storing a list of numbers 

        in a linked list. Here, we just need to replace integer values with string literals.

        Let's first define our node structure.

            struct node{

                      char* word;

                      struct node* next;

            }

        Here are the cost of some operations:

        INSERT: O(1), simply insert at the head of the list.

        DELETE: O(n), you'll have to first search for the element in the list. For searching in the worst case

       you've to compare with every node in the linked list.

        SEARCH: O(n), reason is same as of above.

         

10.2.6. Let's first define our node structure.

            struct node{

                      char* word;

                      struct node* next;

            }

            struct Set{

                    struct node* head;

                    struct node* tail;

            }

        For every list beside with the head pointer we'll also keep a tail pointer.

        Supporting union operation in O(1) time: Suppose we've two Sets S1 and S2.

        

       PSEUDO-CODE:

                node* Union(Set S1,Set S2){

                      S1.tail->next = S2.head;

                      S1.tail = S2.tail;

                      Remove S2 from the list of sets;

                      return S1;

                }


10.4.4. void PrintNodes(node* root){
if(!root){
return;
}
PrintNodes(root->left);
printf("%d ",root->value);
PrintNodes(root->sibling);
            }


10.4.5. One very basic approach would be to do a level-order traversal. This can be implemented using a queue.
PSEUDO-CODE:

void DoLevelTraversal(node* root){
Queue<node*> Q;
Q.push(root);
while(!Q.empty()){
node* top = Q.front();
Q.pop();
printf("%d ",top->value);
while(top->sibling != NULL){
Q.push(top->sibling);
top = top->sibling;
}
}
}

But it uses extra space. Will think of some other approach soon.

Medians and Order Statistics

9.1.1. First of all, make sure that for finding the maximum element out of 'n' elements will take 'n-1' comparisions. Now, when you're through this, let us suppose that you compared the elements by making a pair each time. For better understanding go through the below diagram:

Now, the second maximum element would've compared with the maximum somewhere between the heigth of the tree which will be log(n) as it'll always be a balanced tree. So, we can traverse the tree from the root(which is the maximum element) and compare the elements only in that path to find the maximum among them. As there'll be a maximum of log(n) elements along this path, so the maximum element can be found in log(n)-1 comparisions.

So, in total n+log(n)-2 comparisions will be needed to find the maximum and the second maximum element.

 

9.1.2. This is also very similar to above problem in which we need to compare elements by making pairs. Try Yourself!!!

9.2.1. This is very simple, for any 0-length array (p == q) will evaluates to true and the function will return from there.

9.2.3.

9.2.4. Following can be one of the worst-case performance of randomized selection:

                        (i.) 2, 9, 0, 7, 5, 4, 8, 6, 1

                        (ii.) 9, 0, 7, 5, 4, 8, 6, 1

                        (iii.) 0, 7, 5, 4, 8, 6, 1

                        (iv.) 0, 7, 5, 4, 8, 6

                        (v.) 0, 7, 5, 4, 8

                        (vi.) 0, 7, 5, 4

                        (vii.) 0, 7, 5

                        (viii.) 0, 7

                        (ix.) 0

 

9.3.3. For achieving worst case O(nlogn) complexity for quicksort we can replace the partition in the traditional algorithm for quicksort with

       SELECT procedure mentioned in the article.

9.3.5. Given the black box, after every partition we are sure that the given element either lies to left or to the right side of the partition.

       Thus we need to search only n/2 elements for 2nd iteration. Thus the time complexity can be found as:

    c*n + c*n/2 + c*n/4 + c*n/6 + ... = 2*c*n

       so, our selection algorithm will have O(n) complexity given the linear time black box.

9.3.7. First of all find the median of the 'n' elements, suppose that index is 'i (=n/2)'. Now the 'k' elements that are closest to the median are 

       those which are (i-k/2) and (i+k/2) distance from the median. So, just find the (i+k/2)th element and (i-k/2)th element. Thus, the 'k' 

       elements which are 'k' distance from the median are the elements from (i-k/2) to (i+k/2).  

9.3.9. In order to Þnd the optimal placement for Professor Olay’s pipeline, we need only and the median(s) of the y-coordinates of his oil wells.

       The optimal y-coordinate for Professor Olay’s east-west oil pipeline is as follows:

• If n is even, then on either the oil well whose y-coordinate is the lower median or the one whose y-coordinate is the upper median, or anywhere between them.

• If n is odd, then on the oil well whose y-coordinate is the median.

       The proof is quite simple and can be easily cracked. Try it yourself.

9.1. (a.) The best algorithm will have O(nlogn) complexity. Then finding the i largest element can be done in O(i).

          So, overall complexity will be O(nlogn + i).

     (b.) Building a max-priority queue is O(n) complexity. Then extracting largest 'i' elements can be done with O(ilogi) complexity.

          So, overall complexity will be O(n + ilogi).

  

     (c.) Use the SELECT algorithm of Section 9.3 to Þnd the i th largest number in (n) time. Partition around that number in (n) time. Sort the i largest numbers in

 (i lg i ) worst-case time (with merge sort or heapsort).

          So, overall running time will be: (n + i lg i ).