Anki Deck Changes

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

Deck: ETH::1. Semester::A&D
Note Type: Horvath Classic
GUID: FS|421SN1o

modified

Before

Front

Explain how unions works in the optimised Union-Find:

Back

Explain how unions works in the optimised Union-Find:

Arrays:

rep, where rep[v] gives the representative of $v$.
members, where members[rep[v]] which contains all members of the ZHK of $v$
rank, where rank[rep[v]] contains the size of the ZHK of $v$.

We always merge the smaller ZHK into the bigger to minimise updates.

We update the reps, then the membership lists and finally the size

After

Front

Explain how union works in the optimised Union-Find:

Back

Explain how union works in the optimised Union-Find:

Arrays:

rep, where rep[v] gives the representative of $v$.
members, where members[rep[v]] which contains all members of the ZHK of $v$
rank, where rank[rep[v]] contains the size of the ZHK of $v$.

We always merge the smaller ZHK into the bigger to minimise updates.

We update the reps, then the membership lists and finally the size.

Field-by-field Comparison

Field	Before	After
Front	Explain how unions works in the optimised <b>Union-Find:</b>	Explain how union works in the optimised <b>Union-Find:</b>
Back	Arrays:<br><ul><li><b>rep</b>, where <b>rep[v]</b> gives the representative of $v$.</li><li><b>members</b>, where <b>members[rep[v]] </b>which contains all members of the ZHK of $v$<br></li><li><b>rank</b>, where <b>rank[rep[v]]</b> contains the size of the ZHK of $v$.</li></ul><div>We always merge the smaller ZHK into the bigger to minimise updates.</div><img src="paste-5129796b3ae6c46edebbaae726a47f0c892c2435.jpg"><br>We update the reps, then the membership lists and finally the size	Arrays:<br><ul><li><b>rep</b>, where <b>rep[v]</b> gives the representative of $v$.</li><li><b>members</b>, where <b>members[rep[v]] </b>which contains all members of the ZHK of $v$<br></li><li><b>rank</b>, where <b>rank[rep[v]]</b> contains the size of the ZHK of $v$.</li></ul><div>We always merge the smaller ZHK into the bigger to minimise updates.</div><img src="paste-5129796b3ae6c46edebbaae726a47f0c892c2435.jpg"><br>We update the reps, then the membership lists and finally the size.

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

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

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

modified

Before

Front

Runtime of Kruskal's Algorithm?

Back

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

Runtime of Kruskal's Algorithm?

Back

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
Extra Info	This requires the Union Find Datastructure	This requires the Union Find datastructure.

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

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

Deck: ETH::1. Semester::A&D
Note Type: Horvath Classic
GUID: wxuX$c!)%k

modified

Before

Front

A graph with this DP table from F-W:

contains ___ negative cycles.

Back

A graph with this DP table from F-W:

contains ___ negative cycles.

no (there is no diagonal $< 0$)

After

Front

A graph with this DP table from Floyd-Warshall:

contains ___ negative cycles.

Back

A graph with this DP table from Floyd-Warshall:

contains ___ negative cycles.

no (there is no diagonal $< 0$)

Field-by-field Comparison

Field	Before	After
Front	A graph with this DP table from F-W:<br><img src="paste-deae0d6c4a31dc3e71c5f654f12387c82b186739.jpg"><br>contains ___ negative cycles.	A graph with this DP table from Floyd-Warshall:<br><img src="paste-deae0d6c4a31dc3e71c5f654f12387c82b186739.jpg"><br>contains ___ negative cycles.

Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm PlsFix::ClozeThatBish

