Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Image Occlusion
GUID: GKG~Tp?e4l

modified

Before

Front

Back

After

Front

Note that the key parameter of insertAfter and delete in lists refers to the actual node, not it's value.

Back

Note that the key parameter of insertAfter and delete in lists refers to the actual node, not it's value.

Field-by-field Comparison

Field	Before	After
Header		Note that the key parameter of insertAfter and delete in lists refers to the actual node, not it's value.<br>

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

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Algorithms
GUID: NAHrkHd^ik

modified

Before

Front

Runtime of Merge Sort?

Back

Runtime of Merge Sort?

Best Case: $O(n \log n)$
Worst Case: $O(n \log n)$

After

Front

Runtime of Merge Sort?

Back

Runtime of Merge Sort?

Best Case: $O(n \log n)$
Worst Case: $O(n \log n)$

Field-by-field Comparison

Field	Before	After
Invariant	<div>~~Merge sort always~~ sorts correctly ~~when called for a sub-array shorter than $r - l + 1$.</div><div>This means~~ that merge ~~has to~~ correctly ~~merge the two sub-arrays into a complete array~~.</div>	<div>For all $n < r - l + 1$ merge sort correctly sorts any sub-array of length n.</div><div><br></div><div>Assuming the invariant holds, the two recursive calls return sorted halves. </div><div><br></div><div>It remains to show that merge correctly combines two sorted halves into a sorted whole.</div>

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::4._Merge_Sort

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: H*J4QbU35P

modified

Before

Front

What exponentiation operation is valid in modular arithmetic?

Back

What exponentiation operation is valid in modular arithmetic?

I can do:

$a \equiv_n b$ and then $a^x \equiv_n b^x$

What is illegal is:

$a \equiv_n b$ and $c \equiv_n d$ and then doing $a^c \equiv_n b^d$

After

Front

What exponentiation operation is valid in modular arithmetic?

Back

What exponentiation operation is valid in modular arithmetic?

This is allowed:

$a \equiv_n b$ and then $a^x \equiv_n b^x$

But this on the other hand is illegal:

$a \equiv_n b$ and $c \equiv_n d$ and then doing $a^c \equiv_n b^d$

Field-by-field Comparison

Field	Before	After
Back	~~I can do~~:<br><ul><li>$a \equiv_n b$ and then $a^x \equiv_n b^x$<br></li></ul><div>~~What~~ is illegal is:</div><div><ul><li>$a \equiv_n b$ and $c \equiv_n d$ and then doing $a^c \equiv_n b^d$</li></ul></div>	This is allowed:<br><ul><li>$a \equiv_n b$ and then $a^x \equiv_n b^x$<br></li></ul><div>But this on the other hand is illegal:</div><div><ul><li>$a \equiv_n b$ and $c \equiv_n d$ and then doing $a^c \equiv_n b^d$</li></ul></div>

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::2._Modular_Arithmetic

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Pz>]O?kRm)

modified

Before

Front

It follow from the respective definitions that $\gcd(a,b) \times \text{lcm}(a,b) =$ $ab$.

Back

It follow from the respective definitions that $\gcd(a,b) \times \text{lcm}(a,b) =$ $ab$.

After

Front

It follows from the respective definitions that $\gcd(a,b) \cdot \text{lcm}(a,b) =$ $ab$.

Back

It follows from the respective definitions that $\gcd(a,b) \cdot \text{lcm}(a,b) =$ $ab$.

Field-by-field Comparison

Field	Before	After
Text	It follow from the respective definitions that $\gcd(a,b) \~~times~~ \text{lcm}(a,b) =$ {{c1:: $ab$}}.	It follows from the respective definitions that $\gcd(a,b) \cdot \text{lcm}(a,b) =$ {{c1:: $ab$}}.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::3._Expressing_gcd_and_lcm

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: d_Wm7Nf:G2

modified

Before

Front

What do we need to state before using the decomposition of an $n \in \mathbb{Z}$ into prime factors?

