markormesher / cs-notes Goto Github PK

The function SUCCESSIVE_SP on page 31 may have an error. On line 25, your code uses '+' to combine the existing and new flow, however on the Slides it is using xor '⊕'. Not sure if the '+' is also acceptable but I thought I'd point it out.

On page 10 where Bellman Ford is illustrated, the algorithm contains the return true statement, indicating no negative cycles, inside the for loop when it should be outside, meaning it returns true after every edge has been checked.

Currently

fun BELLMAN􀀀FORD(G, w, s):
2
3 // run initialisation and relaxation:
4 INITIALISE(G, s)
5 for i from 1 to n 􀀀 1, do:
6   for each edge (u, v) in G, do:
7     RELAX(u, v, w)
8
9 // determine outcome:
10 for each edge (u, v) in G, do:
11   if (d[v] > d[u] + w(u, v)):
12     return FALSE // negative cycle reachable from s
13 else:
14     return TRUE

Should be:

fun BELLMAN􀀀FORD(G, w, s):
2
3 // run initialisation and relaxation:
4 INITIALISE(G, s)
5 for i from 1 to n 􀀀 1, do:
6   for each edge (u, v) in G, do:
7     RELAX(u, v, w)
8
9 // determine outcome:
10 for each edge (u, v) in G, do:
11   if (d[v] > d[u] + w(u, v)):
12     return FALSE // negative cycle reachable from s
13 return TRUE

Question 5

Line 9: Close a complexType type with a simpleType tag

Question 6

Line 7: Same issue as in Q5.

Amazing notes Mark! 👍

There's a typo for OM, page 21, under residual capacity:

f(u,v) should equal 3 in the example, currently it's f(u,v) = 2.

It would be cool if these notes go on to be used by other students in the future. It would be even cooler if those students could add to them and fix the odd typo. Is it worth converting these notes to Markdown so others can easily make suggestions?