Description

Most Important guidelines
• Refrain from collaborating with the students of other groups. If any evidence is found that confirms copying, the penalty will be very harsh. Refer to the website at the link: https://cse.iitk.ac.in/pages/AntiCheatingPolicy.html regarding the departmental policy on cheating.
General guidelines
1. There are three problems in this assignment: 2 Difficult problems and 1 Easy. Eachdifficult problem carries 100 marks, and the easy one carries 70 marks. Attempt only one of the 3 problems.
2. You are strongly discouraged to submit the scanned copy of a handwritten solution.Instead, you should prepare your answer using any text processing software (LaTex, Microsoft word, …). The final submission should be a single pdf file.
3. You need to justify any claim that you make during the analysis of the algorithm.But you must be formal, concise, and precise.
5. Naming the file:
The submission file has to be given a name that reflects the information about the assignment number, version attempted (difficult/moderate/esay), and the roll numbers of the 2 students of the group. For example, you should name the file as D 2 Rollnumber1 Rollnumber2.pdf if you are submitting the solution for the difficult version of the 1st assignment. In a similar manner, E 2 Rollnumber1 Rollnumber2.pdf if you are submitting the solution for the easy problem of the 2nd assignment.
6. Both students of a group have to upload the identical copy of their final submission.Be careful during the submission of an assignment. Once submitted, it can not be re-submitted.
Difficult
1. A large collection of mobile wireless devices can naturally form a network in which the devices are the nodes, and two devices x and y are connected by an edge if they are able to directly communicate with each other (e.g., by a short-range radio link). Such a network of wireless devices is a highly dynamic object, in which edges can appear and disappear over time as the devices move around. For instance, an edge (x,y) might disappear as x and y move apart from each other and lose ability to communicate directly.
In a network that changes over time, it is natural to look for efficient ways of maintaining a path between certain designated nodes. There are two opposing concerns in maintaining such a path: we want paths that are short, but we also do not want to have to change the path frequently as the network structure changes. That is, we would like a single path to continue working, if possible, even as the network gains and loses edges. Here is a way we model this problem.
Suppose we have a set of nodes V , and at a particular point in time there is a set E0 of edges among the nodes. As the nodes move, the set of edges changes from E0 to E1, then to E2, then to E3, and so on, to an edge set Eb. For i = 0,1,2,…,b, let Gi denote the graph (V,Ei). So if we were to watch the structure of the network on the nodes V as a “time lapse”, it would look precisely like the sequence of graphs G0,G1,…,Gb. We will assume that each of these graphs Gi is connected.
Now consider two particular nodes s,t ∈ V . For an s − t path P in one of the graphs Gi, we define the length of P to be simply the number of edges in P, and we denote this by `(P). Our goal is to produce a sequence of paths P0,…,Pb so that for each i, Pi is an s − t path in Gi. We want the paths to be relatively short. We also do not want there to be too many changes – points at which the identity of the path switches. Formally, we define changes(P0,…,Pb) to be the number of indices i (0 ≤ i ≤ b − 1) for which Pi 6= Pi+1.
Fix a constant K > 0. We define the cost of the sequence of paths P0,…,Pb to be
b
cost(P0,P1,…,Pb) = X`(Pi) + K · changes(P0,P1,…,Pb)
i=0
Give a polynomial time algorithm to find a sequence of paths P0,…,Pb of minimum cost.
2. We have already seen Bellman Ford algorithm which solves single source shortest paths (SSSP) problem in O(mn) time for directed graphs with potentially negative weighted edges but no negative cycle. Consider a related problem of finding shortest paths between every pair of vertices in such a graph. This problem is commonly known as the All-Pair Shortest Paths (APSP) problem. One can trivially solve APSP problem in O(mn2) time by executing Bellman Ford algorithm on each of the n vertices. However, there exists a better and novel algorithm to solve APSP problem which takes O(n3) time. Interestingly, it is also based on the Dynamic Programming technique, though applied in a manner which is totally different from Bellman Ford algorithm. We now provide some notations in the following paragraph which will guide you towards the desired algorithm.
Recall that the vertices in a graph are labeled (numbered) from 1 to n. Let Pk(i,j) be the set all paths from vertex i to vertex j whose intermediate vertices have label at most k. Let pk(i,j) be the shortest path from the set Pk(i,j) and δk(i,j) be the corresponding distance (length of the shortest path). Try to explore answers to the following questions : What would δ0(i,j) mean ? What would δn(i,j) mean ? How would pk(i,j) look like for any 0 < k ? Use the insight from the answers of the above questions to derive a recurrence for δk(i,j). Interestingly, the final algorithm consist of a few nested for-loops.
As a part of the assignment, you have to achieve the following two objectives.
(a) Design an algorithm which processes a given directed graph in O(n3) time and outputs a n × n matrix D storing all-pairs distances in the graph. The space used by the algorithm has to be O(n2). As a hint, note that the code of this algorithm uses just three nested for-loops and is very short and simple.
(b) Extend the above algorithm to output an O(n2) size data structure using which any shortest path can be reported in optimal time, that is, the time of the order of the number of edges on the shortest path. You must also describe the corresponding algorithm to report any shortest path using the data structure.
An important note: Instead of searching for the solution of the above problem elsewhere, make a sincere attempt to solve it on your own. Take this problem as an opportunity to improve your skills of dynamic programming; you will realize that it will be a very satisfying experience.
Easy