Note 4: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: El$[?h8w;k

modified

Before

Front

Attribute access modifiers:

default: package scoped, only available in same package.
public: by everyone
private: only accessible from within the object itself (not shared with other instances, unlike static)
static:: no initialisation needed, can be accessed through Math.PI
final: prevents overwriting, like const
protected: only by this class and subclasses

Back

Attribute access modifiers:

default: package scoped, only available in same package.
public: by everyone
private: only accessible from within the object itself (not shared with other instances, unlike static)
static:: no initialisation needed, can be accessed through Math.PI
final: prevents overwriting, like const
protected: only by this class and subclasses

After

Front

Attribute access modifiers:

default: package scoped, only available in same package.
public: by everyone
private: only accessible from within the object itself (not shared with other instances, unlike static)
static: no initialisation needed, can be accessed through Math.PI
final: prevents overwriting, like const
protected: only by this class and subclasses

Back

Attribute access modifiers:

default: package scoped, only available in same package.
public: by everyone
private: only accessible from within the object itself (not shared with other instances, unlike static)
static: no initialisation needed, can be accessed through Math.PI
final: prevents overwriting, like const
protected: only by this class and subclasses

Field-by-field Comparison

Field	Before	After
Text	Attribute access modifiers:<br><ul><li>default: {{c1:: package scoped, only available in same package.}}</li><li>public: {{c2:: by everyone}}</li><li>private: {{c3:: only accessible from within the object itself (not shared with other instances, unlike static)}}</li><li>static:: {{c4:: no initialisation needed, can be accessed through <b>Math.PI</b>}}<br></li><li>final: {{c5:: prevents overwriting, like const}}</li><li>protected: {{c6:: only by this class and subclasses}}</li></ul>	Attribute access modifiers:<br><ul><li>default: {{c1:: package scoped, only available in same package.}}</li><li>public: {{c2:: by everyone}}</li><li>private: {{c3:: only accessible from within the object itself (not shared with other instances, unlike static)}}</li><li>static: {{c4:: no initialisation needed, can be accessed through <b>Math.PI</b>}}<br></li><li>final: {{c5:: prevents overwriting, like const}}</li><li>protected: {{c6:: only by this class and subclasses}}</li></ul>

Tags: ETH::1._Semester::EProg::7._Classes_and_Objects

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: F$o5lV^z=H

modified

Before

Front

Note that a class can implement multiple interfaces.

If a method is defined in multiple of those interfaces, it of course has to implemented only once.

Back

Note that a class can implement multiple interfaces.

If a method is defined in multiple of those interfaces, it of course has to implemented only once.

After

Front

Note that a class can implement multiple interfaces.

If a method is defined in multiple of those interfaces, it of course has to be implemented only once.

Back

Note that a class can implement multiple interfaces.

If a method is defined in multiple of those interfaces, it of course has to be implemented only once.

Field-by-field Comparison

Field	Before	After
Text	<div>Note that a class can<b> </b>{{c1::<b>implement multiple interfaces</b>}}.</div><div>If a method is defined in {{c1::multiple of those interfaces}}, it {{c1::of course has to implemented only once}}.</div>	<div>Note that a class can<b> </b>{{c1::<b>implement multiple interfaces</b>}}.</div><div>If a method is defined in {{c1::multiple of those interfaces}}, it {{c1::of course has to be implemented only once}}.</div>

Tags: ETH::1._Semester::EProg::13._Interfaces

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: G]t&7SvtKp

modified

Before

Front

In a dynamic dispatch, the this still refers to the dynamic type, thus even if the method is in a superclass, it will always try to use the "most overriden" method.

Back

In a dynamic dispatch, the this still refers to the dynamic type, thus even if the method is in a superclass, it will always try to use the "most overriden" method.

After

Front

In a dynamic dispatch, the "this"-keyword still refers to the dynamic type, thus even if the method is in a superclass, it will always try to use the "most overriden" method.

Back

In a dynamic dispatch, the "this"-keyword still refers to the dynamic type, thus even if the method is in a superclass, it will always try to use the "most overriden" method.

Field-by-field Comparison

