Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: H0^#YREe-o

modified

Before

Front

A 2-3 Tree is an external search-tree.

Back

A 2-3 Tree is an external search-tree.

This means that the values are stored in the leaves only. The nodes are for "navigation".

After

Front

A 2-3 Tree is an external search-tree.

Back

A 2-3 Tree is an external search-tree.

This means that the values are stored in the leaves only. The nodes are for "navigation".

Field-by-field Comparison

Field	Before	After
Text	A <b>2-3 Tree</b> is an {{c1:: external}} search-tree.	A <b>2-3 Tree</b> is {{c1::an external}} search-tree.

Tags: ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: Pf|C9|^n[w

modified

Before

Front

In a singly and doubly linked list, the operation:

Insert is $\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$.
Get is $\Theta(i)$ very slow as we need to traverse the entire list up to i
insertAfter is $O(1)$ if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer.}
DLL: $O(1)$ we know the address of the previous element and then just edit it's pointer.

Back

In a singly and doubly linked list, the operation:

Insert is $\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$.
Get is $\Theta(i)$ very slow as we need to traverse the entire list up to i
insertAfter is $O(1)$ if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer.}
DLL: $O(1)$ we know the address of the previous element and then just edit it's pointer.

After

Front

In a singly and doubly linked list, the operation:

Insert is $\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$.
Get is $\Theta(i)$ very slow as we need to traverse the entire list up to i
insertAfter is $O(1)$ if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer}.}
DLL: $O(1)$ we know the address of the previous element and then just edit it's pointer.

Back

In a singly and doubly linked list, the operation:

Insert is $\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$.
Get is $\Theta(i)$ very slow as we need to traverse the entire list up to i
insertAfter is $O(1)$ if we get the memory address of the element to insert after.
delete is:
SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer}.}
DLL: $O(1)$ we know the address of the previous element and then just edit it's pointer.

Field-by-field Comparison

Field	Before	After
Text	In a <b>singly</b> and <b>doubly linked list</b>, the operation:<br><ul><li><b>Insert</b> is {{c1::$\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$. }}<br></li><li><b>Get</b> is {{c2::$\Theta(i)$ very slow as we need to traverse the entire list up to <b>i</b>}}<br></li><li><b>insertAfter</b> is {{c3:: $O(1)$ if we get the memory address of the element to insert after.}}<br></li><li><b>delete</b> is:<br>      SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer.}<br>      DLL: {{c5:: $O(1)$ we know the address of the previous element and then just edit it's pointer.}}</li></ul>	In a <b>singly</b> and <b>doubly linked list</b>, the operation:<br><ul><li><b>Insert</b> is {{c1::$\Theta(1)$ as we know the memory address of the final element in the list and just have to set the null pointer to the new keys address. Without this pointer it's $\Theta(l)$. }}<br></li><li><b>Get</b> is {{c2::$\Theta(i)$ very slow as we need to traverse the entire list up to <b>i</b>}}<br></li><li><b>insertAfter</b> is {{c3:: $O(1)$ if we get the memory address of the element to insert after.}}<br></li><li><b>delete</b> is:<br>      SLL: {{c4::$\Theta(l)$ as we need to find the previous element and change it's pointer}.}<br>      DLL: {{c5:: $O(1)$ we know the address of the previous element and then just edit it's pointer.}}</li></ul>

Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: M035/^ZEJ$

modified

Before

Front

What is the number of subgroups of $\mathbb{Z}_n$?

Back

What is the number of subgroups of $\mathbb{Z}_n$?

it is the number of divisors of $n$
if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$

After

Front

What is the number of subgroups of $\mathbb{Z}_n$?

Back

What is the number of subgroups of $\mathbb{Z}_n$?

it is the number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange).
if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$

Field-by-field Comparison

