COMP225 : Algorithms and Data Structures
Week 9
Objectives : to learn more about hash tables, STL map, and balanced search trees Reference Carrano chapter 12 (Advanced Implementations of ADT table).
- * 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
- * Assume a hash table of size 11 using separate chaining. Insert the
same keys into the hash table.
- * What is the average case and worst case time complexity for
insertion, retrieval and deletion for each of the above type of hash tables.
- Assuming the following definition of a node, write the insert function to insert a node into a hash table using separate chaining.
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
- Consider keys which are strings. How can we create a hash function for strings which will convert the string to an int without too many collisions.
- What's the difference between an STL map and an STL multimap? Could we use a map for a simple-minded sorting algorithm? How about a multimap? Write the following function.
void multimapsort (int a[], int n)
// precondition : none
// postcondition : a is sorted in ascending order
- What is the efficiency of the above - justify your answer.
-
How could we find the smallest value in a multimap? What is the efficiency of this operation?
Write a c++ function to do this.
-
How could we find the largest value in a multimap? What is the efficiency of this operation?
Write a c++ function to do this.
- Discuss < algorithm> in STL - what functions are available? (Not examinable but will improve your programming productivity - need to have some idea of what is available)
All enquiries to Ros Ballantyne
