Anki Deck Changes

Note 1: ETH::1. Semester::A&D

Deck: ETH::1. Semester::A&D
Note Type: Horvath Classic
GUID: CJsa&>C5sO

modified

Before

Front

Kruskal's Algorithm can be executed in \(O(|E| + |V|\log|V|)\) time?

Back

Kruskal's Algorithm can be executed in \(O(|E| + |V|\log|V|)\) time?

No, we need to sort the edges which takes at least \(|E| \log |E|\) time.

After

Front

Can Kruskal's Algorithm be executed in \(O(|E| + |V|\log|V|)\) time?

Back

Can Kruskal's Algorithm be executed in \(O(|E| + |V|\log|V|)\) time?

No, we need to sort the edges which takes at least \(|E| \log |E|\) time.

Field-by-field Comparison

Field	Before	After
Front	Kruskal's Algorithm ~~can~~ be executed in \(O(\|E\| + \|V\|\log\|V\|)\) time?	Can Kruskal's Algorithm be executed in \(O(\|E\| + \|V\|\log\|V\|)\) time?

Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm

Note 2: ETH::1. Semester::A&D

Deck: ETH::1. Semester::A&D
Note Type: Horvath Classic
GUID: c1d=kD*#nb

modified

Before

Front

How do we prove/disprove such as statement "There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."

Back

How do we prove/disprove such as statement "There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."

We use the handshake Lemma: \(\sum \deg(v) = 7 \cdot 3 = 2 |E|\) but 21 is not even. Thus this cannot be true.

After

Front

How do we prove/disprove such a statement?

"There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."

Back

How do we prove/disprove such a statement?

"There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."

We use the handshake Lemma: \(\sum \deg(v) = 7 \cdot 3 = 2 |E|\) but 21 is not even. Thus this cannot be true.

Field-by-field Comparison

Field	Before	After
Front	How do we prove/disprove such as statement "There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."	How do we prove/disprove such a statement?<br><br>"There exists at least one undirected graph with 7 vertices in which all vertices have degree 3."

Tags: ETH::1._Semester::A&D::07._Graphs::1._Introduction_to_Graphs::1._Handshake_Lemma

Note 3: ETH::1. Semester::A&D

Deck: ETH::1. Semester::A&D
Note Type: Horvath Cloze
GUID: kCvO2]PU.a

modified

Before

Front

\(\ln(1)= 0\).

Back

\(\ln(1)= 0\).

After

Front

\(\ln(1)= {{c1:: 0::\text{Number} }}\)

Back

\(\ln(1)= {{c1:: 0::\text{Number} }}\)

Field-by-field Comparison

Field	Before	After
Text	\(\ln(1)= {{c1:: 0}}\).	\(\ln(1)= {{c1:: 0::\text{Number} }}\)

Tags: ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation

Note 4: ETH::1. Semester::A&D

Deck: ETH::1. Semester::A&D
Note Type: Horvath Classic
GUID: kXVME,u35.

modified

Before

Front

Merge Sort space Complexity?

Back

Merge Sort space Complexity?

\(O(n)\)

After

Front

What's the space complexity of merge sort?

Back

What's the space complexity of merge sort?

\(O(n)\)

Field-by-field Comparison

Field	Before	After
Front	~~Merge Sort~~ space Complexity?	What's the space complexity of merge sort?

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

Note 5: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: Bx0~E*k+P5

modified

Before

Front

a != 0 && b / a == 3 evaluates to ???

Back

a != 0 && b / a == 3 evaluates to ???

Works fine, since if a == 0, it shortcircuits and simply returns false.

After

Front

Does this code snippet work?

a != 0 && b / a == 3

Back

Does this code snippet work?

a != 0 && b / a == 3

Yes, since if a == 0, it shortcircuits and simply returns false.

Field-by-field Comparison

Field	Before	After
Front	<div><b>a != 0 && b / a == 3</b>~~ evaluates to ???~~</div>	<div><b>Does this code snippet work?</b></div><div><b><br></b></div><div><b>a != 0 && b / a == 3</b></div>
Back	~~Works fine~~, since if <b>a == 0, </b>it shortcircuits and simply returns false.	Yes, since if <b>a == 0, </b>it shortcircuits and simply returns false.

Tags: PlsFix::ClozeThatBish ETH::1._Semester::EProg::3._Control_Structures::1._Branching

Note 6: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: E_rcts7/^g

modified

Before

Front

while (i < n) {
result = result * k;
i = i + 1;
}

For the loop invariant, what bounds hold for i?

Back

while (i < n) {
result = result * k;
i = i + 1;
}

For the loop invariant, what bounds hold for i?

i <= n (the equality holds as we execute + 1 after the final execution)

In general: a x < n becomes x <= n and x <= n becomes x <= n + 1!

After

Front

