Anki Deck Changes

Note 1: ETH::A&D

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

modified

Before

Front

A Minimum Spanning Tree is a subgraph of a connected, undirected, weighted Graph with that fullfills:

spanning, it connects all vertices
acylic, it's a tree
minimal, the sum of all edge weights in the Tree is minimal

Back

A Minimum Spanning Tree is a subgraph of a connected, undirected, weighted Graph with that fullfills:

spanning, it connects all vertices
acylic, it's a tree
minimal, the sum of all edge weights in the Tree is minimal

After

Front

A Minimum Spanning Tree is a subgraph of a connected, undirected, weighted graph that fullfills:

spanning, it connects all vertices
acylic, it's a tree
minimal, the sum of all edge weights in the Tree is minimal

Back

A Minimum Spanning Tree is a subgraph of a connected, undirected, weighted graph that fullfills:

spanning, it connects all vertices
acylic, it's a tree
minimal, the sum of all edge weights in the Tree is minimal

Field-by-field Comparison

Field	Before	After
Text	A <b>Minimum Spanning Tree</b> is a subgraph of a {{c1:: connected, undirected, weighted}} Graph ~~with~~ that fullfills:<br><ul><li>{{c2:: spanning, it connects all vertices}}</li><li>{{c3:: acylic, it's a tree}}</li><li>{{c4:: minimal, the sum of all edge weights in the Tree is minimal}}</li></ul>	A <b>Minimum Spanning Tree</b> is a subgraph of a {{c1:: connected, undirected, weighted}} graph that fullfills:<br><ul><li>{{c2:: spanning, it connects all vertices}}</li><li>{{c3:: acylic, it's a tree}}</li><li>{{c4:: minimal, the sum of all edge weights in the Tree is minimal}}</li></ul>

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

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: t:15}v~LmN

modified

Before

Front

Runtime of Bellman-Ford?

Back

Runtime of Bellman-Ford?

\(O(|V| \cdot |E|)\) (uses DP)

We iterate over all edges in the "relaxation" thus the time complexity of that step is \(O(m)\) (the actual check is \(O(1)\)).
As we relax \(n - 1\) (or \(n\) for negative cycle check) times, the total runtime is \(O(n \cdot m)\).

After

Front

Runtime of Bellman-Ford?

Back

Runtime of Bellman-Ford?

\(O(|V| \cdot |E|)\) (uses DP)

We iterate over all edges in the "relaxation" thus the time complexity of that step is \(O(m)\) (the actual check is \(O(1)\)).
As we relax \(n - 1\) (or \(n\) for negative cycle check) times, the total runtime is \(O(n \cdot m)\).

Field-by-field Comparison