Field	Before	After
Text	In a dynamic dispatch, the this still refers to the dynamic type, thus {{c1:: even if the method is in a superclass, it will always try to use the "most overriden" method}}.	In a dynamic dispatch, the "this"-keyword still refers to the dynamic type, thus {{c1:: even if the method is in a superclass, it will always try to use the "most overriden" method}}.

Tags: ETH::1._Semester::EProg::10._Inheritance::2._Polymorphism::3._Static_vs_Dynamic

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: HNxps|u:&w

modified

Before

Front

Enums are special classes, they are initialised like this:

Back

Enums are special classes, they are initialised like this:

public enum Status {
    SUBMITTED,
    PAID,
    ...
}

After

Front

How are enums initialized?

Back

How are enums initialized?

public enum Status {
    SUBMITTED,
    PAID,
    ...
}

Field-by-field Comparison

Field	Before	After
Front	~~Enums are special classes, they are~~ initialised ~~like this:~~	How are enums initialized?

Tags: ETH::1._Semester::EProg::7._Classes_and_Objects::2._Enums

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: Hz_:Sp*X(y

modified

Before

Front

class A {  
    public int x = 5;
}  

class B extends A {  
    public int y = 6;
    public int test() { return 0; }

}

A a1 = new B(1);
B.y; //  leads to a compile error, as A doesn't have x
B.test() //  leads to a compile error, as A doesn't have test()

Back

class A {  
    public int x = 5;
}  

class B extends A {  
    public int y = 6;
    public int test() { return 0; }

}

A a1 = new B(1);
B.y; //  leads to a compile error, as A doesn't have x
B.test() //  leads to a compile error, as A doesn't have test()

After

Front

class A {  
    public int x = 5;
}  

class B extends A {  
    public int y = 6;
    public int test() { return 0; }

    public B(int i) {
        super();
    }


A a1 = new B(1);

a1.y; //  leads to a compile error, as A doesn't have x

a1.test(); //

leads to a compile error, as A doesn't have test()

Back

class A {  
    public int x = 5;
}  

class B extends A {  
    public int y = 6;
    public int test() { return 0; }

    public B(int i) {
        super();
    }


A a1 = new B(1);

a1.y; //  leads to a compile error, as A doesn't have x

a1.test(); //

leads to a compile error, as A doesn't have test()

Field-by-field Comparison

Field	Before	After
Text	<pre><code>class A { public int x = 5; } class B extends A { public int y = 6; public int test() { return 0; } </code></pre><pre><code>} A a1 = new B(1); B.y; // {{c1:: leads to a compile error, as A doesn't have x}} B.test() // </code>{{c2:: leads to a compile error, as A doesn't have test()}}~~</pre>~~	<pre><code>class A { public int x = 5; } class B extends A { public int y = 6; public int test() { return 0; }</code></pre><pre><code><div> public B(int i) {<br> super();<br> }</div></code></pre><pre><span style="font-family: "Liberation Sans";">}</span><br></pre><code> A a1 = new B(1); <br>a1.y; // {{c1:: leads to a compile error, as A doesn't have x}} <br>a1.test(); // </code>{{c2:: leads to a compile error, as A doesn't have test()}}

Tags: ETH::1._Semester::EProg::10._Inheritance::2._Polymorphism::3._Static_vs_Dynamic

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Classic
GUID: gK8R,r`Ne1

modified

Before

Front

Java Modulo operator a % b expression

Back

Java Modulo operator a % b expression

(a / b) * b + (a % b) = a (with a / b being division with rest)

In general, if the a is negative, the result is negative.

After

Front

How is a % b defined in Java?

Back

How is a % b defined in Java?

(a / b) * b + (a % b) = a (with a / b being division with rest)

In general, if the a is negative, the result is negative.

Field-by-field Comparison

Field	Before	After
Front	~~Java Modulo operator <b>a % b</b> expression~~	How is a % b defined in Java?

Tags: ETH::1._Semester::EProg::2._First_Java_Programs::3._Simple_Calculations