Field	Before	After
Back	it is the number of divisors of $n$<br>if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$	it is the number of divisors of $n$ (as the order of each subgroup divides the group order (which is n here) by Lagrange). <br>if $n$ is written $n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}$ then it is $\prod_{i=1}^k (e_i+1)$

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: kC`G6X,/]b

added

New Note

Front

$\gcd(a, 0) = $ $|a|$

Back

$\gcd(a, 0) = $ $|a|$

This is why $0$ not in $Z_m^* $ and $F[x]^*_{m(x)}$

Field-by-field Comparison

Field	Before	After
Text		$\gcd(a, 0) = $ {{c1::$\|a\|$}}
Extra		This is why $0$ not in $Z_m^* $ and $F[x]^*_{m(x)}$

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: lq:b}[Y<9t

modified

Before

Front

Lagrange Interpolation for polynomials in a Field

Back

Lagrange Interpolation for polynomials in a Field

Let $\beta_i = a(\alpha_i)$ for $i = 1, \dots, d+1$.

Then $a(x)$ is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial $u_i(x)$ is: \[u_i(x) = \frac{{{c2::(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}}}{{{c3::(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}}}\]

Note that for $u_i(x)$ to be well-defined, all constant terms $\alpha_i - \alpha_j$ in the denominator must be invertible. This is guaranteed in a field since $a_i - a_j \neq 0$ for $i \neq j$ (as they are all distinct).

After

Front

Lagrange Interpolation for polynomials in a Field

Back

Lagrange Interpolation for polynomials in a Field

Let $\beta_i = a(\alpha_i)$ for $i = 1, \dots, d+1$ where Then $\alpha_i$ distinct for all $i.$

$a(x)$ is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial $u_i(x)$ is: \[u_i(x) = \frac{(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}{(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}\]

Note that for $u_i(x)$ to be well-defined, all constant terms $\alpha_i - \alpha_j$ in the denominator must be invertible. This is guaranteed in a field since $\alpha_i - \alpha_j \neq 0$ for $i \neq j$ (as they are all distinct).

Field-by-field Comparison

Field	Before	After
Back	<p>Let $\beta_i = a(\alpha_i)$ for $i = 1, \dots, d+1$.</p> <p>~~Then~~ $a(x)$ is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial $u_i(x)$ is: \[u_i(x) = \frac{~~{{c2::~~(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}~~}}{{{c3::~~(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}}}\]</p> <p>Note that for $u_i(x)$ to be well-defined, all constant terms $\alpha_i - \alpha_j$ in the denominator must be invertible. This is guaranteed in a field since $a_i - a_j \neq 0$ for $i \neq j$ (as they are all distinct).</p>	<p>Let $\beta_i = a(\alpha_i)$ for $i = 1, \dots, d+1$ where Then $\alpha_i$ distinct for all $i.$</p><p><br>$a(x)$ is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial $u_i(x)$ is: \[u_i(x) = \frac{(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}{(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}\]</p> <p>Note that for $u_i(x)$ to be well-defined, all constant terms $\alpha_i - \alpha_j$ in the denominator must be invertible. This is guaranteed in a field since $\alpha_i - \alpha_j \neq 0$ for $i \neq j$ (as they are all distinct).</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::7._Polynomials_as_Functions::3._Polynomial_Interpolation

Note 6: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: oPaK;$.R2B

modified

Before

Front

An irreducible polynomial has no roots in the field. It has to have degree $\geq 2$.

Back

An irreducible polynomial has no roots in the field. It has to have degree $\geq 2$.

Proof: If it had a root $\alpha$, then $(x - \alpha)$ would divide it by Lemma 5.29, contradicting irreducibility.

After

Front

An irreducible polynomial has no roots in the field. It has to have degree $\geq 2$.

Back

An irreducible polynomial has no roots in the field. It has to have degree $\geq 2$.

Note that this is not a sufficient condition (no roots does not imply irreducible)!

Proof: If it had a root $\alpha$, then $(x - \alpha)$ would divide it by Lemma 5.29, contradicting irreducibility.

Field-by-field Comparison

Field	Before	After
Extra	<strong>Proof</strong>: If it had a root $\alpha$, then $(x - \alpha)$ would divide it by Lemma 5.29, contradicting irreducibility.	<strong>Note that this is not a sufficient condition (no roots does not imply irreducible)!<br><br>Proof</strong>: If it had a root $\alpha$, then $(x - \alpha)$ would divide it by Lemma 5.29, contradicting irreducibility.

Tags: ETH::1._Semester::DiskMat::5._Algebra::7._Polynomials_as_Functions::2._Roots

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: r3)589~fN6

modified

Before

Front

What is the cardinality of $F[x]_{m(x)}$?

Back

What is the cardinality of $F[x]_{m(x)}$?

Lemma 5.34: Let $F$ be a finite field with $q$ elements and let $m(x)$ be a polynomial of degree $d$ over $F$. Then: \[|F[x]_{m(x)}| = q^d\]

Explanation: Each polynomial has $d$ coefficients, and each coefficient can be any of $q$ elements from $F$.

After

Front

What is the cardinality of $F[x]_{m(x)}$?

Back

What is the cardinality of $F[x]_{m(x)}$?

Lemma 5.34: Let $F$ be a finite field with $q$ elements and let $m(x)$ be a polynomial of degree $d$ over $F$. Then: \[|F[x]_{m(x)}| = q^d\]

Explanation: Each polynomial has $d$ coefficients (from $0, \dots, d - 1$), and each coefficient can be any of $q$ elements from $F$.

Field-by-field Comparison

Field	Before	After
Back	<p><strong>Lemma 5.34</strong>: Let $F$ be a finite field with $q$ elements and let $m(x)$ be a polynomial of degree $d$ over $F$. Then: \[\|F[x]_{m(x)}\| = q^d\]</p> <p><strong>Explanation</strong>: Each polynomial has $d$ coefficients, and each coefficient can be any of $q$ elements from $F$.</p>	<p><strong>Lemma 5.34</strong>: Let $F$ be a finite field with $q$ elements and let $m(x)$ be a polynomial of degree $d$ over $F$. Then: \[\|F[x]_{m(x)}\| = q^d\]</p> <p><strong>Explanation</strong>: Each polynomial has $d$ coefficients (from $0, \dots, d - 1$), and each coefficient can be any of $q$ elements from $F$.</p>

Tags: ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Note 8: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: tXnVRUZ1r.

modified

Before

Front

To show that a newly defined operator can be used to express any formula, we show that:

Back

To show that a newly defined operator can be used to express any formula, we show that:

$\lnot F$, $F \lor G$ and $F \land G$ can be rewritten only in terms of it.

For example NOT, AND, OR can be expressed in NAND form, thus we can rewritten in CNF (or DNF) then NANDs (by simply replacing).

After

Front

To show that a newly defined operator can be used to express any formula, we show that:

Back

To show that a newly defined operator can be used to express any formula, we show that:

$\lnot F$, $F \lor G$ and $F \land G$ can be rewritten only in terms of it.

For example NOT, AND, OR can be expressed in NAND form, thus we can rewritten in CNF (or DNF) then NANDs (by simply replacing). As we can write every formula in CNF (or DNF) this prooves it.

Field-by-field Comparison

Field	Before	After
Back	$\lnot F$, $F \lor G$ and $F \land G$ can be rewritten <b>only</b> in terms of it.<br><br>For example NOT, AND, OR can be expressed in NAND form, thus we can rewritten in ~~CNF~~ (or DNF) then NANDs (by simply replacing).	$\lnot F$, $F \lor G$ and $F \land G$ can be rewritten <b>only</b> in terms of it.<br><br>For example NOT, AND, OR can be expressed in NAND form, thus we can rewritten in <b>CNF</b> (or DNF) then NANDs (by simply replacing). As we can write every formula in CNF (or DNF) this prooves it.

Tags: ETH::1._Semester::DiskMat::6._Logic::5._Propositional_Logic::4._Normal_Forms

Note 9: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: wV8=4Xrwg1

added

New Note

Front

$F[x]_{m(x)}^*$ is defined as:

Back

$F[x]_{m(x)}^*$ is defined as:

\[\{ a(x) \in F[x]_{m(x)} \ | \ \gcd(a(x), m(x)) = 1 \}\]

Field-by-field Comparison

Field	Before	After
Front		$F[x]_{m(x)}^*$ is defined as:
Back		\[\{ a(x) \in F[x]_{m(x)} \ \| \ \gcd(a(x), m(x)) = 1 \}\]

Tags: ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Field	Before	After
Text		\(\gcd(a, 0) = \) {{c1::\(\|a\|\)}}
Extra		This is why \(0\) not in \(Z_m^* \) and \(F[x]^*_{m(x)}\)

Field	Before	After
Front		\(F[x]_{m(x)}^*\) is defined as:
Back		\[\{ a(x) \in F[x]_{m(x)} \ \| \ \gcd(a(x), m(x)) = 1 \}\]

Note 1: ETH::A&D

Before

Front

Back

After

Front

Back

Note 2: ETH::A&D

Before

Front

Back

After

Front

Back

Note 3: ETH::DiskMat

Before

Front

Back

After

Front

Back

Note 4: ETH::DiskMat

Previous

New Note

Front

Back

Note 5: ETH::DiskMat

Before

Front

Back

After

Front

Back

Note 6: ETH::DiskMat

Before

Front

Back

After

Front

Back

Note 7: ETH::DiskMat

Before

Front

Back

After

Front

Back

Note 8: ETH::DiskMat

Before

Front

Back

After

Front

Back

Note 9: ETH::DiskMat

Previous

New Note

Front

Back