Back

What do we need to state before using the decomposition of an $n \in \mathbb{Z}$ into prime factors?

We need to state that this is allowed by the fundamental theorem of arithmetic.

After

Front

What do we need to state before using the decomposition of an $n \in \mathbb{Z}$ into prime factors?

Back

What do we need to state before using the decomposition of an $n \in \mathbb{Z}$ into prime factors?

That this is allowed by the fundamental theorem of arithmetic.

Field-by-field Comparison

Field	Before	After
Back	~~We need to state t~~hat this is allowed by the fundamental theorem of arithmetic.	That this is allowed by the fundamental theorem of arithmetic.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic

Note 6: ETH::DiskMat

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

modified

Before

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

After

Front

How does one show the injectivity of a function?

Back

How does one show the injectivity of a function?

Assume $a \not= b$ and show that$f(a) \neq f(b)$. Equivalently (by contrapositive), assume $f(a) = f(b)$ and show that $a = b$.

Example: $f(x) = 2x$, if $f(a) = f(b)$, then $2a = 2b$, which implies $a = b$. Hence $f$ is injective.

Field-by-field Comparison

Field	Before	After
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 \ 2~~a = 2b$. ~~This however $ \ \implies a = b$~~.	Assume $a \not= b$ and show that$f(a) \neq f(b)$. Equivalently (by contrapositive), assume $f(a) = f(b)$ and show that $a = b$.<br><br><b>Example: </b>$f(x) = 2x$, if $f(a) = f(b)$, then $2a = 2b$, which implies $a = b$. Hence $f$ is injective.

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

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: g|p?@3JwCd

modified

Before

Front

Why does $ax \equiv_m 1$ have no solution when $\text{gcd}(a, m) = d > 1$?

Back

Why does $ax \equiv_m 1$ have no solution when $\text{gcd}(a, m) = d > 1$?

We can rewrite $ax \equiv_m 1$ as $ax - 1 = km \Leftrightarrow ax - km = 1$. Now since, $d | a$ and $d | m$, then $d | ax$ and $d | km$ for any $x$.
Thus $d | (ax - km)$, and $ax - km = 1$.

But $d \nmid 1 \implies d \nmid (ax - km)$, which is a contradiction. Thus $ax$ can never be congruent to $1$ modulo $m$.

After

Front

Why does $ax \equiv_m 1$ have no solution when $\text{gcd}(a, m) = d > 1$?

Back

Why does $ax \equiv_m 1$ have no solution when $\text{gcd}(a, m) = d > 1$?

We can rewrite $ax \equiv_m 1$ as $ax - 1 = km \Leftrightarrow ax - km = 1$. Now since, $d \mid a$ and $d \mid m$, then $d \mid ax$ and $d \mid km$ for any $x$.
Thus $d \mid (ax - km)$, and $ax - km = 1$.

But $d \nmid 1 \implies d \nmid (ax - km)$, which is a contradiction. Thus $ax$ can never be congruent to $1$ modulo $m$.

Field-by-field Comparison

Field	Before	After
Back	We can rewrite $ax \equiv_m 1$ as $ax - 1 = km \Leftrightarrow ax - km = 1$. Now since, $d \| a$ and $d \| m$, then $d \| ax$ and $d \| km$ for any $x$.<br>Thus $d \| (ax - km)$, and $ax - km = 1$.<br><br>But $d \nmid 1 \implies d \nmid (ax - km)$, which is a contradiction. Thus $ax$ can never be congruent to $1$ modulo $m$.	We can rewrite $ax \equiv_m 1$ as $ax - 1 = km \Leftrightarrow ax - km = 1$. Now since, $d \mid a$ and $d \mid m$, then $d \mid ax$ and $d \mid km$ for any $x$.<br>Thus $d \mid (ax - km)$, and $ax - km = 1$.<br><br>But $d \nmid 1 \implies d \nmid (ax - km)$, which is a contradiction. Thus $ax$ can never be congruent to $1$ modulo $m$.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses

