You are probably being recorded (and transcribed)
Approximate overview
If you’d like to suggest token events, please let me know in advance of class.
When you finish grading SoLA 12, will we get another grade report?
Yes.
When you finish grading SoLA 13, will we get another grade report?
Yes.
When you finish grading SoLA 14, will we get another grade report?
Yes.
If we need help finishing a lab, who do we ask for help?
Evening tutors, if they are available.
Sam on Teams.
Classmates.
What happens if the graders don’t grade MP7 and MP9 promptly?
Sam will probably work longer days and catch those up.
Can we have another mentor session during finals week?
DM me if you’d like one, and I’ll consider it.
If we forgot the CHANGES.txt files on previous redos, should we resubmit?
Nah.
When would we use these algorithms?
Dijkstra’s algorithm is likely at the root of Google Maps and such.
MSTs might be used to decide which streets to prioritize in case of a snowstorm so that emergency workers can reach every house (or at least every corner).
MSTs can also be used to prioritize connections to restore in an electrical grid.
Can you tell me more about the “fail fast” policy for iterators?
If we change a graph (or any structure, for that matter) while we’re iterating it, the iterator may no longer correctly show the rest of the graph (structure). A “fail fast” policy suggests that as soon as the graph changes, the iterator should become invalid and report so.
How else might we represent a graph?
Another common approach is to use an adjacency matrix, a matrix whose rows and columns are labeled with vertex names/numbers and whose values are the distance between the two vertices.
We could also use nodes and a linked structure.
Why would we choose one representation over another?
The approach we used in class (a variant of adjacency lists) is good when you want to iterate edges (either edges from particular nodes or all edges). However, it’s not as good when you want to pick pairs of vertices and find the distance between them.
Adjacency matrices are good when you want to find the distances between pairs of vertices (it’s O(1)). However, they require a lot of space and are not quite as efficient for iterating edges.
I’m sure that at this point in your career, you can perform similar analyses.
See the list of LOs. There are fifty! of them.
But we’ve also learned some other things …
To find the shortest path from SOURCE to SINK,
Indicate that all vertices have infinite distance from SOURCE
Indicate that SOURCE has a distance of 0 from itself
While unmarked(SINK) and there exists an unmarked node with finite distance fr
om SOURCE
Find the nearest unmarked vertex, U
Mark U
For each unmarked neighbor, V, of U
If distanceTo(U) + edgeWeight(U,V) < distanceTo(V)
Note that the best known path to V is the path to U plus the
edge from U to V.
Update the distance to V
Report the path to SINK, if there is one
How might you keep track of the best known distance to each vertex?
An array of distances, indexed by vertex number.
int[] distances = new int[vertices.length];
or
Integer[] distances = new Integer[vertices.length];
How might you keep track of the path that gives that distance?
// The preceding vertex in the shortest path to each vertex
int[] prevNode = new int[vertices.length];
or
// The last edge in the shortest path to each vertex
Edge[] incoming = new Edge[vertices.length];
or
// The shortest known path to each vertex
List<Edge> shortestPaths = new List<Edge>[vertices.length];
How might you find the nearest unmarked vertex?
We use a for loop to iterate through the distances array.
At each point, we make sure that the distance is not “infinity” and that the node is not marked. If so, we compare to the best we’ve seen.
How might you find all the edges from a vertex?
We use Graph.edgesFrom(vertex).