Runtime of sorting an array containing only \(1, 0\)?
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
A8P;P^G,v4
Previous
Note did not exist
New Note
Front
Back
Runtime of sorting an array containing only \(1, 0\)?
Using bucketsort, we can achieve \(O(n)\). this seems contradictory.
We go through the array once, counting occurences of \(0\) as x. We then add \(x\) zeros in the beginning and fill the rest with 1s.
We go through the array once, counting occurences of \(0\) as x. We then add \(x\) zeros in the beginning and fill the rest with 1s.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Runtime of sorting an array containing only \(1, 0\)? | |
| Back | Using bucketsort, we can achieve \(O(n)\). this seems contradictory.<br>We go through the array once, counting occurences of \(0\) as x. We then add \(x\) zeros in the beginning and fill the rest with 1s. |
Note 2: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
B#Jj9:E=8j
Previous
Note did not exist
New Note
Front
Cut and Paste Proof of Cut-Property:
Back
Cut and Paste Proof of Cut-Property:
Let $(S, V - S)$ be any cut of a graph $G$.
Let $e = (u,v)$ be the minimal edge crossing this cut.
We want to show that $e \in T$.
- Assume \(e \not \in T\) for contradiction.
- Since \(T\) is a spanning tree, \(T \cup {u}\) contains a cycle, crossing the cut at least twice (once via \(e\) and once via another edge \(e’\).)
- We now construct \(T’= (T \cup {e}) \setminus {e’}\) which breaks the cycle but keeps the MST property.
- Since \(w(e) < w(e’)\), \(w(T’) < w(T)\) and thus \(T\) is not an MST.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Cut and Paste Proof of <b>Cut-Property</b>: | |
| Back | <div>Let $(S, V - S)$ be any cut of a graph $G$. </div><div>Let $e = (u,v)$ be the minimal edge crossing this cut. </div><div>We want to show that $e \in T$. </div><div><br></div><div><ol><li>Assume \(e \not \in T\) for contradiction.</li><li>Since \(T\) is a spanning tree, \(T \cup {u}\) contains a cycle, crossing the cut at least twice (once via \(e\) and once via another edge \(e’\).)</li><li>We now construct \(T’= (T \cup {e}) \setminus {e’}\) which breaks the cycle but keeps the MST property.</li><li>Since \(w(e) < w(e’)\), \(w(T’) < w(T)\) and thus \(T\) is not an MST.</li></ol></div> |
Note 3: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
KCjL6r:?jQ
Previous
Note did not exist
New Note
Front
A graph with more than \(n-1\) edges has a cycle if it is undirected.
Back
A graph with more than \(n-1\) edges has a cycle if it is undirected.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | A graph with more than \(n-1\) edges has {{c1::a cycle}} if it is {{c1::undirected}}. |
Note 4: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
NGdgt3D+pd
Previous
Note did not exist
New Note
Front
We can ignore the base of a logarithm only if it's not in the exponent.
Back
We can ignore the base of a logarithm only if it's not in the exponent.
\(e^{\log_2 n} \neq \Theta(e^{\log_3 n})\) as \(e^{\log_2 n - \log_3 n} = e^{\ln n (\frac{1}{\ln(2)} - \frac{1}{\ln(3)})}\) goes to \(\infty\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | We can ignore the base of a logarithm {{c1:: only if it's not in the exponent}}. | |
| Extra | \(e^{\log_2 n} \neq \Theta(e^{\log_3 n})\) as \(e^{\log_2 n - \log_3 n} = e^{\ln n (\frac{1}{\ln(2)} - \frac{1}{\ln(3)})}\) goes to \(\infty\) |
Note 5: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
o3QNr=]FF`
Previous
Note did not exist
New Note
Front
What is contracting an edge?
Back
What is contracting an edge?
We contract \(\{v, w\}\) by:
- replacing \(v\) and \(w\) by a single vertex \(vw\)
- Replacy any edge \(\{v,x\}\) or \(\{w, x\}\) by \(\{vw, x\}\).
- Set the weights to their previous ones, and the minimum if there was more than one.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | What is <b>contracting</b> an edge? | |
| Back | We contract \(\{v, w\}\) by:<br><ol><li>replacing \(v\) and \(w\) by a single vertex \(vw\)</li><li>Replacy any edge \(\{v,x\}\) or \(\{w, x\}\) by \(\{vw, x\}\).</li><li>Set the weights to their previous ones, and the minimum if there was more than one.</li></ol> |