Ex. 1 — Hash tables
In this exercise we want to estimate the maximum number of keys per slot we can expect when inserting n keys into n slots of a hash table.
Given a hash table with n slots, n keys are equiprobably hashed to each slot. Let M denote the maximum number of keys in a slot once they have all been inserted.
1. For any positive integer k, show that the probability Pk that exactly k keys hash to a same slot is
.
2. Prove that the probability Pk′ , for the slot with the most keys to have exactly k keys, is less or equal to nPk.
3. Prove that Pk <ek/kk.
* 4. Show that for any positive integer k ≥ c log n/log log n, for some constant c 1, Pk′ < 1/n2. 5. Denoting the expected value of M by E(M), observe that
c log n E ,
log log n
and conclude that E .
Hint: for question 3 apply Stirling formula.
Ex. 2 — Minimum spanning tree
Let G be a graph and T be a minimum spanning tree for G. Write the pseudocode of an algorithm which determines the minimum spanning tree of the graph G when the weight of an edge not in T is decreased.
Ex. 3 — Simple algorithms
* 1. Given two n-bits integers stored in two arrays, explain how to compute their sum in an n + 1-bits array. Write the corresponding pseudocode.
2. One decides to multiply two integers x and y by writing a function mult(x,y) returning 0 if one of them is 0 and otherwise returning the sum of a recursive call on mult, with parameters 2x and ⌊y/2⌋, and x · (y mod 2).
a) Express this algorithm as pseudo-code.
b) Prove the correctness of this algorithm.
Ex. 4 — Problem
Given twenty five horses determine the three fastest ones, in the right order, knowing that no more than five can race at a time. What is the minimum number of races necessary? Detail a general algorithm which solves the problem.
Ex. 5 — Critical thinking
1. The Knapsack problem is defined as follows. Given a set S and a number n find a subset of S whose elements add up exactly to n. Which of the following algorithms solve the Knapsack problem?
• Fit the knapsack with the smallest items first.
• Fit the knapsack with the largest items first.
* 2. In the course (Example 1.??) it is mentioned that m should be “a prime not too close from a power of 2” in order for the hash function H(k) = k mod m to be a good choice. Explain.
3. Provide an example of a greedy algorithm which is locally optimal while not being globally optimal.
Provide all the necessary details to support your claim.
