Exercise 1 - Hash tables (30 pts) a) Insert the following keys in a hash table of size 13: 38, 12, 0, 26, 17, 52, 61. You may use the hash function h(x) = 7 - x mod 7 to resolve collisions. b) What is the overall running time of your algorithm? Does sorting the elements first improve it? Exercise 2 - MST (30 pts) Prims algorithm allows us to find the minimum spanning tree in a weighted graph. It is identical to Kruskal's one (except for the update rule when processing a vertex of the graph). a) Apply Prims algorithm to find the MST for the following graph. 5 6 6 4 7 5 2 b) Explain briefly how you compute its asymptotic running time. c) Which programming strategy does use? Exercise 3 - Red-black trees (40 pts) Read about red-black trees and answer the following questions. a) What are the basic operations supported by this data structure? b) What is the running time of inserting an element in a red-black tree? c) Briefly explain how an insertion is performed in such a data structure. d) Show the steps of inserting the following keys into an initially empty red-black tree: 5, 3, 6, 9, 14, 7, 4 Note: you may build your tree by showing the elements of the red-black tree at different levels (using 2 different colors). For example, the steps to insert the elements 12, 19, 62 are: 12 12 -19 19 12 62