CS345-Assignment II Solved

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
There are n jobs: J1,...,Jn. Job Ji has a deadline di and a required processing time ti, and all jobs are available to be scheduled starting at time ti, and all jobs are available to be scheduled starting at time s. For a job i to be done, it needs to be assigned a period from si ≥ s to fi = si +ti, and different jobs should be assigned nonoverlapping intervals. As usual, such an assignment of times will be called a schedule.

Each job must either be done by its deadline or not at all. We will say that a subset J of jobs is schedulable if there is a schedule for the jobs in J so that each of them finishes by its deadline. Your problems is to select a schedulable subset of maximum possible size and give a schedule for this subset that allows each job to finish by its deadline.