while (i < n) {
result = result * k;
i = i + 1;
}

For the loop invariant, what bounds hold for i?

Back

while (i < n) {
result = result * k;
i = i + 1;
}

For the loop invariant, what bounds hold for i?

i <= n (the equality holds as we execute + 1 after the final execution)

In general: x < n becomes x <= n and x <= n becomes x <= n + 1

Field-by-field Comparison

Field	Before	After
Back	<div><code>i <= n</code> (the equality holds as we execute <code>+ 1</code> after the final execution)<br><br><div>In general: a x < n becomes x <= n and x <= n becomes x <= n + 1!</div></div>	<div><code>i <= n</code> (the equality holds as we execute <code>+ 1</code> after the final execution)<br><br><div>In general: x < n becomes x <= n and x <= n becomes x <= n + 1</div></div>

Tags: ETH::1._Semester::EProg::5._Logisches_Schliessen

Note 7: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: J)-A!rQ/Od

modified

Before

Front

int[][] b = new int[3][0]
int[] c = new int[3]

b[0] = c

does this compile / runtime?

Back

int[][] b = new int[3][0]
int[] c = new int[3]

b[0] = c

does this compile / runtime?

Yes, it works fine as we just set the pointer of b[0] to c. Java does not typecheck array dimensions.

After

Front

int[][] b = new int[3][0]
int[] c = new int[3]

b[0] = c

Is this fine?

Back

int[][] b = new int[3][0]
int[] c = new int[3]

b[0] = c

Is this fine?

Yes, it works fine as we just set the pointer of b[0] to c. Java does not typecheck array dimensions.

Field-by-field Comparison

Field	Before	After
Front	<code>int[][] b = new int[3][0]</code><br><code>int[] c = new int[3]</code> <br> <code>b[0] = c<br></code> ~~doe~~s this ~~compile / runtim~~e?	<code>int[][] b = new int[3][0]</code><br><code>int[] c = new int[3]</code> <br> <code>b[0] = c<br></code><br>Is this fine?

Tags: ETH::1._Semester::EProg::2._First_Java_Programs::3._Simple_Calculations::1._Types,_Variables,_Values

Note 8: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: MlNjJv:07k

modified

Before

Front

String s1 = "test";
String s2 = "test";
s1 == s2 returns?

Back

String s1 = "test";
String s2 = "test";
s1 == s2 returns?

false, as we compare references. To compare strings we should use .equals()

After

Front

String s1 = "test";
String s2 = "test";
s1 == s2 returns?

Back

String s1 = "test";
String s2 = "test";
s1 == s2 returns?

Usually false, as we compare references. To compare strings we should use .equals().

Field-by-field Comparison

Field	Before	After
Back	false, as we compare references. To compare strings we should use <b>.equals()</b>	Usually false, as we compare references. To compare strings we should use <b>.equals().</b>

Tags: ETH::1._Semester::EProg::4._Sequences PlsFix::ClozeThatBish

Note 9: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Image Occlusion-73a2c
GUID: gef_5DD5?n

modified

Before

Front

Back

After

Front

Back

Field-by-field Comparison

Field	Before	After
Occlusion	{{c1::image-occlusion:rect:left=.116:top=.~~0188~~:width=.~~6994~~:height=.~~1251:oi=1~~}}<br>{{c2::image-occlusion:rect:left=.~~1147~~:top=.~~2666~~:width=.~~8699~~:height=.~~3679:oi=1~~}}<br>{{c3::image-occlusion:rect:left=.~~0988~~:top=.~~7522~~:width=.~~7656~~:height=.~~2278:oi=1~~}}<br>	{{c2::image-occlusion:rect:left=.1151:top=.2639:width=.8709:height=.3659}}<br>{{c3::image-occlusion:rect:left=.0974:top=.7498:width=.7647:height=.2279}}<br>{{c1::image-occlusion:rect:left=.1151:top=.018:width=.6997:height=.126}}<br>

Tags: ETH::1._Semester::EProg::5._Logisches_Schliessen

Note 10: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: io,]_+ZcUp

modified

Before

Front

What is the result of:

void test(Integer k) {
k = Integer.valueOf(1); This only changes it locally! (Shadowing)
//
k.value = 1; This changes the value for the caller also
}

Back

What is the result of:

void test(Integer k) {
k = Integer.valueOf(1); This only changes it locally! (Shadowing)
//
k.value = 1; This changes the value for the caller also
}

After

Front

What is the result of:

void test(Integer k) {
k = Integer.valueOf(1); This only changes it locally! (Shadowing)
//
k.value = 1; This changes the value for the caller as well
}

Back

What is the result of:

void test(Integer k) {
k = Integer.valueOf(1); This only changes it locally! (Shadowing)
//
k.value = 1; This changes the value for the caller as well
}

Field-by-field Comparison

