Anki Deck Changes

Commit: c94c70ba - we're going to MONACOOOOO

Author: lhorva <lhorva@student.ethz.ch>

Date: 2026-01-20T03:38:05+01:00

Changes: 26 note(s) changed (0 added, 26 modified, 0 deleted)

ℹ️ Cosmetic Changes Hidden: 5 note(s) had formatting-only changes and are not shown below • 1 whitespace updates • 3 HTML formatting changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: B#Jj9:E=8j
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees
Cut and Paste Proof of Cut-Property:

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees
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\). 

  1. Assume \(e \not \in T\) for contradiction.
  2. 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’\).)
  3. We now construct \(T’= (T \cup {e}) \setminus {e’}\) which breaks the cycle but keeps the MST property.
  4. Since \(w(e) < w(e’)\), \(w(T’) < w(T)\) and thus \(T\) is not an MST.

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees
Cut and Paste Proof of Cut-Property:

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees
Cut and Paste Proof of Cut-Property:
Let \((S, V \setminus 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\). 

  1. Assume \(e \not \in T\) for contradiction.
  2. 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’\).)
  3. We now construct \(T’= (T \cup {e}) \setminus {e’}\) which breaks the cycle but keeps the MST property.
  4. Since \(w(e) < w(e’)\), \(w(T’) < w(T)\) and thus \(T\) is not an MST.
Field-by-field Comparison
Field Before After
Back <div>Let \((S, V - S)\)&nbsp;be any cut of a graph \(G\).</div><div><br></div><div>Let&nbsp;\(e = (u,v)\)&nbsp;be the minimal edge crossing this cut.&nbsp;</div><div>We want to show that&nbsp;\(e \in T\).&nbsp;</div><div><br></div><div><ol><li>Assume&nbsp;\(e \not \in T\)&nbsp;for contradiction.</li><li>Since&nbsp;\(T\)&nbsp;is a spanning tree, \(T \cup {u}\)&nbsp;contains a cycle, crossing the cut at least twice (once via&nbsp;\(e\)&nbsp;and once via another edge&nbsp;\(e’\).)</li><li>We now construct&nbsp;\(T’= (T \cup {e}) \setminus {e’}\)&nbsp;which breaks the cycle but keeps the MST property.</li><li>Since&nbsp;\(w(e) &lt; w(e’)\),&nbsp;\(w(T’) &lt; w(T)\)&nbsp;and thus&nbsp;\(T\)&nbsp;is not an MST.</li></ol></div> <div>Let \((S, V \setminus S)\)&nbsp;be any cut of a graph \(G\).</div><div><br></div><div>Let&nbsp;\(e = (u,v)\)&nbsp;be the minimal edge crossing this cut.&nbsp;</div><div>We want to show that&nbsp;\(e \in T\).&nbsp;</div><div><br></div><div><ol><li>Assume&nbsp;\(e \not \in T\)&nbsp;for contradiction.</li><li>Since&nbsp;\(T\)&nbsp;is a spanning tree, \(T \cup {u}\)&nbsp;contains a cycle, crossing the cut at least twice (once via&nbsp;\(e\)&nbsp;and once via another edge&nbsp;\(e’\).)</li><li>We now construct&nbsp;\(T’= (T \cup {e}) \setminus {e’}\)&nbsp;which breaks the cycle but keeps the MST property.</li><li>Since&nbsp;\(w(e) &lt; w(e’)\),&nbsp;\(w(T’) &lt; w(T)\)&nbsp;and thus&nbsp;\(T\)&nbsp;is not an MST.</li></ol></div>
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: M11/nZaHIu
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary
Search   Insertion   Deletion
Non-sorted array   \(O(n)\) \(O(1)\) \(O(n)\)
Sorted array \(O(\log n)\)  \(O(n)\) \(O(n)\)
Doubly linked list   \(O(n)\) \(O(1)\) \(O(n)\)

Back

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary
Search   Insertion   Deletion
Non-sorted array   \(O(n)\) \(O(1)\) \(O(n)\)
Sorted array \(O(\log n)\)  \(O(n)\) \(O(n)\)
Doubly linked list   \(O(n)\) \(O(1)\) \(O(n)\)

After

