Anki Deck Changes

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: hL7UB-)y6N

modified

Before

Front

Runtime of Floyd-Warshall?

Back

Runtime of Floyd-Warshall?

\(O(|V|^3)\)

After

Front

Runtime of Floyd-Warshall?

Back

Runtime of Floyd-Warshall?

\(O(|V|^3)\)

Field-by-field Comparison

Field	Before	After
Approach	<ol><li><b>Initialise</b>: distance matrix D D[i][j] is the weight of the edge from \(i \rightarrow j\) if it exists, \(\infty\) otherwise<br></li><li><b>Iterate over intermediate</b>: for each vertex \(k\) update D[i][j] = min(D[i][j], D[i][k] + D[k][j]). for all intermediate k from 1,...,n</li></ol><div><br></div><div>The final distance matrix D contains the shortest path from any i to j.</div><div><br></div><div><i>Note that this can also be done using a 3d DP table, the 2d is just optimised.</i><br></div>	<ol><li><b>Initialise</b>: distance matrix D D[i][j] is the weight of the edge from \(i \rightarrow j\) if it exists, \(\infty\) otherwise<br></li><li><b>Iterate over intermediate</b>: for each vertex \(k\) update D[i][j] = min(D[i][j], D[i][k] + D[k][j]). for all intermediate k from 1, ..., n</li></ol><div><br></div><div>The final distance matrix D contains the shortest path from any i to j.</div><div><br></div><div><i>Note that this can also be done using a 3d DP table, the 2d is just optimised.</i><br></div>

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

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

Deck: ETH::1. Semester::A&D
Note Type: Horvath Cloze
GUID: oWyDyQ_9bL

modified

Before

Front

After adding \(x\) edges to the Union-Find DS, the repr array contains \(n-x\) components (different values).

Back

After adding \(x\) edges to the Union-Find DS, the repr array contains \(n-x\) components (different values).

Each added edge removes one unconnected component.

After

Front

After adding \(x\) edges to the Union-Find datastructure, the repr array contains \(n-x\) components (different values).

Back

After adding \(x\) edges to the Union-Find datastructure, the repr array contains \(n-x\) components (different values).

Each added edge removes one unconnected component.

Field-by-field Comparison

Field	Before	After
Text	After adding \(x\) edges to the Union-Find DS, the <b>repr</b> array contains {{c1::\(n-x\) components (different values)}}.	After adding \(x\) edges to the Union-Find datastructure, the <b>repr</b> array contains {{c1::\(n-x\) components (different values)}}.

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

Note 3: ETH::1. Semester::EProg

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: DL*jz,QL[w

modified

Before

Front

WP { }
PC {false}
the WP is false

Back

WP { }
PC {false}
the WP is false

As only false implies false.

After

Front

The weakest precondition for an empty program with postcondition false is false.

Back

The weakest precondition for an empty program with postcondition false is false.

As only false implies false.

Field-by-field Comparison

Field	Before	After
Text	~~WP { }<br>PC {false}<br>the WP~~ is {{c1::false}}	The weakest precondition for an empty program with postcondition false is {{c1::false}}.

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

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

Deck: ETH::1. Semester::EProg
Note Type: Horvath Cloze
GUID: E_A@gwOm;?

modified

Before

Front

Arrays has helper methods that make simple operations quicker:

Arrays.equals(a, b) to compare arrays
Arrays.copyOf(arr, l) that returns a new copied array of length l
Sorting useing Arrays.sort(arr)
toString() and deepToString()

Back

Arrays has helper methods that make simple operations quicker:

Arrays.equals(a, b) to compare arrays
Arrays.copyOf(arr, l) that returns a new copied array of length l
Sorting useing Arrays.sort(arr)
toString() and deepToString()

After

Front

The Arrays class has helper methods that make simple operations quicker:

Arrays.equals(a, b) to compare arrays
Arrays.copyOf(arr, l) that returns a new copied array of length l
Sorting using Arrays.sort(arr)
toString() and deepToString()

Back

ETH::1._Semester::EProg::4._Sequences

The Arrays class has helper methods that make simple operations quicker:
Arrays.equals(a, b) to compare arrays
Arrays.copyOf(arr, l) that returns a new copied array of length l
Sorting using Arrays.sort(arr)
toString() and deepToString()

Arrays.deepToString() converts a nested/multidimensional array to a readable string representation, recursively handling inner arrays.

Field-by-field Comparison

Field Before After

Text Arrays has helper methods that make simple operations quicker: <ul><li>{{c1:: Arrays.equals(a, b) to compare arrays}} </li><li>{{c2::~~ ~~Arrays.copyOf(arr, l) that returns a new copied array of length l}}</li><li>{{c3:: Sorting useing Arrays.sort(arr)}}</li><li>{{c4:: toString() and deepToString()}}</li></ul> The Arrays class has helper methods that make simple operations quicker: <ul><li>{{c1::Arrays.equals(a, b) to compare arrays::Compare}} </li><li>{{c2::Arrays.copyOf(arr, l) that returns a new copied array of length l::Transfer values}}</li><li>{{c3::Sorting using Arrays.sort(arr)::Order}}</li><li>{{c4::toString() and deepToString()::Print}}</li></ul>

Extra Arrays.deepToString() converts a nested/multidimensional array to a readable string representation, recursively handling inner arrays.

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