Runtime of
Prim
Runtime: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}
Approach:
Uses:
?Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
cKo%p6:M08
Before
Front
Back
After
Front
Back
Runtime of
Prim
Runtime: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}
Approach:
Uses: Runtime: {{c1::
\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}
Approach:
Uses:
?Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Name | <div style="text-align: center;"><b>Prim</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::We start at a given vertex. To this subtree we add one-by-one the cheapest edge connecting the subtree to another component until all vertices are connected. The implementation is very similar to Dijkstra.}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}</div> | <div style="text-align: center;"><b>Prim</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::We start at a given vertex. To this subtree we add one-by-one the cheapest edge connecting the subtree to another component until all vertices are connected. The implementation is very similar to Dijkstra.}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}<b>Runtime</b>: {{c1::</div><div>\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::We start at a given vertex. To this subtree we add one-by-one the cheapest edge connecting the subtree to another component until all vertices are connected. The implementation is very similar to Dijkstra.}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}</div> |
Note 2: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
kn@H8`z>0t
Before
Front
Runtime of DFS (Depth First Search)?
Back
Runtime of DFS (Depth First Search)?
\( \mathcal{O}(|E| + |V|) \) (using Adjacency List)
Can be efficiently implemented using a stack.
Can be efficiently implemented using a stack.
After
Front
Runtime of DFS (Depth First Search)?
Back
Runtime of DFS (Depth First Search)?
\( \mathcal{O}(|E| + |V|) \) (using Adjacency List)
Can be efficiently implemented using a stack.
Can be efficiently implemented using a stack.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Use Case | Find Connected Components, Toposort |
Note 3: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
y@l`JCIJ<4
Before
Front
Runtime of BFS (Breadth First Search)?
Back
Runtime of BFS (Breadth First Search)?
\(O(|V|+|E|)\) (Adjacency List)
The runtime of BFS:
The runtime of BFS:
- each loop we take \(O(1 + \deg(u))\) time (go through the vertex \(u\)'s edges
- We loop a total of \(|V|\) times (we visit each edge max. 1 time)
After
Front
Runtime of BFS (Breadth First Search)?
Back
Runtime of BFS (Breadth First Search)?
\(O(|V|+|E|)\) (Adjacency List)
The runtime of BFS:
The runtime of BFS:
- each loop we take \(O(1 + \deg(u))\) time (go through the vertex \(u\)'s edges
- We loop a total of \(|V|\) times (we visit each edge max. 1 time)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Use Case | Shortest Path in a directed graph | Shortest Path in a directed graph, Bipartite Test |
Note 4: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
H>#zg]RQy9
Previous
Note did not exist
New Note
Front
Do we need positive edges for an MST?
Back
Do we need positive edges for an MST?
No, the algorithms can handle negative edges as there are no distances to compute.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Do we need positive edges for an MST? | |
| Back | No, the algorithms can handle negative edges as there are no distances to compute. |
Note 5: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
added
Note Type: Algorithms
GUID:
dl`?#
Previous
Note did not exist
New Note
Front
Runtime of Boruvka's Algorithm?
Back
Runtime of Boruvka's Algorithm?
\(O((|V| + |E|) \cdot \log |V|)\)
During each iteration, we examine all edges to find the cheapest one: \(O(|V| + |E|)\):
During each iteration, we examine all edges to find the cheapest one: \(O(|V| + |E|)\):
- Run DFS to find the connected components: \(O(|V| + |E|)\)
- Find the cheapest one \(O(|E|)\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Name | Boruvka's Algorithm | |
| Runtime | \(O((|V| + |E|) \cdot \log |V|)\)<br><br>During each iteration, we examine all edges to find the cheapest one: \(O(|V| + |E|)\):<br><ol><li>Run DFS to find the connected components: \(O(|V| + |E|)\)</li><li>Find the cheapest one \(O(|E|)\)</li></ol>We iterate a total of \(\log_2 |V|\) times as each iteration halves the number of connected components. | |
| Requirements | undirected, connected, weighted Graph. | |
| Approach | <ol><li>For Boruvka, we start with the set of edges \(F = \emptyset\). We treat each of the <em>isolated vertices</em> of the graph as it’s <em>own connected component</em>.</li><li>Each vertex marks it’s cheapest outgoing edge as a <em>safe edge</em> (making use of the cut property). We add these to \(F\).</li></ol><ul><li>Note that some of the edges might be chosen by both adjacent vertices, we still only add them once.<br><img src="paste-053ccf0acc6d560628bd8518b928a0d6c2687cb1.jpg"></li></ul><ol><li>Now, repeat by finding the cheapest outgoing edge for each component. Do this until all are connected.</li><li>\(F\) constitutes the edges of the MST.</li></ol> | |
| Pseudocode | <img src="paste-7f2fe108c849a581658c052b210a79e0897f8fe0.jpg"> | |
| Use Case | Find an MST |
Note 6: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
added
Note Type: Algorithms
GUID:
m`oj
Previous
Note did not exist
New Note
Front
Runtime of Prim's Algorithm?
Back
Runtime of Prim's Algorithm?
\(O((|V| + |E|) \log |V|)\) (Adjacency List, otherwise \(\Theta(|V|^2)\) like Dijkstra's)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Name | Prim's Algorithm | |
| Runtime | \(O((|V| + |E|) \log |V|)\) (Adjacency List, otherwise \(\Theta(|V|^2)\) like Dijkstra's) | |
| Requirements | undirected, connected, weighted Graph | |
| Approach | <div>Prim’s algorithm starts with a single vertex and grows the MST outwards from that seed.</div> <ol> <li><strong>Initialisation:</strong><ul> <li>Select and arbitrary starting vertex \(s\) and empty set \(F\)</li> <li>Set \(S = {s}\) tracks the vertices in the MST</li> <li>Each vertex gets a <code>key[v] =</code> representing the cheapest known connection cost to \(v\):<ul> <li>\(\infty\) if no edge connects \(s\) to \(v\)</li> <li>\(w(s, v)\) if edge \((s, v)\) exists</li> </ul> </li> <li>Use a priority queue \(Q\) (<em>Min-Heap</em>) to store the vertices, in order of lowest <code>key</code> cost</li> </ul> </li> <li><strong>Iteration:</strong><ul> <li><em>Select and add</em> Extract the vertex \(u\) with the minimum <code>key</code> from \(Q\). This is the cheapest to connected to the current MST. Add \(u\) to \(S\).</li> <li><em>Update Neighbours</em> For each neighbour <b>\(v\) </b>of \(u\) <em>not</em> in \(S\):<ul> <li>If \(w(u, v) < \text{key}[v]\) update <code>key[v] = w(u, v)</code> and update the priority in \(Q\).<ul> <li>This discovers potentially cheaper connections to vertices outside the current MST. If a <em>cheaper edge</em> to \(v\) is found, the current value in <code>key[v]</code> cannot be part of the MST</li> </ul> </li> </ul> </li> </ul> </li> <li><strong>Termination:</strong> When \(Q\) is empty, all vertices are in \(S\) and connected, and the edges chosen are in the MST (tracked in the set \(F\) through updates).</li></ol> | |
| Pseudocode | <img src="paste-7d28e852262c66f4efd97974921c1a6120b2c2a1.jpg"> | |
| Use Case | Find MST |
Note 7: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
x@F_EbzW}O
Previous
Note did not exist
New Note
Front
Prim's Algorithm Invariants:
The priority queue \(H = V \setminus S\) (\(V\) set of all vertices, \(S\) vertices currently in the MST) never contains a vertex already in the MST.
The priority queue \(H = V \setminus S\) (\(V\) set of all vertices, \(S\) vertices currently in the MST) never contains a vertex already in the MST.
Back
Prim's Algorithm Invariants:
The priority queue \(H = V \setminus S\) (\(V\) set of all vertices, \(S\) vertices currently in the MST) never contains a vertex already in the MST.
The priority queue \(H = V \setminus S\) (\(V\) set of all vertices, \(S\) vertices currently in the MST) never contains a vertex already in the MST.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Prim's Algorithm Invariants: <br>The priority queue \(H = V \setminus S\) (\(V\) set of all vertices, \(S\) vertices currently in the MST) {{c1::never contains a vertex already in the MST}}. |
Note 8: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
v|.y5zi[:;
Previous
Note did not exist
New Note
Front
Prim's Algorithm Invariants:
The distances "d[.] = " in the distance array are the values of the vertices in the priority queue (see line decrease_key(H, v, d[v])).
Back
Prim's Algorithm Invariants:
The distances "d[.] = " in the distance array are the values of the vertices in the priority queue (see line decrease_key(H, v, d[v])).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Prim's Algorithm Invariants:<br><br><div>The distances "d[.] = " in the distance array are {{c1::the values of the vertices in the priority queue (see line decrease_key(H, v, d[v]))}}.</div> | |
| Extra | <img src="paste-c6f5e360bdfa85548214127036942fc80a2cde0e.jpg"> |
Note 9: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
IV81kgA3~6
Previous
Note did not exist
New Note
Front
Prim's Algorithm Invariants:
\(\forall v \not \in S, v \neq s\), \(d[v] = \) {{c1:: \(\min \{ w(u, v) \ | \ (u, v) \in E, u \in S \}\)(\(\infty\) if no such edge exists)}}.
\(\forall v \not \in S, v \neq s\), \(d[v] = \) {{c1:: \(\min \{ w(u, v) \ | \ (u, v) \in E, u \in S \}\)(\(\infty\) if no such edge exists)}}.
Back
Prim's Algorithm Invariants:
\(\forall v \not \in S, v \neq s\), \(d[v] = \) {{c1:: \(\min \{ w(u, v) \ | \ (u, v) \in E, u \in S \}\)(\(\infty\) if no such edge exists)}}.
\(\forall v \not \in S, v \neq s\), \(d[v] = \) {{c1:: \(\min \{ w(u, v) \ | \ (u, v) \in E, u \in S \}\)(\(\infty\) if no such edge exists)}}.
The 3rd invariant \[d[v] = \begin{cases} 0, & \text{if } v = s \text{ (the starting vertex)} \\ \min_{(u,v) \in E : u \in S} {w(u,v)}, & \text{if } v \in V \setminus S \text{ and } \exists (u,v) \in E \text{ with } u \in S \\ \infty, & \text{if } v \in V \setminus S \text{ and } \nexists (u,v) \in E \text{ with } u \in S \end{cases}\]ensures that d[v] always reflects the minimum cost to reach vertex v from the current MST.
We always want to add the vertex with the cheapest edge connecting it to the MST, thus this invariant has to hold in order for the algorithm to be correct.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Prim's Algorithm Invariants:<br>\(\forall v \not \in S, v \neq s\), \(d[v] = \) {{c1:: \(\min \{ w(u, v) \ | \ (u, v) \in E, u \in S \}\)(\(\infty\) if no such edge exists)}}. | |
| Extra | <div>The 3rd invariant \[d[v] = \begin{cases} 0, & \text{if } v = s \text{ (the starting vertex)} \\ \min_{(u,v) \in E : u \in S} {w(u,v)}, & \text{if } v \in V \setminus S \text{ and } \exists (u,v) \in E \text{ with } u \in S \\ \infty, & \text{if } v \in V \setminus S \text{ and } \nexists (u,v) \in E \text{ with } u \in S \end{cases}\]ensures that d[v] always reflects the minimum cost to reach vertex v from the current MST.</div><div><br></div> <div>We always want to add the vertex with the cheapest edge connecting it to the MST, thus this invariant has to hold in order for the algorithm to be correct.</div> |
Note 10: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
added
Note Type: Algorithms
GUID:
T?I`@dy&K
Previous
Note did not exist
New Note
Front
Runtime of Kruskal's Algorithm?
Back
Runtime of Kruskal's Algorithm?
\(O(|E| \log |E| + |V| \log |V|)\)
Outer loop: Iterate \(|E|\) times at most:
Inner loop: find and union take \(O(\log |V|)\) per call amortised, thus \(O(|V| \log |V|)\) total.
This requires the Union Find Datastructure
Outer loop: Iterate \(|E|\) times at most:
Inner loop: find and union take \(O(\log |V|)\) per call amortised, thus \(O(|V| \log |V|)\) total.
This requires the Union Find Datastructure
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Name | Kruskal's Algorithm | |
| Runtime | \(O(|E| \log |E| + |V| \log |V|)\)<br><br><b>Outer loop: </b>Iterate \(|E|\) times at most:<br><b>Inner loop: </b>find and union take \(O(\log |V|)\) per call <b>amortised</b>, thus \(O(|V| \log |V|)\) total. | |
| Requirements | Undirected, weighted, connected graph | |
| Approach | <ol><li><b>Initialisation</b>: Start with an empty set \(F = \emptyset\) to represent the MST edges. Initially each vertex is it’s own seperate ZHK. </li><li><b>Iteration</b>: Sort all edges in the graphs by weight in increasing order. For each edge \((u, v)\) in sorted order: <br>If adding \((u, v)\) does not create a cycle (i.e. \(u\) and \(v\) in different ZHKs) <br>Add \((u, v)\) to \(F\). Merge the ZHKs of \(u\) and \(v\)</li><li>Stop: once we have \(n-1\) edges</li></ol><div>The operation of checking if there is no cycle can be done efficiently using the check of \(u\) and \(v\) being in different ZHKs. </div><div>This can be done efficiently using the <b>Union-Find datastructure</b>.</div> | |
| Pseudocode | <img src="paste-4f95b1dbfefb25bbfd8327342ed84d0141d63587.jpg"> | |
| Use Case | Find MST | |
| Extra Info | This requires the Union Find Datastructure |
Note 11: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
ea8^2Vp8-y
Previous
Note did not exist
New Note
Front
Union-Find datastructure methods:
- make(u, v) creates the DS for \(F = \emptyset\)
- same(u,v) test if \(u, v\) in the same component
- union(u,v) merge ZHKs of \(u, v\)
Back
Union-Find datastructure methods:
- make(u, v) creates the DS for \(F = \emptyset\)
- same(u,v) test if \(u, v\) in the same component
- union(u,v) merge ZHKs of \(u, v\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | <b>Union-Find</b> datastructure methods:<br><ul><li>{{c1::<b>make(u, v)</b> creates the DS for \(F = \emptyset\)}}<br></li><li>{{c2::<b>same(u,v) </b>test if \(u, v\) in the same component}}</li><li>{{c3::<b>union(u,v)</b> merge ZHKs of \(u, v\)}}<br></li></ul> |
Note 12: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
oWyDyQ_9bL
Previous
Note did not exist
New Note
Front
After adding \(x\) edges to the Union-Find DS, the repr array contains \(n-x\) components (different values).
Back
After adding \(x\) edges to the Union-Find DS, the repr array contains \(n-x\) components (different values).
Each added edge removes one unconnected component.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | After adding \(x\) edges to the Union-Find DS, the <b>repr</b> array contains {{c1::\(n-x\) components (different values)}}. | |
| Extra | Each added edge <i>removes one unconnected component</i>. |
Note 13: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
hv)-{h!@?x
Previous
Note did not exist
New Note
Front
The amortised runtime of union in the Union-Find DS is \(O(|V| \log |V|)\).
Back
The amortised runtime of union in the Union-Find DS is \(O(|V| \log |V|)\).
union takes \(\Theta(\min \{ |ZHK(u)| , |ZHK(v)| \}\). In the worst case, the minimum is \(|V| / 2\) as both have the same size.
Therefore over all loops, this would take \(O(|V| \log |V|)\) time, as on average we only take \(O(\log |V|)\) time.
The graph stays worst case, this is the average of the calls in the worst case.
Therefore over all loops, this would take \(O(|V| \log |V|)\) time, as on average we only take \(O(\log |V|)\) time.
The graph stays worst case, this is the average of the calls in the worst case.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | The amortised runtime of <b>union</b> in the Union-Find DS is {{c1:: \(O(|V| \log |V|)\)}}. | |
| Extra | union takes \(\Theta(\min \{ |ZHK(u)| , |ZHK(v)| \}\). In the worst case, the minimum is \(|V| / 2\) as both have the same size.<br><br>Therefore over all loops, this would take \(O(|V| \log |V|)\) time, as <i>on average</i> we only take \(O(\log |V|)\) time.<br><i>The graph stays worst case, this is the average of the calls in the worst case.</i> |
Note 14: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
FS|421SN1o
Previous
Note did not exist
New Note
Front
Explain how unions works in the optimised Union-Find:
Back
Explain how unions works in the optimised Union-Find:
Arrays:
We update the reps, then the membership lists and finally the size
- rep, where rep[v] gives the representative of \(v\).
- members, where members[rep[v]] which contains all members of the ZHK of \(v\)
- rank, where rank[rep[v]] contains the size of the ZHK of \(v\).
We always merge the smaller ZHK into the bigger to minimise updates.
We update the reps, then the membership lists and finally the size
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Explain how unions works in the optimised <b>Union-Find:</b> | |
| Back | Arrays:<br><ul><li><b>rep</b>, where <b>rep[v]</b> gives the representative of \(v\).</li><li><b>members</b>, where <b>members[rep[v]] </b>which contains all members of the ZHK of \(v\)<br></li><li><b>rank</b>, where <b>rank[rep[v]]</b> contains the size of the ZHK of \(v\).</li></ul><div>We always merge the smaller ZHK into the bigger to minimise updates.</div><img src="paste-5129796b3ae6c46edebbaae726a47f0c892c2435.jpg"><br>We update the reps, then the membership lists and finally the size |