Midterm Solutions

1)

   0 1 2 3 4 5
  _____________
0| 0 0 1 1 0 0
1| 0 0 0 0 1 1
2| 1 0 0 0 1 0
3| 1 0 0 0 0 1
4| 0 1 1 0 0 1
5| 0 1 0 1 1 0

2)
A valid topological ordering

e,c,a,h,d,f,i,j,g

3)
Correct Choice: Bellman-Ford
Dijkstra's algorithm- is not guaranteed to work with negative edge weights
Bellman-Ford- works with negative weights and solves an s-t problem
Topological order relaxation - does not handle cycles
Johnson's algorithm - solves all pairs shortest path, does more work than Bellman-Ford

4)
a. The MST - AD,DB,AC,EC

Starting tour at A- Start changes answers to b and c.
b. A-> D -> B -> D -> A -> C -> E -> C -> A

c. A-> D -> B -> C -> E -> A