Field	Before	After
Approach	<ol> <li><b>Initialize</b>:<br>Set the distance to the source vertex as 0 and to all other vertices as infinity.</li> <li><b>Relax Edges</b>: <br>Repeat for V − 1 iterations (where V is the number of vertices):<br>For each edge, update the distance to its destination vertex if the distance through the edge is smaller than the current distance.</li> <li><b>Check for Negative Cycles</b>: <br>Check all edges to see if a shorter path can still be found. If so, the graph contains a negative- weight cycle.</li> <li><b>End</b>: <br>If no negative-weight cycle is found, the algorithm outputs the shortest paths.</li></ol><img src="paste-95017d19365697a9f94b52394c6bdb999dfc81d1.jpg"><br><br>(quicker to implement the edge-based approach, but there's also a vertex based approach)	<ol> <li><b>Initialize</b>:<br>Set the distance to the source vertex as 0 and to all other vertices as infinity.</li> <li><b>Relax Edges</b>: <br>Repeat for V − 1 iterations (where V is the number of vertices):<br>For each edge, update the distance to its destination vertex if the distance through the edge is smaller than the current distance.</li> <li><b>Check for Negative Cycles</b>: <br>Check all edges to see if a shorter path can still be found. If so, the graph contains a negative-weight cycle.</li> <li><b>End</b>: <br>If no negative-weight cycle is found, the algorithm outputs the shortest paths.</li></ol><img src="paste-95017d19365697a9f94b52394c6bdb999dfc81d1.jpg"><br><br>(quicker to implement the edge-based approach, but there's also a vertex based approach)

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

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: z{8WPibSbC

modified

Before

Front

Runtime of Dijkstra's Algorithm?

Back

Runtime of Dijkstra's Algorithm?

\(O((|V| + |E|) \log |V|)\) (or \(O(|V|^2)\)

The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).

After

Front

Runtime of Dijkstra's Algorithm?

Back

Runtime of Dijkstra's Algorithm?

\(O((|V| + |E|) \log |V|)\) (or \(O(|V|^2)\)

The runtime is calculated from \(O(n + (\#\text{extract-min} + \#\text{decrease-key}) \cdot \log n)\) which gives \(O((n + m) \cdot \log n)\).

Field-by-field Comparison

Field	Before	After
Use Case	Cheapest Path in Weighted graph with non-negative edge costs	Cheapest path in weighted graph with non-negative edge costs.

Tags: ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: q]nbKvbP{^

modified

Before

Front

In a field, you can:

Back

In a field, you can:

add
subtract
multiply
divide by any nonzero element.

You can divide as in a field, the multiplicative monoid is also a group (without \(0\), thus \(0\) cannot be divided by - no inverse).

After

Front

In a field, you can:

Back

In a field, you can:

add
subtract
multiply
divide by any nonzero element.

You can divide, because in a field the multiplicative monoid is also a group (without \(0\), thus \(0\) cannot be divided by - no inverse).

Field-by-field Comparison

Field	Before	After
Back	<ul> <li>add</li> <li>subtract</li> <li>multiply</li> <li><em>divide</em> by any nonzero element.</li> </ul> <p>You can divide as in a field, the multiplicative monoid is also a <em>group</em> (without \(0\), thus \(0\) cannot be divided by - no inverse).</p>	<ul> <li>add</li> <li>subtract</li> <li>multiply</li> <li><em>divide</em> by any nonzero element.</li> </ul> <p>You can divide, because in a field the multiplicative monoid is also a <em>group</em> (without \(0\), thus \(0\) cannot be divided by - no inverse).</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::6._Fields

Note 5: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: FjSbP7PsTQ

modified

Before

Front

\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).

Back

\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).

After

Front

\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).

Back

\(A^\dagger A\) is the projection matrix onto \(C(A^\top)\).

Field-by-field Comparison

Field	Before	After
Text	\(A^\dagger A\) is ~~{{c1::~~the projection matrix onto \(C(A^\top)\)}}.	\(A^\dagger A\) is the projection matrix onto {{c1::\(C(A^\top)\)}}.

Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::4._The_Pseudoinverse,_also_known_as_Moore-Penrose_Inverse::2._Properties

Note 6: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: P+IBIpS^<+

modified

Before

Front

\(A^\dagger A\) is symmetric

Back

\(A^\dagger A\) is symmetric

After

Front

\(A^\dagger A\) is symmetric.

Back

\(A^\dagger A\) is symmetric.

Field-by-field Comparison

Field	Before	After
Text	\(A^\dagger A\) is {{c1:: symmetric :: property }}	\(A^\dagger A\) is {{c1::symmetric::property?}}.

Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::4._The_Pseudoinverse,_also_known_as_Moore-Penrose_Inverse::2._Properties

Note 7: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: PCBMoNL{vn

modified

Before

Front

The nullspace of \(A\) \(N(A) \) is equal to the nullspace of \(N(A^\dagger)\). Proof Included

Back

The nullspace of \(A\) \(N(A) \) is equal to the nullspace of \(N(A^\dagger)\). Proof Included

Intuitively this holds as \(A^\dagger\) projects onto the \(C(A)\).

Thus anything in \(C(A)^\bot = N(A^\top)\) is projected to \(0\). In other words, \(\forall x \in C(A^\top)^\bot = N(A^\top)\) we have \(A^\dagger x = 0\).
We conclude that \(N(A) = C(A^\top)^\bot = N(A^\dagger)\).

After

Front

The nullspace of \(N(A) \) is equal to the nullspace of \(N(A^\dagger)\). Proof Included

Back

The nullspace of \(N(A) \) is equal to the nullspace of \(N(A^\dagger)\). Proof Included

Intuitively this holds as \(A^\dagger\) projects onto the \(C(A)\).

Thus anything in \(C(A)^\bot = N(A^\top)\) is projected to \(0\). In other words, \(\forall x \in C(A^\top)^\bot = N(A^\top)\) we have \(A^\dagger x = 0\).
We conclude that \(N(A) = C(A^\top)^\bot = N(A^\dagger)\).

Field-by-field Comparison

Field	Before	After
Text	The <b>nullspace of </b>\(~~A\) \(~~N(A) \) is equal to {{c1:: the nullspace of \(N(A^\dagger)\)}}. <i>Proof Included</i>	The <b>nullspace of </b>\(N(A) \) is equal to {{c1:: the nullspace of \(N(A^\dagger)\)}}. <i>Proof Included</i>

Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::4._The_Pseudoinverse,_also_known_as_Moore-Penrose_Inverse::2._Properties

Note 8: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID: Q&0Jp*eAqN

modified

Before

Front

How can we use Gauss-Jordan to simplify the determinant calculations?

Back

How can we use Gauss-Jordan to simplify the determinant calculations?

We can use G-J to make any matrix upper triangular (then the determinant is the product of the diagonals).

We are allowed to use:

Row addition / substraction
Exchanging rows (change sign)
Multiply rows (multiply the determinant at the end)

After

Front

How can we use Gauss-Jordan to simplify the determinant calculations?

Back

How can we use Gauss-Jordan to simplify the determinant calculations?

We can use Gauss-Jordan to make any matrix upper triangular (then the determinant is the product of the diagonals).

We are allowed to use:

Row addition / substraction
Exchanging rows (change sign)
Multiply rows (multiply the determinant at the end)

Field-by-field Comparison

Field	Before	After
Back	We can use G-J to make any matrix upper triangular (then the determinant is the product of the diagonals).<br><br>We are allowed to use:<br><ul><li>Row addition / substraction</li><li>Exchanging rows (change sign)</li><li>Multiply rows (multiply the determinant at the end)</li></ul>	We can use Gauss-Jordan to make any matrix upper triangular (then the determinant is the product of the diagonals).<br><br>We are allowed to use:<br><ul><li>Row addition / substraction</li><li>Exchanging rows (change sign)</li><li>Multiply rows (multiply the determinant at the end)</li></ul>

Tags: ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::1._Properties

Note 9: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: hy_&_By5dp

modified

Before

Front

\(\det(A) = \det(A^T)\)
\(\det(I) = 1\)
\(\det(A) = 0\) if linearly dependent columns.
Exchanging two rows flips the sign of the determinant.
Subtracting two rows does not change the \(\det\). (we can use G-J (only row substractions) to simplify calculations…)

Back

\(\det(A) = \det(A^T)\)
\(\det(I) = 1\)
\(\det(A) = 0\) if linearly dependent columns.
Exchanging two rows flips the sign of the determinant.
Subtracting two rows does not change the \(\det\). (we can use G-J (only row substractions) to simplify calculations…)

After

Front

\(\det(A) = \det(A^T)\)
\(\det(I) = 1\)
\(\det(A) = 0\) if linearly dependent columns.
Exchanging two rows flips the sign of the determinant.
Subtracting two rows does not change the \(\det\). (we can use Gauss-Jordan (only row substractions) to simplify calculations…)

Back

\(\det(A) = \det(A^T)\)
\(\det(I) = 1\)
\(\det(A) = 0\) if linearly dependent columns.
Exchanging two rows flips the sign of the determinant.
Subtracting two rows does not change the \(\det\). (we can use Gauss-Jordan (only row substractions) to simplify calculations…)

Field-by-field Comparison

Field	Before	After
Text	<ol> <li>{{c1::\(\det(A) = \det(A^T)\)}}</li><li>~~{{c2::~~\(\det(I) = ~~1\)}}~~</li><li>{{c3::\(\det(A) = 0\) if linearly dependent columns.}}</li><li>{{c4::Exchanging two rows flips the sign of the determinant.}}</li><li>{{c5::Subtracting two rows does not change the \(\det\). (we can use G-J (only row substractions) to simplify calculations…)}}</li></ol>	<ol> <li>{{c1::\(\det(A) = \det(A^T)\)}}</li><li>\(\det(I) = {{c2::1}}\)</li><li>{{c3::\(\det(A) = 0\) if linearly dependent columns.}}</li><li>{{c4::Exchanging two rows flips the sign of the determinant.::Effect of row exchange?}}</li><li>{{c5::Subtracting two rows does not change the \(\det\). (we can use Gauss-Jordan (only row substractions) to simplify calculations…)::Subtraction}}</li></ol>

Tags: ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::1._Properties

Note 10: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: tjub=34aze

modified

Before

Front

\(AA^\dagger\) is symmetric

Back

\(AA^\dagger\) is symmetric

After

Front

\(AA^\dagger\) is symmetric.

Back

\(AA^\dagger\) is symmetric.

Field-by-field Comparison

Field	Before	After
Text	\(AA^\dagger\) is{{c1:: symmetric :: property }}	\(AA^\dagger\) is {{c1::symmetric::property?}}.

Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::4._The_Pseudoinverse,_also_known_as_Moore-Penrose_Inverse::2._Properties

Note 11: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: x|?8Eu84o6

modified

Before

Front

\(AA^\dagger\) is the projection matrix on \(C(A)\).

Back

\(AA^\dagger\) is the projection matrix on \(C(A)\).

After

Front

\(AA^\dagger\) is the projection matrix on \(C(A)\).

Back

\(AA^\dagger\) is the projection matrix on \(C(A)\).

Field-by-field Comparison

Field	Before	After
Text	\(AA^\dagger\) is ~~{{c1::~~ the projection matrix on \(C(A)\)}}.	\(AA^\dagger\) is the projection matrix on {{c1::\(C(A)\)}}.

Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::4._The_Pseudoinverse,_also_known_as_Moore-Penrose_Inverse::2._Properties