Front

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary
Search   Insertion   Deletion
Non-sorted array   \(O(n)\) \(O(1)\) \(O(n)\)
Sorted array \(O(\log n)\)  \(O(n)\) \(O(n)\)
Doubly linked list   \(O(n)\) \(O(1)\) \(O(1)\)

Back

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary
Search   Insertion   Deletion
Non-sorted array   \(O(n)\) \(O(1)\) \(O(n)\)
Sorted array \(O(\log n)\)  \(O(n)\) \(O(n)\)
Doubly linked list   \(O(n)\) \(O(1)\) \(O(1)\)
Field-by-field Comparison
Field Before After
Text <b></b><b></b><b></b><b></b><table> <tbody><tr> <td></td> <td><b>Search&nbsp;&nbsp;</b></td> <td><b>Insertion&nbsp;&nbsp;</b></td> <td><b>Deletion</b></td> </tr> <tr> <td>Non-sorted array&nbsp;&nbsp;</td> <td>{{c1::\(O(n)\)}}</td> <td>{{c2::\(O(1)\)}}</td> <td>{{c3::\(O(n)\)}}</td> </tr> <tr> <td>Sorted array</td> <td>{{c4::\(O(\log n)\)}}&nbsp;</td> <td>{{c5::\(O(n)\)}}</td> <td>{{c6::\(O(n)\)}}</td> </tr> <tr> <td>Doubly linked list&nbsp;&nbsp;</td> <td>{{c7::\(O(n)\)}}</td> <td>{{c8::\(O(1)\)}}</td> <td>{{c9::\(O(n)\)}}</td> </tr> </tbody></table> <b></b><b></b><b></b><b></b><table> <tbody><tr> <td></td> <td><b>Search&nbsp;&nbsp;</b></td> <td><b>Insertion&nbsp;&nbsp;</b></td> <td><b>Deletion</b></td> </tr> <tr> <td>Non-sorted array&nbsp;&nbsp;</td> <td>{{c1::\(O(n)\)}}</td> <td>{{c2::\(O(1)\)}}</td> <td>{{c3::\(O(n)\)}}</td> </tr> <tr> <td>Sorted array</td> <td>{{c4::\(O(\log n)\)}}&nbsp;</td> <td>{{c5::\(O(n)\)}}</td> <td>{{c6::\(O(n)\)}}</td> </tr> <tr> <td>Doubly linked list&nbsp;&nbsp;</td> <td>{{c7::\(O(n)\)}}</td> <td>{{c8::\(O(1)\)}}</td> <td>{{c9::\(O(1)\)}}</td> </tr> </tbody></table>
Tags: ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: T?I`@dy&K
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm
Runtime of Kruskal's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm
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

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm
Runtime of Kruskal's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm
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
Field-by-field Comparison
Field Before After
Requirements Undirected, weighted, connected graph Undirected, weighted and connected graph.
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm

Note 4: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: dl`?#
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm
Runtime of Boruvka's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm
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|)\):
  1. Run DFS to find the connected components: \(O(|V| + |E|)\)
  2. Find the cheapest one \(O(|E|)\)
We iterate a total of \(\log_2 |V|\) times as each iteration halves the number of connected components.

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm
Runtime of Boruvka's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm
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|)\):
  1. Run DFS to find the connected components: \(O(|V| + |E|)\)
  2. Find the cheapest one \(O(|E|)\)
We iterate a total of \(\log_2 |V|\) times as each iteration halves the number of connected components.

Field-by-field Comparison
Field Before After
Requirements undirected, connected, weighted Graph. Undirected, connected and weighted graph.
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm

