Distributed Programming and Networking problems to be solved

To be completed within 36 hours after project is rewarded. Examples of some problems to be solved, please check the PDF for complete. 1. Consider the flooding algorithm in an arbitrary network G = (V, E): 1) Each node acts as both a transmitter and a receiver, and 2) Each node tries to forward every message to every one of its neighbors except the source node. 1.1. Formulate the algorithm in pseudo-code starting from a given node. 1.2. Prove that your algorithm is correct in that it terminates within finite time, and all entities will receive the information held by the initiator. 1.3. Determine an upper bound (formula) on the number of message trans-missions required by the algorithm (Your answer should be expressed in terms of parameters: number n of vertices, number m of edges). 2. If all edges of a graph G have distinct weights, then there is exactly one MST for G. 3. What is the competitive ratio of the zig-zag linear search algorithm for one robot when the expansion factor is some fixed value a > 1. Give the “formal” argument and explicit formula as in the lecture (Recall that we will use the expansion factor a = 2.) is repeated.