Note 8: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: iQE!&/N&9W

modified

Before

Front

How do polynomials behave under modular reduction? (Corollary 4.15)

Back

How do polynomials behave under modular reduction? (Corollary 4.15)

Let $f(x_1, \dots, x_k)$ be a polynomial with integer coefficients, and let $m \geq 1$. If $a_i \equiv_m b_i$ for $1 \leq i \leq k$, then: \[f(a_1, \dots, a_k) \equiv_m f(b_1, \dots, b_k)\]

After

Front

How do polynomials behave under modular reduction? (Corollary 4.15)

Back

How do polynomials behave under modular reduction? (Corollary 4.15)

Let $f(x_1, \dots, x_k)$ be a polynomial with integer coefficients, and let $m \geq 1$.

If $a_i \equiv_m b_i$ for all $i \in \{1, ..., k\}$, then: \[f(a_1, \dots, a_k) \equiv_m f(b_1, \dots, b_k)\]

Field-by-field Comparison

Field	Before	After
Back	Let $f(x_1, \dots, x_k)$ be a polynomial with integer coefficients, and let $m \geq 1$. If $a_i \equiv_m b_i$ for $1 \~~leq i \leq k~~$, then: \[f(a_1, \dots, a_k) \equiv_m f(b_1, \dots, b_k)\]	Let $f(x_1, \dots, x_k)$ be a polynomial with integer coefficients, and let $m \geq 1$. <br><br>If $a_i \equiv_m b_i$ for  all $i \in \{1, ..., k\}$, then: \[f(a_1, \dots, a_k) \equiv_m f(b_1, \dots, b_k)\]

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::1._Modular_Congruences

Note 9: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: l7;;$C9=2

modified

Before

Front

What is the multiplicative inverse of $a$ modulo $m$?

Back

What is the multiplicative inverse of $a$ modulo $m$?

The unique solution $x \in \mathbb{Z}_m$ to the congruence equation $ax \equiv_m 1$, where $\text{gcd}(a, m) = 1$. Denoted $a^{-1} \pmod{m}$ or $1/a \pmod{m}$.

After

Front

What is the meaning of the multiplicative inverse of some number $a$ modulo $m$?

Back

What is the meaning of the multiplicative inverse of some number $a$ modulo $m$?

It is the unique solution $x \in \mathbb{Z}_m$ to the congruence equation $ax \equiv_m 1$, where $\text{gcd}(a, m) = 1$. Denoted $a^{-1} \pmod{m}$ or $1/a \pmod{m}$.

Field-by-field Comparison

Field	Before	After
Front	What is the multiplicative inverse of ~~$a$~~ modulo $m$?	What is the meaning of the multiplicative inverse of some number $a$ modulo $m$?
Back	The unique solution $x \in \mathbb{Z}_m$ to the congruence equation $ax \equiv_m 1$, where $\text{gcd}(a, m) = 1$. Denoted $a^{-1} \pmod{m}$ or $1/a \pmod{m}$.	It is the unique solution $x \in \mathbb{Z}_m$ to the congruence equation $ax \equiv_m 1$, where $\text{gcd}(a, m) = 1$. Denoted $a^{-1} \pmod{m}$ or $1/a \pmod{m}$.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::3._Multiplicative_Inverses

Note 10: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: pI:![>}CgZ

modified

Before

Front

Give the formal definition of "$a$ is congruent to $b$ modulo $m$".

Back

Give the formal definition of "$a$ is congruent to $b$ modulo $m$".

\[a \equiv_m b \overset{\text{def}}{\Longleftrightarrow} m | (a - b)\] Also written as $a \equiv b \pmod{m}$.

After

Front

Give the formal definition of "$a$ is congruent to $b$ modulo $m$".

Back

Give the formal definition of "$a$ is congruent to $b$ modulo $m$".

