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 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

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>{{c3:: spanning, it connects all vertices}}</li><li>{{c3:: acylic, it's a tree}}</li><li>{{c3:: 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 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>

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

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: nzfDv_KLH2

modified

Before

Front

Runtime of Bubble Sort?

Back

Runtime of Bubble Sort?

Best Case: \(O(n^2)\) (\(O(n)\) if checking for swaps and aborting early)
Worst Case: \(O(n^2)\)

We use \(\Theta(n^2)\) comparisons and \(O(n^2)\) switches.

After

Front

Runtime of Bubble Sort?

Back

Runtime of Bubble Sort?

Best Case: \(O(n^2)\) (\(O(n)\) if checking for swaps and aborting early)
Worst Case: \(O(n^2)\)

We use \(\Theta(n^2)\) comparisons and \(O(n^2)\) switches.

Field-by-field Comparison

Field	Before	After
Attributes	In-Place<br>Stable	In-Place<br>Stable<br><div><br></div> <div>An algorithm is in-place if it uses only a constant amount of extra memory (i.e., O(1) additional space), beyond the input itself. It modifies the input data structure directly rather than creating a copy. </div><div><br></div><div>An algorithm is <em>stable</em> if it preserves the relative order of elements with equal keys. If two elements have the same value, they appear in the same order in the output as they did in the input.<br></div>

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::1._Bubble_Sort

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: G2]R~8h{q4

modified

Before

Front

What operations preserve countability?

Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then:

- (i) \(A^n\) (\(n\)-tuples) is countable

- (ii) \(\bigcup_{i\in \mathbb{N A_i\) (countable union) is countable }}

- (iii) \(A^*\) (finite sequences) is countable

Back

What operations preserve countability?

Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then:

- (i) \(A^n\) (\(n\)-tuples) is countable

- (ii) \(\bigcup_{i\in \mathbb{N A_i\) (countable union) is countable }}

- (iii) \(A^*\) (finite sequences) is countable

After

Front

Which operations preserve countability?

Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then:

\(A^n\) (\(n\)-tuples) is countable
{{c2::\(\bigcup_{i\in \mathbb{N} } A_i\) (countable union) is countable}}
\(A^*\) (finite sequences) is countable

Back

Which operations preserve countability?

Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then:

\(A^n\) (\(n\)-tuples) is countable
{{c2::\(\bigcup_{i\in \mathbb{N} } A_i\) (countable union) is countable}}
\(A^*\) (finite sequences) is countable

Field-by-field Comparison

Field	Before	After
Text	What operations preserve countability?<br><br>Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then: <div>~~ - (i)~~ {{c1::\(A^n\) (\(n\)-tuples) is countable }}</~~div><div> - (ii)~~ {{c2::\(\bigcup_{i\in \mathbb{N}} A_i\) (countable union) is countable }}</~~div><div> - (iii)~~ {{c3::\(A^*\) (finite sequences) is countable}}</div>	Which operations preserve countability?<br><br>Let \(A\) and \(A_i\) for \(i \in \mathbb{N}\) be countable sets. Then: <div><ol><li>{{c1::\(A^n\) (\(n\)-tuples) is countable }}</li><li>{{c2::\(\bigcup_{i\in \mathbb{N} } A_i\) (countable union) is countable}}</li><li>{{c3::\(A^*\) (finite sequences) is countable}}</li></ol></div>

Tags: ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::3._Important_Countable_Sets PlsFix::RenderIssues

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: GoF!ZP7[i!

modified

Before

Front

How can we test if a relation is transitive using composition?

Back

How can we test if a relation is transitive using composition?

A relation \(\rho\) is transitive if and only if \(\rho^2 \subseteq \rho\).
(If all two-step paths are already direct edges, the relation is transitive)

After

Front

How can we test whether a relation is transitive using composition?

Back

How can we test whether a relation is transitive using composition?

A relation \(\rho\) is transitive if and only if \(\rho^2 \subseteq \rho\).
(If all two-step paths are already direct edges, the relation is transitive)

Field-by-field Comparison

Field	Before	After
Front	How can we test if a relation is transitive using composition?	How can we test whether a relation is transitive using composition?

Tags: ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::3._Relations::6._Special_Properties_of_Relations

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: e+8V~0_GeE

modified

Before

Front

How do I show the injectivity of a function?

Back

How do I show the injectivity of a function?

Show that if \(a \not= b\) then under that assumption, if \(f(a) = f(b)\) we get a contradiction as this implies \(a = b\).

Example: \(f(x) = 2x\), then if \(a \not = b\) then if \(f(a) = f(b) \ \implies \ 2a = 2b\). This however \( \ \implies a = b\).

After

Front

How does one show the injectivity of a function?

Back

How does one show the injectivity of a function?

Show that if \(a \not= b\), then under that assumption, if \(f(a) = f(b)\) we get a contradiction as this implies \(a = b\).

Example: \(f(x) = 2x\), then if \(a \not = b\) then if \(f(a) = f(b) \ \implies \ 2a = 2b\). This however \( \ \implies a = b\).

Field-by-field Comparison

Field	Before	After
Front	How do I show the injectivity of a function?	How does one show the injectivity of a function?
Back	Show that if \(a \not= b\) then under that assumption, if \(f(a) = f(b)\) we get a contradiction as this implies \(a = b\).<br><br><b>Example: </b>\(f(x) = 2x\), then if \(a \not = b\) then if \(f(a) = f(b) \ \implies \ 2a = 2b\). This however \( \ \implies a = b\).	Show that if \(a \not= b\), then under that assumption, if \(f(a) = f(b)\) we get a contradiction as this implies \(a = b\).<br><br><b>Example: </b>\(f(x) = 2x\), then if \(a \not = b\) then if \(f(a) = f(b) \ \implies \ 2a = 2b\). This however \( \ \implies a = b\).

Tags: ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::6._Functions