Please give answer for following

Topic:ALGORITHMS

Suppose G is a weighted directed graph. Further suppose p = is a shortest from v_0 to v_k, where the weight of the shorted path from v_0 to v_k is denoted by delta (v_0, v_k). Explain why if we relax the edges of p in the following order (v_0, v_1), (v_1, v_2), ..., (v_k - 1, v_k) then after we complete these k relax edges operation we have d[v_k] = delta (v_0, v_k) Consider the hashing scheme for a hash table where collisions are resolved by chaining and assume simple uniform hashing. In the case of a successful search, the expected running time is theta (1 + alpha) where alpha is the load factor. This was found by computing E[1 sigma^n_i = 1 (1 + sigma^n_j = i + 1 X_ij)] Consider the case of an unsuccessful search in a hash table where collisions are resolved by chaining. Again the expected running time is theta(1 + alpha) where alpha is the load Determine the expectation formula (such as equation (1)) that would be used to prove this (you need to prove just set-up/provide the formula). You need to explain what the random variables use your formula