1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Course week 13 - Balanced binary trees »
  3. Exercises for the week 14 exercise session

Exercises for the week 14 exercise session

Task 1

As data we have coordinates (x,y), to which are attached a colour. X and y coordinates are of type unsigned int, and colour is of type string. The data is stored in a chained hash table, with the coordinate as a key. The hash table has 7 buckets, and the hash function in use is h((x,y)) = 13*x*y mod 7.

  1. Add the following elements into the hash table and tell the contents of each bucket after elements have been added: (1, 1):red, (2,2):green, (11,8):blue, (154, 987):yellow, (63, 5):white
  2. What is the load factor of the hash table after elements have been added?
  3. Is the hash function good? If not, come up with a better one.

Extra: find out where the mystery number 0x9e3779b9 in hash_combine comes from.

Task 2 - Project 2 orienting questions

  1. Which graph algorithms we have had in this course? Describe shortly the special features of each, and for which kind of tasks each of them are suited.
  2. Can there be multiple connections between two given affiliations?
  3. Where can I find Project 2 instructions? On which modules are Project 2 graders?