\[a \equiv_m b \overset{\text{def}}{\Longleftrightarrow} m \mid (a - b)\] Also written as $a \equiv b \pmod{m}$.

Field-by-field Comparison

Field	Before	After
Back	\[a \equiv_m b \overset{\text{def}}{\Longleftrightarrow} m \| (a - b)\] Also written as $a \equiv b \pmod{m}$.	\[a \equiv_m b \overset{\text{def}}{\Longleftrightarrow} m \mid (a - b)\] Also written as $a \equiv b \pmod{m}$.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::1._Modular_Congruences

Note 11: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: xWhw%ncc|4

modified

Before

Front

Verify that $\equiv_m$ is reflexive, symmetric, and transitive.

Reflexive: $a \equiv_m a$ since $m | (a - a) = 0$ ✓
Symmetric: $a \equiv_m b \Rightarrow m | (a-b) \Rightarrow m | (b-a) \Rightarrow b \equiv_m a$ ✓
Transitive: If $m | (a-b)$ and $m | (b-c)$, then $m | (a-b+b-c) = (a-c)$ ✓

Back

Verify that $\equiv_m$ is reflexive, symmetric, and transitive.

Reflexive: $a \equiv_m a$ since $m | (a - a) = 0$ ✓
Symmetric: $a \equiv_m b \Rightarrow m | (a-b) \Rightarrow m | (b-a) \Rightarrow b \equiv_m a$ ✓
Transitive: If $m | (a-b)$ and $m | (b-c)$, then $m | (a-b+b-c) = (a-c)$ ✓

After

Front

Verify that $\equiv_m$ is reflexive, symmetric, and transitive.

Reflexive: $a \equiv_m a$ since $m \mid (a - a) = 0$ ✓
Symmetric: $a \equiv_m b \Rightarrow m \mid (a-b) \Rightarrow m \mid (b-a) \Rightarrow b \equiv_m a$ ✓
Transitive: If $m \mid (a-b)$ and $m \mid (b-c)$, then $m \mid (a-b+b-c) = (a-c)$ ✓

Back

Verify that $\equiv_m$ is reflexive, symmetric, and transitive.

Reflexive: $a \equiv_m a$ since $m \mid (a - a) = 0$ ✓
Symmetric: $a \equiv_m b \Rightarrow m \mid (a-b) \Rightarrow m \mid (b-a) \Rightarrow b \equiv_m a$ ✓
Transitive: If $m \mid (a-b)$ and $m \mid (b-c)$, then $m \mid (a-b+b-c) = (a-c)$ ✓

Field-by-field Comparison

Field	Before	After
Text	Verify that $\equiv_m$ is reflexive, symmetric, and transitive.<br><ul><li><strong>Reflexive</strong>: {{c1:: $a \equiv_m a$ since $m \| (a - a) = 0$ ✓}}</li><li><strong>Symmetric</strong>: {{c2:: $a \equiv_m b \Rightarrow m \| (a-b) \Rightarrow m \| (b-a) \Rightarrow b \equiv_m a$ ✓}}</li><li><strong>Transitive</strong>: {{c3:: If $m \| (a-b)$ and $m \| (b-c)$, then $m \| (a-b+b-c) = (a-c)$ ✓}}</li></ul>	Verify that $\equiv_m$ is reflexive, symmetric, and transitive.<br><ul><li><strong>Reflexive</strong>: {{c1:: $a \equiv_m a$ since $m \mid (a - a) = 0$ ✓}}</li><li><strong>Symmetric</strong>: {{c2:: $a \equiv_m b \Rightarrow m \mid (a-b) \Rightarrow m \mid (b-a) \Rightarrow b \equiv_m a$ ✓}}</li><li><strong>Transitive</strong>: {{c3:: If $m \mid (a-b)$ and $m \mid (b-c)$, then $m \mid (a-b+b-c) = (a-c)$ ✓}}</li></ul>

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::5._Congruences_and_Modular_Arithmetic::1._Modular_Congruences