Questions preceded by a * are optional. Although they can be skipped without any deduction, it is important to know and understand the results they contain.
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
(n
)
k
(1 − n
)
n−k
(k)
.
1
1
n
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
E (M) ≤ Pr (
M >
c log n
) n + Pr
(
M ≤
c log n
)
c log n
,
log log n
log log n
log log n
• )
log n
and conclude that E (M) = O
.
log log n
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.
