Week 9

1. * Assume a hash table of size 11 using linear probing with a step size of 1 and a hash function of index = key mod 11. Insert the following keys into an initially empty hash table : 24,26,87, 66, 76, 1, 10

      [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
     _____________________________________________
      66  76   24  1   26  10                  87
     _____________________________________________
    
   Load Factor = number of items/ tablesize
               = 7/11
   

2. * Assume a hash table of size 11 using separate chaining. Insert the same keys into the hash table.

     [0] ---> 66
     [1] ---> 1
     [2] ---> 24
     [3]
     [4] ---> 26
     [5]
     [6]
     [7]
     [8]
     [9]
     [10] --->10 ---> 76 --->87
   
   Load Factor = 7/11 
   

3. Average case insertion/retrieval/deletion for hashtables = 0(1) Worst case insertion/retrieval/deletion for hashtables = O(n) (when choose very poor hash function)
4. For strings need position of char and ascii value eg very simple-minded ... assume have converted string to uppercase

       int hash (string s)
       {
       // precondition : s is uppercase letters
       // postcondition : returns hashed value of s
         int pos = 1;
         int result = 0;
         for (int i = 0; i < s.length();i++)
         {
             result += pos * int(s.at(i)-'A');
             pos *= 10; // could argue for different multiplier
         }
         return result % tableSize;
      }
   

5. Assuming the following definition of a node, write the insert function to insert a node into a hash table using separate chaining. Note will insert on front of list.

      struct node
      {
         int key;
         // other stuff
         node * next;
      };
     void insert (node *hashtable[],int n, node *newItem)
     // precondition : hastable [0..n-1] is a hashtable
     // postcondition : newItem is inserted into hashtable
     //  calls function hash
     {
        int pos = hash(newItem->key);
        newItem->next = hashtable[pos];
        hashtable[pos] = newItem;
     }
   

6. What's the difference between an STL map and an STL multimap? A map assumes keys are unique and refuses to overwrite existing key when duplicate occurs. a multimap allows duplicate keys.
   Could we use a map for a simple-minded sorting algorithm? Could use a multimap - done in lectures. Could only use a map if all elements were unique.
   How could we find the largest key value in a multimap?
   Smallest is easiest - just find the first one.

      int getSmallest( multimap < int,int> m)
      {
         return m.begin()->first;
      }
        // return key value - first field in pair
   

   Largest Key value - find last key in multimap. Note m.end() is BEYOND end of data so cannot use end() but can use rbegin(); which is starting point of reverse_iterator (one which goes backwardS)

     int getLargest( multimap < int, int> m)
     {
        return m.rbegin()->first;
     }
   
   

   What is the efficiency of this operation? Ditto smallest. O(1) for each

   void multimapsort(int a[], int n)
   {
       multimap  m;
       for (int i = 0; i < n; i++)
          m.insert(make_pair(a[i],0));  second argiment is dummy
       multimap  :: itertor it;
       int i = 0;
       for (it = m.begin(); it != m.end(); it++)
          a[i++] = it->first; 
       
   
   }
   

   efficiency is
   n *O( log n) to insert
   O(n ) to traverse
   = O(n log n)
   

   Just improving understanding of multimaps here - not seriously suggesting it as an alternative. Would use sort in if want to keep hands clean. Perhaps we should talk here about how to use algorithm in STL. Not examinable but very useful.

   #include <algorithm>
   
   vector <int > v;
    ...
   sort(v.begin(),v.end());
   stable_sort(v.begin(),v.end());
   random_shuffle(v.begin(), v.end());
   ...