Note 5: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: m`oj
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Runtime of Prim's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Runtime of Prim's Algorithm?
\(O((|V| + |E|) \log |V|)\) (Adjacency List, otherwise \(\Theta(|V|^2)\) like Dijkstra's)

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Runtime of Prim's Algorithm?

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
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
Requirements undirected, connected, weighted Graph Undirected, connected and weighted graph.
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm

Note 6: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: wD<:EQZU&2
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.
Dijkstra's find the shortest distance to each vertex, thus it tracks the total. distance

Prim's needs to build the MST. As in the loop we add vertex \(v\) to the MST, we now want to know the new least distance to the MST for each node.

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm
Prim's Algorithm is similar to Dijkstra's with the difference that {{c1:: \(d[v] = \min \{d[v], w(v*, v)\}\) instead of \(d[v^*] + w(v^*, v)\) }}.
Dijkstra's find the shortest distance to each vertex, thus it tracks the total distance.

Prim's needs to build the MST. Since we add vertex \(v\) to the MST in the loop, we now want to know the new least distance to the MST for each node.
Field-by-field Comparison
Field Before After
Extra Dijkstra's find the shortest distance to each vertex, thus it tracks the total. distance<br><br>Prim's needs to build the MST. As in the loop we add vertex&nbsp;\(v\)&nbsp;to the MST, we now want to know the new least distance to the MST for each node. Dijkstra's find the shortest distance to each vertex, thus it tracks the total distance.<br><br>Prim's needs to build the MST. Since we add vertex&nbsp;\(v\)&nbsp;to the MST in the loop, we now want to know the new least distance to the MST for each node.
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm

Note 7: ETH::DiskMat

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

Before

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
For a formula \(F\), a variable \(x\) and a term \(t\), \(F[x/t]\) denotes the formula obtained from \(F\) by substituting every free occurrence of \(x\) by \(t\).

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
For a formula \(F\), a variable \(x\) and a term \(t\), \(F[x/t]\) denotes the formula obtained from \(F\) by substituting every free occurrence of \(x\) by \(t\).

After

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
For a formula \(F\), a variable \(x\) and a term \(t\), \(F[x/t]\) denotes the formula obtained from \(F\) by substituting every free occurrence of \(x\) by \(t\).

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
For a formula \(F\), a variable \(x\) and a term \(t\), \(F[x/t]\) denotes the formula obtained from \(F\) by substituting every free occurrence of \(x\) by \(t\).
Field-by-field Comparison
Field Before After
Text For a formula&nbsp;\(F\), {{c1::a variable&nbsp;\(x\)&nbsp;and a term&nbsp;\(t\), \(F[x/t]\)}} denotes {{c2::the formula obtained from&nbsp;\(F\)&nbsp;by substituting every free occurrence of&nbsp;\(x\)&nbsp;by&nbsp;\(t\)}}. For a formula&nbsp;\(F\), a variable&nbsp;\(x\)&nbsp;and a term&nbsp;\(t\),&nbsp;{{c1::\(F[x/t]\)}} denotes {{c2::the formula obtained from&nbsp;\(F\)&nbsp;by substituting every free occurrence of&nbsp;\(x\)&nbsp;by&nbsp;\(t\)}}.
Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution

Note 8: ETH::DiskMat

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

Before

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics
An interpretation or structure in predicate logic is a tuple \(\mathcal{A} = (U, \phi, \varphi, \xi)\) where:
- \(U\) is a non-empty universe
- \(\phi\) (phi) assigns function symbols to functions \(U^k \rightarrow U\)
- {{c3::\(\psi\) (psi) assigns predicate symbols to functions \(U^k \rightarrow \{0,1\}\)}}
- \(\xi\) (xi) assigns variable symbols to values in \(U\)

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics
An interpretation or structure in predicate logic is a tuple \(\mathcal{A} = (U, \phi, \varphi, \xi)\) where:
- \(U\) is a non-empty universe
- \(\phi\) (phi) assigns function symbols to functions \(U^k \rightarrow U\)
- {{c3::\(\psi\) (psi) assigns predicate symbols to functions \(U^k \rightarrow \{0,1\}\)}}
- \(\xi\) (xi) assigns variable symbols to values in \(U\)

After

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics
An interpretation or structure in predicate logic is a tuple \(\mathcal{A} = (U, \phi, \psi, \xi)\) where:
  1. \(U\) is a non-empty universe
  2. \(\phi\) (phi) assigns function symbols to functions \(U^k \rightarrow U\)
  3. {{c3::\(\psi\) (psi) assigns predicate symbols to functions \(U^k \rightarrow \{0,1\}\)}}
  4. \(\xi\) (xi) assigns variable symbols to values in \(U\)

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics
An interpretation or structure in predicate logic is a tuple \(\mathcal{A} = (U, \phi, \psi, \xi)\) where:
  1. \(U\) is a non-empty universe
  2. \(\phi\) (phi) assigns function symbols to functions \(U^k \rightarrow U\)
  3. {{c3::\(\psi\) (psi) assigns predicate symbols to functions \(U^k \rightarrow \{0,1\}\)}}
  4. \(\xi\) (xi) assigns variable symbols to values in \(U\)
Field-by-field Comparison
Field Before After
Text An <i>interpretation</i> or <i>structure</i> in predicate logic is a tuple&nbsp;\(\mathcal{A} = (U, \phi, \varphi, \xi)\)&nbsp;where:<br>- {{c1::\(U\)&nbsp;is a <b>non-empty</b> universe}}<br>- {{c2::\(\phi\)&nbsp;(phi)&nbsp;assigns function symbols to functions&nbsp;\(U^k \rightarrow U\)}}<br>- {{c3::\(\psi\)&nbsp;(psi)&nbsp;assigns predicate symbols to functions&nbsp;\(U^k \rightarrow \{0,1\}\)}}<br>- {{c4::\(\xi\)&nbsp;(xi) assigns variable symbols to values in&nbsp;\(U\)}} An <i>interpretation</i> or <i>structure</i> in predicate logic is a tuple&nbsp;\(\mathcal{A} = (U, \phi, \psi, \xi)\)&nbsp;where:<br><ol><li>{{c1::\(U\)&nbsp;is a <b>non-empty</b> universe}}</li><li>{{c2::\(\phi\)&nbsp;(phi)&nbsp;assigns function symbols to functions&nbsp;\(U^k \rightarrow U\)}}</li><li>{{c3::\(\psi\)&nbsp;(psi)&nbsp;assigns predicate symbols to functions&nbsp;\(U^k \rightarrow \{0,1\}\)}}</li><li>{{c4::\(\xi\)&nbsp;(xi) assigns variable symbols to values in&nbsp;\(U\)}}</li></ol>
Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics

Note 9: ETH::DiskMat

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

Before

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax
A term is defined inductively:
  • A variable is a term
  • if \((t_1, \dots, t_k)\) are terms, then {{c3::\(f^{(k)}(t_1, \dots, t_k)\) is a term}}.

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax
A term is defined inductively:
  • A variable is a term
  • if \((t_1, \dots, t_k)\) are terms, then {{c3::\(f^{(k)}(t_1, \dots, t_k)\) is a term}}.
For \(k = 0\) one writes no parenthesis (constants).

After

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax
A term is defined inductively:
  • A variable is a term
  • if \((t_1, \dots, t_k)\) are terms, then {{c3::\(f^{(k)}(t_1, \dots, t_k)\) is a term}}.

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax
A term is defined inductively:
  • A variable is a term
  • if \((t_1, \dots, t_k)\) are terms, then {{c3::\(f^{(k)}(t_1, \dots, t_k)\) is a term}}.
For \(k = 0\) one writes no parentheses (constants).
Field-by-field Comparison
Field Before After
Extra For&nbsp;\(k = 0\)&nbsp;one writes no parenthesis (constants). For&nbsp;\(k = 0\)&nbsp;one writes no parentheses (constants).
Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax

Note 10: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: b75u`Hl{|J
modified

Before

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
If a variable \(x\) occurs in a (sub-)formula of the form \(\forall x G\) or \(\exists x G\) then it is  bound, otherwise it is free.

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
If a variable \(x\) occurs in a (sub-)formula of the form \(\forall x G\) or \(\exists x G\) then it is  bound, otherwise it is free.

After

Front

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
If a variable \(x\) occurs in a (sub-)formula of the form \(\forall x G\) or \(\exists x G\) then it is bound, otherwise it is free.

Back

ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution
If a variable \(x\) occurs in a (sub-)formula of the form \(\forall x G\) or \(\exists x G\) then it is bound, otherwise it is free.
Field-by-field Comparison
Field Before After
Text If a variable&nbsp;\(x\)&nbsp;occurs {{c1::in a (sub-)formula of the form&nbsp;\(\forall x G\)&nbsp;or \(\exists x G\)}}&nbsp;then it is {{c2::&nbsp;<b>bound</b>, otherwise it is <b>free</b>}}. If a variable&nbsp;\(x\)&nbsp;occurs {{c1::in a (sub-)formula of the form&nbsp;\(\forall x G\)&nbsp;or \(\exists x G\)}}&nbsp;then it is {{c2::<b>bound</b>, otherwise it is <b>free</b>}}.
Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::2._Free_Variables_and_Variable_Substitution

Note 11: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: f1r3O.O4h,
modified

Before

Front

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field::1._Factorization_and_Irreducible_Polynomials

What is the GCD in a polynomial Field

Back

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field::1._Factorization_and_Irreducible_Polynomials

What is the GCD in a polynomial Field

The monic polynomial \(g(x)\) of largest degree such that \(g(x) \ | \ a(x)\) and \(g(x) \ | \ b(x)\) is called the greatest common divisor of \(a(x)\) and \(b(x)\), denoted \(\gcd(a(x), b(x))\).

After

Front

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field::1._Factorization_and_Irreducible_Polynomials

What is the GCD in a polynomial field?

Back

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field::1._Factorization_and_Irreducible_Polynomials

What is the GCD in a polynomial field?

The monic polynomial \(g(x)\) of largest degree such that \(g(x) \ | \ a(x)\) and \(g(x) \ | \ b(x)\) is called the greatest common divisor of \(a(x)\) and \(b(x)\), denoted \(\gcd(a(x), b(x))\).

Field-by-field Comparison
Field Before After
Front <p>What is the GCD in a polynomial Field</p> <p>What is the GCD in a polynomial field?</p>
Tags: ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field::1._Factorization_and_Irreducible_Polynomials

Note 12: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: nNq&rzbEm:
modified

Before

Front

ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition
Every statement \(s \in \mathcal{S}\) is either true or false as assigned by the {{c2:: truth function \(\tau : \mathcal{S} \rightarrow \{0,1\}\) which assigns to each statement it's truth value}}.

Back

ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition
Every statement \(s \in \mathcal{S}\) is either true or false as assigned by the {{c2:: truth function \(\tau : \mathcal{S} \rightarrow \{0,1\}\) which assigns to each statement it's truth value}}.

After

Front

ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition
Every statement \(s \in \mathcal{S}\) is either true or false as assigned by the {{c2:: truth function \(\tau : \mathcal{S} \rightarrow \{0,1\}\) which assigns to each statement it's truth value}}.

Back

ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition
Every statement \(s \in \mathcal{S}\) is either true or false as assigned by the {{c2:: truth function \(\tau : \mathcal{S} \rightarrow \{0,1\}\) which assigns to each statement it's truth value}}.
Field-by-field Comparison
Field Before After
Text Every statement&nbsp;\(s \in \mathcal{S}\)&nbsp;is {{c1:: either true or false}} as assigned by the {{c2:: truth function&nbsp;\(\tau : \mathcal{S} \rightarrow \{0,1\}\)&nbsp;which assigns to each statement it's&nbsp;<b>truth value</b>}}. Every statement&nbsp;\(s \in \mathcal{S}\)&nbsp;is either {{c1::true or false}} as assigned by the {{c2:: truth function&nbsp;\(\tau : \mathcal{S} \rightarrow \{0,1\}\)&nbsp;which assigns to each statement it's&nbsp;<b>truth value</b>}}.
Tags: ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition

Note 13: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: AN(F>bO#!5
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
The matrix \(A^k\) has EW-EW pair \(\lambda^k\) and \(v\) if \(A\) has \(\lambda, v\) as an EW-EV pair.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
The matrix \(A^k\) has EW-EW pair \(\lambda^k\) and \(v\) if \(A\) has \(\lambda, v\) as an EW-EV pair.
Intuitively, \(A\) on \(v\) scales it by \(\lambda\). Then scaling that already scaled \(\lambda v\) by \(A\) again gives us \(\lambda^2 v\), etc...

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
The matrix \(A^k\) has EW-EV pair \(\lambda^k\) and \(v\) if \(A\) has \(\lambda, v\) as an EW-EV pair.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
The matrix \(A^k\) has EW-EV pair \(\lambda^k\) and \(v\) if \(A\) has \(\lambda, v\) as an EW-EV pair.
Intuitively, \(A\) on \(v\) scales it by \(\lambda\). Then scaling that already scaled \(\lambda v\) by \(A\) again gives us \(\lambda^2 v\), etc...
Field-by-field Comparison
Field Before After
Text The matrix&nbsp;\(A^k\)&nbsp;has EW-EW pair {{c1::\(\lambda^k\)&nbsp;and&nbsp;\(v\)}} if&nbsp;\(A\)&nbsp;has&nbsp;\(\lambda, v\)&nbsp;as an EW-EV pair. The matrix&nbsp;\(A^k\)&nbsp;has EW-EV pair {{c1::\(\lambda^k\)&nbsp;and&nbsp;\(v\)}} if&nbsp;\(A\)&nbsp;has&nbsp;\(\lambda, v\)&nbsp;as an EW-EV pair.
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties

Note 14: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: HVb7^Pa98H
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All eigenvalues are exactly the roots of the polynomial \(\det(A - \lambda I)\) .

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All eigenvalues are exactly the roots of the polynomial \(\det(A - \lambda I)\) .

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All eigenvalues are exactly the roots of the polynomial \(\det(A - \lambda I)\).

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All eigenvalues are exactly the roots of the polynomial \(\det(A - \lambda I)\).
Field-by-field Comparison
Field Before After
Text <div>All eigenvalues are {{c1::exactly the roots of the polynomial \(\det(A - \lambda I)\)&nbsp;:: in terms of polynomial }}.</div> <div>All eigenvalues are {{c1::exactly the roots of the polynomial \(\det(A - \lambda I)\)::in terms of polynomial}}.</div>
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors

Note 15: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: I`-{jhD?WK
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
If \(Av = \lambda v\) and \(\lambda\) and \(v\) are an EW, EV pair we know \(v \neq 0\) .

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
If \(Av = \lambda v\) and \(\lambda\) and \(v\) are an EW, EV pair we know \(v \neq 0\) .

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
If \(Av = \lambda v\) and \(\lambda\) and \(v\) are an EW-EV pair we know \(v \neq 0\) .

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
If \(Av = \lambda v\) and \(\lambda\) and \(v\) are an EW-EV pair we know \(v \neq 0\) .
Field-by-field Comparison
Field Before After
Text If&nbsp;\(Av = \lambda v\)&nbsp;and&nbsp;\(\lambda\)&nbsp;and&nbsp;\(v\)&nbsp;are an EW, EV pair we know {{c1::\(v \neq 0\)&nbsp;:: property of&nbsp;\(v\)}}. If&nbsp;\(Av = \lambda v\)&nbsp;and&nbsp;\(\lambda\)&nbsp;and&nbsp;\(v\)&nbsp;are an EW-EV pair we know {{c1::\(v \neq 0\)&nbsp;::property of&nbsp;\(v\)}}.
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors

Note 16: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: O7M|kGyh}1
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
Let \(A\) with \(n\) distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\)) , then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
Let \(A\) with \(n\) distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\)) , then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.
We also call this the Eigenbasis or a complete set of real EVs, which will come in handy later for Diagonalisation.

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
Let \(A\) with \(n\) distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\)), then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties
Let \(A\) with \(n\) distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\)), then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.
We also call this the Eigenbasis or a complete set of real EVs, which will come in handy later for Diagonalisation.
Field-by-field Comparison
Field Before After
Text <div>Let \(A\) with \(n\)&nbsp;{{c1::distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\)) :: property and in terms of algebraic }}, then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.</div> <div>Let \(A\) with \(n\)&nbsp;{{c1::distinct real eigenvalues (meaning that the zeros of \(\det(A- \lambda I)\) as described in Corollary 8.1.3 are all distinct, algebraic multiplicity \(1\))::property and in terms of algebraic}}, then {{c2::there is a basis of \(\mathbb{R}^n\) made up of EVs of \(A\)}}.</div>
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::3._Properties

Note 17: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: i$=u%lLqUM
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All the eigenvectors for \(\lambda_i\) are the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace .

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All the eigenvectors for \(\lambda_i\) are the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace .

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All the eigenvectors for \(\lambda_i\) are the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
All the eigenvectors for \(\lambda_i\) are the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace.
Field-by-field Comparison
Field Before After
Text <div>All the eigenvectors for \(\lambda_i\) are {{c1::the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace :: subspace}}.</div> <div>All the eigenvectors for \(\lambda_i\) are {{c1::the vectors \(v \neq 0\), \(v \in N(A - \lambda_i I)\), in the nullspace::subspace}}.</div>
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors

Note 18: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: o#.FGP:Yyu
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
An EW can have many EVs associated with it.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
An EW can have many EVs associated with it.

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
An EW can have many EVs associated with it.

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
An EW can have many EVs associated with it.
Field-by-field Comparison
Field Before After
Text An EW can have {{c1::many :: number}} EVs associated with it. An EW can have {{c1::many::quantity}} EVs associated with it.
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors

Note 19: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: oSLQnuRv!X
modified

Before

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
Every matrix \(A \in \mathbb{R}^{n \times n}\) has an eigenvalue (perhaps complex-valued) .

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
Every matrix \(A \in \mathbb{R}^{n \times n}\) has an eigenvalue (perhaps complex-valued) .

After

Front

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
Every matrix \(A \in \mathbb{R}^{n \times n}\) has an eigenvalue (perhaps complex-valued).

Back

ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors
Every matrix \(A \in \mathbb{R}^{n \times n}\) has an eigenvalue (perhaps complex-valued).
Field-by-field Comparison
Field Before After
Text Every matrix \(A \in \mathbb{R}^{n \times n}\) has {{c1::an eigenvalue (perhaps <i>complex</i>-valued) :: due to fundamental theorem of algebra}}. Every matrix \(A \in \mathbb{R}^{n \times n}\) has {{c1::an eigenvalue (perhaps <i>complex</i>-valued)::due to fundamental theorem of algebra}}.
Tags: ETH::1._Semester::LinAlg::8._Eigenvalues_and_Eigenvectors::2._Introduction_to_Eigenvalues_and_Eigenvectors

Note 20: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Cloze
GUID: uamL=`piJf
modified

Before

Front

ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::2._Permutations
The sign of a permutation is multiplicative: \(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\).

Back

ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::2._Permutations
The sign of a permutation is multiplicative: \(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\).

After

Front

ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::2._Permutations
The sign of a permutation is multiplicative:

\(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\).

Back

ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::2._Permutations
The sign of a permutation is multiplicative:

\(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\).
Field-by-field Comparison
Field Before After
Text The sign of a permutation is {{c1::multiplicative}}: \(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\). The sign of a permutation is {{c1::multiplicative::property}}: <br><br>\(\text{sgn}(\sigma \circ \lambda) = {{c1:: \text{sgn}(\sigma) \cdot \text{sgn}(\lambda)}}\).
Tags: ETH::1._Semester::LinAlg::7._The_determinant::2._The_general_case::2._Permutations

Note 21: ETH::LinAlg

Deck: ETH::LinAlg
Note Type: Horvath Classic
GUID: vA(v{*KZt+
modified

Before

Front

ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::3._Orthonormal_Bases_and_Gram_Schmidt::2._QR_Decomposition
In QR decomposition \(R\)  is invertible because:

Back

ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::3._Orthonormal_Bases_and_Gram_Schmidt::2._QR_Decomposition
In QR decomposition \(R\)  is invertible because:
\(N(A) = \{0\}\) since \(A\) has independent columns and thus \(N(R) = \{0\}\):
  • \(Rx = 0\) then \(Ax = QRx = 0\) thus \(Q\cdot 0 = 0\)
  • Thus \(x \in N(A) \implies x = 0\)
Thus \(R \in \mathbb{R}^{n \times n}\) (square) must be invertible.

After

Front

ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::3._Orthonormal_Bases_and_Gram_Schmidt::2._QR_Decomposition
In QR decomposition \(R\)  is invertible because?

Back

ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::3._Orthonormal_Bases_and_Gram_Schmidt::2._QR_Decomposition
In QR decomposition \(R\)  is invertible because?
\(N(A) = \{0\}\) since \(A\) has independent columns and thus \(N(R) = \{0\}\):
  • \(Rx = 0\) then \(Ax = QRx = 0\) thus \(Q\cdot 0 = 0\)
  • Thus \(x \in N(A) \implies x = 0\)
Thus \(R \in \mathbb{R}^{n \times n}\) (square) must be invertible.
Field-by-field Comparison
Field Before After
Front In QR decomposition&nbsp;\(R\)&nbsp; is invertible because: In QR decomposition&nbsp;\(R\)&nbsp; is invertible because?
Tags: ETH::1._Semester::LinAlg::6._Applications_of_orthogonality_and_projections::3._Orthonormal_Bases_and_Gram_Schmidt::2._QR_Decomposition
↑ Top