Field	Before	After
Text	What is the result of:<br><br><b>void test(Integer k) {</b><br>    <b>k = Integer.valueOf(1); </b>{{c1:: This only changes it locally! (Shadowing)}}<br>//<br>    <b>k.value = 1;  </b>{{c1:: This changes the value for the caller a~~lso~~}}<br><b>}</b>	What is the result of:<br><br><b>void test(Integer k) {</b><br>    <b>k = Integer.valueOf(1); </b>{{c1:: This only changes it locally! (Shadowing)}}<br>//<br>    <b>k.value = 1;  </b>{{c1:: This changes the value for the caller as well}}<br><b>}</b>

Tags: ETH::1._Semester::EProg::Shadowing ETH::1._Semester::EProg::99._Shadowing

Note 11: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: q|N{Bb]-?+

modified

Before

Front

// {P}
if (a) {
    S1;
} else {
    S2;
}
// {Q}

How to find the precondition?

Back

// {P}
if (a) {
    S1;
} else {
    S2;
}
// {Q}

How to find the precondition?

Muss man zwei Fälle checken:

\(P \land a \implies Q\) when S1; is executed.
\(P \land \lnot a \implies Q\) when S2; is executed.

Dann kann man mit einem || beide Fälle in der Precondition verbinden: a && precondition1 OR !a && precondition2

After

Front

// {P}
if (a) {
    S1;
} else {
    S2;
}
// {Q}

How can the precondition be found?

Back

// {P}
if (a) {
    S1;
} else {
    S2;
}
// {Q}

How can the precondition be found?

Man muss zwei Fälle checken:

\(P \land a \implies Q\) when S1; is executed.
\(P \land \lnot a \implies Q\) when S2; is executed.

Dann kann man mit einem || beide Fälle in der Precondition verbinden: a && precondition1 OR !a && precondition2

Field-by-field Comparison

Field	Before	After
Front	<pre><code>// {P} if (a) { S1; } else { S2; } // {Q} </code> </pre>How ~~to find~~ the precondition?	<pre><code>// {P} if (a) { S1; } else { S2; } // {Q}</code> </pre>How can the precondition be found?
Back	M~~uss man~~ zwei Fälle checken:<br><ul><li>\(P \land a \implies Q\) when S1; is executed.</li><li>\(P \land \lnot a \implies Q\) when S2; is executed. </li></ul>Dann kann man mit einem <b>\|\|</b> beide Fälle in der Precondition verbinden: <code>a && precondition1</code> OR <code>!a && precondition2</code>	Man muss zwei Fälle checken:<br><ul><li>\(P \land a \implies Q\) when S1; is executed.</li><li>\(P \land \lnot a \implies Q\) when S2; is executed. </li></ul>Dann kann man mit einem <b>\|\|</b> beide Fälle in der Precondition verbinden: <code>a && precondition1</code> OR <code>!a && precondition2</code>

Tags: ETH::1._Semester::EProg::5._Logisches_Schliessen

Note 12: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: t=MANr.EfE

modified

Before

Front

WP { }
PC { true }

the WP is .

Back

WP { }
PC { true }

the WP is .

Everything implies true and true implies true.

After

Front

What is the weakest precondition for an empty program with postcondition true?

Back

What is the weakest precondition for an empty program with postcondition true?

true.

Everything implies true and true implies true.

Field-by-field Comparison

Field	Before	After
Front	~~WP { }<br>PC { true }<br><br>the WP is {{c1:: true}}.~~	<div>What is the weakest precondition for an empty program with postcondition <code>true</code>?</div> <div><strong></strong></div>
Back	Everything implies true and true implies true.	true.<br><br>Everything implies true and true implies true.

Tags: ETH::1._Semester::EProg::5._Logisches_Schliessen

Note 13: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: tja~6C@vsv

modified

Before

Front

Does Java enforce array dimensions using type- or runtime-checks?

Back

Does Java enforce array dimensions using type- or runtime-checks?

No.

int[][] b = new int[3][0]
int[] c = new int[3]

b[0] = c

is fine

After

Front

Does Java enforce array dimensions using type- or runtime-checks?

Back

Does Java enforce array dimensions using type- or runtime-checks?

No, this is fine:

int[][] b = new int[3][0];
int[] c = new int[3];
b[0] = c;

Field-by-field Comparison

Field	Before	After
Back	No.<br><br><code>int[][] b = new int[3][0]</code> <br><code>int[] c = new int[3]</code> <br> <code>b[0] = c~~<br><br></code> is fine~~	No, this is fine:<br><br><code>int[][] b = new int[3][0];</code><br><code>int[] c = new int[3];</code> <br> <code>b[0] = c;</code>

Tags: ETH::1._Semester::EProg::2._First_Java_Programs::3._Simple_Calculations::1._Types,_Variables,_Values