Suppose we have a directed graph G and a weight matrix W such that W[i; j] is the time in
seconds it takes to traverse arc (i; j). In addition, suppose that each time you go through an intermediate
node there is a delay of 2 seconds. Thus the path i􀀀j􀀀k􀀀r takes time W[i; j]+2+W[j; k]+2+W[k; r]
to go from i to r. We want to nd the path with smallest delay from node x to all other nodes. We
assume all values in W are positive.
(a) Describe how to modify Dijkstra's algorithm to nd the least delay path from a start node x to
all other vertices. Specically, when we process a vertex v describe how to update the labels of all the
neighbors of v.
(b) What is the running time of your algorithm on a graph with n nodes and m arcs which is stored
using adjacency lists?
(c) What is the running time of your algorithm on a graph with n nodes and m arcs which is stored
using an adjacency matrix?
(d) Describe how to modify the all-pairs-shortest path algorithm to nd the least delay path between
all pairs of nodes. Analyze the complexity of your solution.
Use network
ows to nd an ecient solution for the following problem:
a) In a computer network there are p processors P1; P2; ::; Pp, and c communication lines C1;C2; :::;Cc
(with c > p. Each processor i has the ability to test ti lines per day and there is a list Li which contains
the communication lines that processor i is able to test. Subject to these constraints we would like to be
able to test all the communication lines every day. A testing schedule determines for each processor the
lines it should test. Give an ecient algorithm to nd a testing schedule or determine that no schedule
can test all lines in a single day. Give the run time of your algorithm in terms of p and c.
b) Same as a) but nd the minimum number of days to test all lines (and a schedule that achieves it).
(25) Problem 3. Suppose we are given a directed graph G;
a) We want to nd 3 edge disjoint paths from a designated starting vertex u to a specic destination
vertex d (or determine that no such paths exist). Describe an ecient algorithm to nd the paths and
give the running time of your solution.
b) Now suppose we have three dierent destinations d1; d2 and d3. We want to nd 3 paths from our
start vertex u, one to each of the destinations and we want these 3 paths to be edge [login to view URL] an
ecient algorithm to nd the paths and give the running time of your solution.
(25) Problem 4. For the input string: BABAACAABAACACAABAACCBABAAC
(a) Give a human code for this string (describe both your tree and the actual binary encoding of the
above string).
(b) Give the "high-level" Lempel-Ziv encoding of the above string where each match of length 3 or
longer is represented by a length, pointer pair, and otherwise by the actual input character.
(c) Now give the actual bit string representation for the encoding of part b) that would be produced
by encoding literals, lengths and pointers using two human trees. Again give the human trees used
followed by the encoding.
Dear sir,
I am strong in algorithm implementation, algorithm analysis and data structures. I have deep insight into algorithm complexity analysis in running time and space using Omega, Theta symbols and etc. I have also done many similar algorithm analysis assignments and I am strong in analysis. I can do the job with high quality.
Wait for your response
Thank you
BR
Hi,
I can help you with this project. I have 9 years of Software Engineering experience. I have strong expertise in Data Structures and am sure of finishing you the project meeting the quality expectations.
Regards,
Arunachalam