Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: DeJ!2ph{Al

added

Note did not exist

New Note

Front

Runtime of Johnson's Algorithm?

Back

Runtime of Johnson's Algorithm?

$O(|V| \cdot (|V| + |E|) \log |V|)$ (running dijkstra's n times, but allows negatives)

Field-by-field Comparison

Field	Before	After
Name		Johnson's Algorithm
Runtime		$O(\|V\| \cdot (\|V\| + \|E\|) \log \|V\|)$ (running dijkstra's n times, but allows negatives)<br><img src="paste-b0103885454d02688fec99eb8383f57710d89f68.jpg">
Requirements		No negative cycles
Approach		<ol><li><b>Add a New Vertex:</b><ul><li>Add a new vertex s to the graph and connect it to all vertices with zero-weight edges. </li> </ul></li><li><b>Run Bellman-Ford</b>:<ul><li>Use the Bellman-Ford algorithm starting from s to compute the shortest distance h[v] from s to each vertex v.</li><li>If a negative-weight cycle is detected, stop.</li></ul></li><li><b>Reweight Edges</b>: <ul><li>For each edge u → v with weight w(u, v), reweight it as: w′(u, v) = w(u, v) + h[u] − h[v]</li><li>This ensures all edge weights are non-negative.</li> </ul> </li><li><b>Run Dijkstra’s Algorithm:</b><ul><li>For each vertex v, use Dijkstra’s algorithm to compute the shortest paths to all other vertices.</li> </ul></li><li><b>Adjust Back</b>:<ul><li>Convert the distances back to the original weights using: d′(u, v) = d′(u, v) − h[u] + h[v]</li> </ul></li><li><b>End:</b></li><ul><li>The resulting shortest path distances between all pairs of vertices are valid.</li></ul></ol><div>The overall higher cost allows us to run pre-computation steps like B-F for "free"</div>
Use Case		All Pairs Shortest Path

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: GsU2XikyZ:

added

Note did not exist

New Note

Front

We use Johnsons over F-W, when the graph is sparse, like in a tree.

Back

We use Johnsons over F-W, when the graph is sparse, like in a tree.

Then the $|E|$ doesn't matter much in comparison to F-Ws $|V|^3$.

Field-by-field Comparison

Field	Before	After
Text		We use <b>Johnsons</b> over <b>F-W</b>, when the graph is {{c1:: sparse, like in a tree}}.
Extra		Then the $\|E\|$ doesn't matter much in comparison to F-Ws $\|V\|^3$.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: baz0GGlXM[

added

Note did not exist

New Note

Front

Why does naively adding the lowest-edge weight not work for Johnson's?

Back

Why does naively adding the lowest-edge weight not work for Johnson's?

We need the cost of the paths to stay the same relative to each other.

If we add a constant to each edge, long (length-wise) paths are penalised more. This means that the ordering of all paths by cost changes.

Field-by-field Comparison

Field	Before	After
Front		Why does naively adding the lowest-edge weight not work for Johnson's?
Back		We need the cost of the paths to stay the same relative to each other.<br><br>If we add a constant to each edge, long (length-wise) paths are penalised more. This means that the ordering of all paths by cost changes.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm

Note 4: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: ePS|dQ=3Ic

added

Note did not exist

New Note

Front

F-W implementation java, use 10000 or other high values but not Integer.MAX_VALUE.

Back

F-W implementation java, use 10000 or other high values but not Integer.MAX_VALUE.

Otherwise you might get an overflow.

Field-by-field Comparison

Field	Before	After
Text		<b>F-W</b> implementation java, use {{c1::10000 or other high values but not <b>Integer.MAX_VALUE</b>}}.
Extra		Otherwise you might get an overflow.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm

Note 5: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: hL7UB-)y6N

added

Note did not exist

New Note

Front

Runtime of Floyd-Warshall?

Back

Runtime of Floyd-Warshall?

$O(|V|^3)$

Field-by-field Comparison

Field	Before	After
Name		Floyd-Warshall
Runtime		$O(\|V\|^3)$
Requirements		No negative cycles
Approach		<ol><li><b>Initialise</b>: distance matrix D D[i][j] is the weight of the edge from $i \rightarrow j$ if it exists, $\infty$ otherwise<br></li><li><b>Iterate over intermediate</b>: for each vertex $k$ update D[i][j] = min(D[i][j], D[i][k] + D[k][j]). for all intermediate k from 1,...,n</li></ol><div><br></div><div>The final distance matrix D contains the shortest path from any i to j.</div><div><br></div><div><i>Note that this can also be done using a 3d DP table, the 2d is just optimised.</i><br></div>
Pseudocode		<img src="paste-f6965d427f4a2df5b61ba8dd2ee9c0f0a90baaf6.jpg"><br><div><b>Important</b>: Use a value like 10000 instead of Integer.MAX_VALUE in Java, as you get <b>overflows</b> otherwise.</div>
Use Case		All Pairs Shortest Path

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm

Note 6: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: hsaD+h{~n8

added

Note did not exist

New Note

Front

Reweighting in Johnson's algorithm:

We add a vertex $s$ and add a 0 cost edge from it to all vertices.
We then run B-F which determines the height of each vertex by the d[v] from start vertex $s$

Back

Reweighting in Johnson's algorithm:

We add a vertex $s$ and add a 0 cost edge from it to all vertices.
We then run B-F which determines the height of each vertex by the d[v] from start vertex $s$

Field-by-field Comparison

Field	Before	After
Text		Reweighting in Johnson's algorithm:<br><ol><li>We {{c1::add a vertex $s$}} and {{c1::add a 0 cost edge from it to all vertices}}.</li><li>We then {{c2::run B-F which determines the height of each vertex by the d[v] from start vertex $s$}} </li></ol>

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm

Note 7: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: j+9WeY4$!x

added

Note did not exist

New Note

Front

Explain why reweighting in Johnson's algorithm works:

Back

Explain why reweighting in Johnson's algorithm works:

Assigns a height $h(v)$ to each vertex. The new cost is then $\hat{c}(u, v) = c(u, v) + h(u) - h(v)$.

For a path $P = (s, v_1, v_2, \dots, v_n, t)$ the cost $\hat{c}(P) = \hat{c}(s, v_1) + \hat{c}(v_1, v_2) + \dots + \hat{c}(v_n, t)$ the costs cancel out in pairs: $c(s, v_1) + h(s) - h(v_1) + c(v_1, v_2) + h(v_1) - h(v_2) + \dots + c(v_n, t) + h(v_n) - h(t)$ gives $= c(P) + h(s) - h(t)$, which satisfies our requirements that the ordering stay the same.

Field-by-field Comparison

Field	Before	After
Front		Explain <b>why</b> reweighting in Johnson's algorithm works:
Back		Assigns a height $h(v)$ to each vertex. The new cost is then $\hat{c}(u, v) = c(u, v) + h(u) - h(v)$.<br><br>For a path $P = (s, v_1, v_2, \dots, v_n, t)$ the cost $\hat{c}(P) = \hat{c}(s, v_1) + \hat{c}(v_1, v_2) + \dots + \hat{c}(v_n, t)$ the costs cancel out in pairs: $c(s, v_1) + h(s) - h(v_1) + c(v_1, v_2) + h(v_1) - h(v_2) + \dots + c(v_n, t) + h(v_n) - h(t)$ gives $= c(P) + h(s) - h(t)$, which satisfies our requirements that the ordering stay the same.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm

Note 8: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: jBru?ce!L0

added

Note did not exist

New Note

Front

We use F-W over Johnsons, when the graph is very dense $|E| = \Theta(|V|^2)$.

Back

We use F-W over Johnsons, when the graph is very dense $|E| = \Theta(|V|^2)$.

Then the $n \cdot (n + m) $ becomes $n \cdot (n + n^2)$ which is $O(n^3)$.

Field-by-field Comparison

Field	Before	After
Text		We use <b>F-W</b> over <b>Johnsons</b>, when the graph is {{c1:: very dense $\|E\| = \Theta(\|V\|^2)$}}.
Extra		Then the $n \cdot (n + m) $ becomes $n \cdot (n + n^2)$ which is $O(n^3)$.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths

Note 9: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: o5O]N!`p|^

added

Note did not exist

New Note

Front

Floyd-Warshall, when is there a negative cycle?

Back

Floyd-Warshall, when is there a negative cycle?

There exists a negative cycle $\Leftrightarrow \exists v \in V \ : \ d^n_{v \rightarrow v} < 0$

In words: If there exists a path from a vertex to itself with negative weight (passing through any other vertex, i.e. $n$th iteration of the outer loop), then there exists a negative cycle that contains this vertex.

We can perform a negative cycle check at the end, by going over all diagonals.

Field-by-field Comparison

Field	Before	After
Front		Floyd-Warshall, when is there a negative cycle?
Back		<div>There exists a negative cycle $\Leftrightarrow \exists v \in V \ : \ d^n_{v \rightarrow v} < 0$</div><div><br></div> <div>In words: If there exists a path from a vertex to itself with negative weight (passing through any other vertex, i.e. $n$th iteration of the outer loop), then there exists a negative cycle that contains this vertex.</div><br><div>We can perform a negative cycle check at the end, by going over all diagonals.</div>

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm

Note 10: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: CJsa&>C5sO

added

Note did not exist

New Note

Front

Kruskal's Algorithm can be executed in $O(|E| + |V|\log|V|)$ time?

Back

Kruskal's Algorithm can be executed in $O(|E| + |V|\log|V|)$ time?

no, we need to sort the edges which takes at least $|E| \log |E|$ time.

Field-by-field Comparison

Field	Before	After
Front		Kruskal's Algorithm can be executed in $O(\|E\| + \|V\|\log\|V\|)$ time?
Back		no, we need to sort the edges which takes at least $\|E\| \log \|E\|$ time.

Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm

Note 11: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Fn+W}!cgj0

added

Note did not exist

New Note

Front

If we know that shortest paths have a length of max $h$, runtime of algo to find them?

Back

If we know that shortest paths have a length of max $h$, runtime of algo to find them?

We can find them in $O(h|E|)$ using B-F since we only need to relax $h$ times.

Field-by-field Comparison

Field	Before	After
Front		If we know that shortest paths have a length of max $h$, runtime of algo to find them?
Back		We can find them in $O(h\|E\|)$ using B-F since we only need to relax $h$ times.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm

Note 12: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Mv|.Tnx#vx

added

Note did not exist

New Note

Front

A graph with distinct ege weights has one unique MST.

Back

A graph with distinct ege weights has one unique MST.

There is one unique safe-edge.

Field-by-field Comparison

Field	Before	After
Text		A graph with {{c1::distinct ege weights}} has {{c2::one unique MST}}.
Extra		There is one unique safe-edge.

Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees

Note 13: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Qv/bX3RU0v

added

Note did not exist

New Note

Front

How does the number of ZHK's change in Boruvka's for each round?

Back

How does the number of ZHK's change in Boruvka's for each round?

The number of component halves in each round, thus $\log |V|$ iterations worst case.

Field-by-field Comparison

Field	Before	After
Front		How does the number of ZHK's change in Boruvka's for each round?
Back		The number of component halves in each round, thus $\log \|V\|$ iterations worst case.

Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm

Note 14: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: k%duL(GzS|

added

Note did not exist

New Note

Front

In every connected graph $G$, when executing Kruskal using Union-Find, the representative repr[u] changes $O(\dots)$ times:

Back

In every connected graph $G$, when executing Kruskal using Union-Find, the representative repr[u] changes $O(\dots)$ times:

$O(\log_2 |V|)$, as we always at least double the size of the representative (we merge smaller into bigger, and repr[u] changes if it's the smaller one).

Field-by-field Comparison

Field	Before	After
Front		In every connected graph $G$, when executing Kruskal using Union-Find, the representative <b>repr[u]</b> changes $O(\dots)$ times:
Back		$O(\log_2 \|V\|)$, as we always at least double the size of the representative (we merge smaller into bigger, and repr[u] changes if it's the smaller one).

Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm

Note 15: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID:

s0knxb/


            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm
  
  
    The height \(h(v)\) in Johnson's Algorithm is always negative \(\leq 0\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm
  
  
    The height \(h(v)\) in Johnson's Algorithm is always negative \(\leq 0\).
    
    
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            The height&nbsp;\(h(v)\)&nbsp;in Johnson's Algorithm is {{c1::always negative&nbsp;\(\leq 0\)}}.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm

Field	Before	After
Text		The height \(h(v)\) in Johnson's Algorithm is {{c1::always negative \(\leq 0\)}}.


        
        
            Note 16: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Classic

                GUID: wxuX$c!)%k
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm
  
  
    A graph with this DP table from F-W:

contains ___ negative cycles.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm
  
  
    A graph with this DP table from F-W:

contains ___ negative cycles.
    
    no (there is no diagonal \(< 0\))
  






                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            
                            A graph with this DP table from F-W:<br><img src="paste-deae0d6c4a31dc3e71c5f654f12387c82b186739.jpg"><br>contains ___ negative cycles.
                        
                        
                        
                            Back
                            
                            <b>no</b>&nbsp;(there is no diagonal&nbsp;\(&lt; 0\))
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm

Field	Before	After
Front		Kruskal's Algorithm can be executed in \(O(\|E\| + \|V\|\log\|V\|)\) time?
Back		no, we need to sort the edges which takes at least \(\|E\| \log \|E\|\) time.

Field	Before	After
Front		In every connected graph \(G\), when executing Kruskal using Union-Find, the representative <b>repr[u]</b> changes \(O(\dots)\) times:
Back		\(O(\log_2 \|V\|)\), as we always at least double the size of the representative (we merge smaller into bigger, and repr[u] changes if it's the smaller one).

Field	Before	After
Front		A graph with this DP table from F-W:<br><img src="paste-deae0d6c4a31dc3e71c5f654f12387c82b186739.jpg"><br>contains ___ negative cycles.
Back		<b>no</b> (there is no diagonal \(< 0\))