VE477-Homework 1 Hash tables, Minimum Spanning Tree and Simple Algorithms Solved

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.