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.

- If all three members besides yourself were present at some time, you have a total of 3 points to allocate.
- If only two members besides yourself were present, you have a total of 4 points to allocate.
- If only one other member was present, you have a total of 6 points to allocate.
- You need not allocate all the points available to you. Points allocated to yourself will not be recorded.

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.

- Edges from j_i_s to j_i_f are weighted with the time required to do job j_i_.
- If job j_j_ cannot start until job j_i_ finishes, a 0 weighted edge is put from j_i_f to j_j_s.
- There is an implicit 0 weight edge from start node s to every j_j_ s and from every j_j_ f to f.

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 *. You will fill in the edge weights,
run

`DAG-Shortest-Paths`

`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 ```
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