Please list the names of the other members of your peer group for this week and the number of extra credit points you think they deserve for their participation in group work on Tuesday and Thursday combined.
In class we learned how the problem of scheduling a set of jobs with time required and precedence constraints can be modeled using a Directed Acyclic Graph.
We also discussed how it would be preferable to use an existing algorithm so
we don’t have to go to the trouble of developing a new one and proving that it
is correct. The DAG-Shortest-Paths
algorithm is promising, but it computes
shortest paths while we need longest paths in order to find the longest chain
of precedence constraints. A simple transformation to the problem
representation makes it possible to use DAG-Shortest-Paths
: negate the
weights!
Your problem here is to solve the job scheduling problem for the jobs shown
in the table using DAG-Shortest-Paths
. You will fill in the edge weights,
run DAG-Shortest-Paths
on the modified DAG, and transform the results into a
table for each job of the time that it can start running and the time it will
finish. (The start time of s is time 0.)
job start end
----- ----- -----
j1
j2
j3
j4
j5
j6
j7
Last job finishes at:
Run Dijkstra’s algorithm on the graph shown, using vertex a
as the start
vertex. For each step of the algorithm, show what vertex is dequeued and the
distance estimate v.d it had at the time it is put into S. (To help the
TA debug, you may wish to show the entire graph each iteration.) Then identify
the final distance estimates and explain what distance estimate is in error
and why.
Step v put in S v.d
---- ---------- ---
1.
2.
3.
4.
5.
(Final distance estimates are in column v.d.)
**What distance estimate(s) is(are) in error, and explanation of why:**
problem we just showed above.
(a) First we construct the graph G’ defined in the first step of Johnson’s algorithm by adding a new vertex s
with edges of cost 0 to all other vertices. Run Initialize-Single-Source
(the first step of Bellman-Ford
) on this graph (so vertices are labeled by v.d, either 0 or ∞). Use the template below to show the resulting graph. (Large version of templates will be emailed to you.)
(b) Complete running the Bellman-Ford
algorithm on the graph you just constructed, using vertex s
as the start vertex. For Pass #0 (first line), copy the values of v.d from the graph above and nil for v.π. Then show updated values of d and π for each vertex after each pass of loop at line 2 (at the end, v.d = δ(s,v), which will be used in problem 5). To make it easier for the TA to grade, let’s all relax the edges in the same order, namely lexical order of pairs: ` (a,b), (a,c), (a,d), (b,c), (b,e), (c,d), (d,e), (e,d), (s,a), (s,b), (s,c), (s,d), (s,e).`
Pass# a._d_ a.π b._d_ b.π c._d_ c.π d._d_ d.π e._d_ e.π
----- --- --- --- --- --- --- --- --- --- ---
0.
1.
2.
3.
4.
5.
δ(s,v)):
(a) Using the results of problem 4 and defining h(v) = δ(s,v) ∀ v ∈ V, draw the revised graph G (with s
removed) with edge weights ŵ(u,v) = w(u,v) + h(u) − h(v) and after Initialize-Single-Source
(vertices are labeled by v.d, either 0 or ∞). (Refer to 4b above for h values.)
Source:
(b) Run Dijkstra’s algorithm on the resulting graph, again using vertex a
as the start vertex. Show the resulting δ̂(a,v) as labels inside the vertices.
Step v put in S v.d
---- ---------- -----
1.
2.
3.
4.
5.
(c) Now map the distances above back to what they would be under w by using δ(a,v) = δ̂(a,v) − h(u) + h(v), referring to your results of 4b for h. Note that this should get the correct path that was missed in problem 2!
Johnson’s algorithm would now repeat 5(a) and 5(b) on each of the other vertices b, c, d, and e. However, you do not need to turn in the other runs of Dijkstra. We’ll compute the other paths below.
Construct and show the matrix D(0) for the graph shown again here. Then run Floyd-Warshall, showing the matrix D(k) for each value of k. The final matrix should have the same values as those computed in problem 5 for the start vertex a, as well as values for all other start vertices. To make it clear what order to process the vertices and easier for the TA to grade, we will number the vertices in alphabetical order: for k=1, k is vertex a; for k=2, k is vertex b, etc.
Dan Suthers Last modified: Sun Apr 20 03:32:41 HST 2014