Exercise 1a - Hash table-theory¶

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.

Exercise 1b - Hash Function - mystery number¶

Explain how the mystery number 0x9e3779b9 in boost::hash_combine (same as hash function for coord in customtypes.hh in prg1 and prg2) is computed?

Exercise 2a - Kruskal’s algorithm-theory¶

A spanning tree of a graph is the subset of graph edges so that they connect all nodes and form a tree, i.e. the result doesn’t contain cycles. Typically there are many possible spanning trees for a graph. The minimal spanning tree is the one where the sum of its edge weights is smallest. A minimal spanning tree is useful, if there is a need to minimize the ”total cost”, i.e. create the cheapest possible graph where you can still reach every node. You can meet these problems for example when configuring and building communications networks.

Kruskal’s algorithm is one way to create the minimal spanning tree. Read about the algorithm from Wikipedia article Kruskal’s algorithm How does the algorithm work and create the minimal spanning tree? Can you notice why it creates specifically a minimal spanning tree? Kruskal’s algorithm works also if the graph is not connected. Then it automatically creates a set of spanning trees, i.e. a forest.

Exercise 2b - Kruskal’s algorithm-implementation¶

Run Kruskal’s algorithm for the graph below. Return a list of the remaining edges.