Anki Deck Changes

Commit: d20632a3 - minor stuff + fixed note types

Author: lhorva <lhorva@student.ethz.ch>

Date: 2026-02-24T01:04:13+01:00

Changes: 12 note(s) changed (8 added, 4 modified, 0 deleted)

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

Deck: ETH::1. Semester::A&D
Note Type: Horvath Cloze
GUID: AY}!l[d)1z
modified

Before

Front

ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search
Name the impossible cases in DFS pre/post ordering for edge \((u, v)\):
  • Overlapping but not nested intervals: 
  • {{c2:: \(\text{pre}(u)<\text{post}(u)<\text{pre}(v)<\text{post}(v)\): As visit(u) would call visit(v) before the recursive call ends.  }}

Back

ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search
Name the impossible cases in DFS pre/post ordering for edge \((u, v)\):
  • Overlapping but not nested intervals: 
  • {{c2:: \(\text{pre}(u)<\text{post}(u)<\text{pre}(v)<\text{post}(v)\): As visit(u) would call visit(v) before the recursive call ends.  }}

After

Front

ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search
Name the impossible cases in DFS pre/post ordering for edge \((u, v)\):
  • Overlapping but not nested intervals: 
  • {{c2:: \(\text{pre}(u)<\text{pre}(v)<\text{post}(u)<\text{post}(v)\): As visit(u) would call visit(v) before the recursive call ends.  }}

Back

ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search
Name the impossible cases in DFS pre/post ordering for edge \((u, v)\):
  • Overlapping but not nested intervals: 
  • {{c2:: \(\text{pre}(u)<\text{pre}(v)<\text{post}(u)<\text{post}(v)\): As visit(u) would call visit(v) before the recursive call ends.  }}
Field-by-field Comparison
Field Before After
Text Name the impossible cases in DFS pre/post ordering for edge&nbsp;\((u, v)\):<br><ul><li>{{c1::Overlapping but not nested intervals:&nbsp;<img src="paste-b7976dbbff12de2b44594553e0c91633f59e9c05.jpg">}}</li><li>{{c2::&nbsp;\(\text{pre}(u)&lt;\text{post}(u)&lt;\text{pre}(v)&lt;\text{post}(v)\):&nbsp;As visit(u)&nbsp;would call visit(v) before the recursive call ends.&nbsp;<img src="paste-a6fc070f96de8bd2b8148e3891cf956fd611a0a2.jpg">&nbsp;}}</li></ul> Name the impossible cases in DFS pre/post ordering for edge&nbsp;\((u, v)\):<br><ul><li>{{c1::Overlapping but not nested intervals:&nbsp;<img src="paste-b7976dbbff12de2b44594553e0c91633f59e9c05.jpg">}}</li><li>{{c2::&nbsp;\(\text{pre}(u)&lt;\text{pre}(v)&lt;\text{post}(u)&lt;\text{post}(v)\):&nbsp;As visit(u)&nbsp;would call visit(v) before the recursive call ends.&nbsp;<img src="paste-a6fc070f96de8bd2b8148e3891cf956fd611a0a2.jpg">&nbsp;}}</li></ul>
Tags: ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: BRmyi3>lm%
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search PlsFix::DELETE
Runtime of
DFS

Runtime: {{c1::\( \mathcal{O}(|E| + |V|) \)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>DFS</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}(|E| + |V|) \)}}</div><div><br></div><div><b>Approach</b>: {{c2::Explore as far as possible along each branch before backtracking. Potentially keep track of pre- / post-numbers to make edge classifications.}}</div><div><br></div><div><b>Uses</b>: {{c3::Detect cycles (if backward edge), <b>topological sorting </b>(reverse post-ordering), test if bipartite, mazes, ...}}</div>
Tags: ETH::1._Semester::A&D::09._Graph_Search::1._Depth_First_Search PlsFix::DELETE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: KD23pBO,?%
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm PlsFix::DELETE
Runtime of
Johnson

Runtime: {{c1::\( \mathcal{O}(|E| \cdot |V| + |V|^2 \cdot \log|V|)\)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Johnson</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}(|E| \cdot |V| + |V|^2 \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::Idea: Make all edges positive and then perform Dijkstra  \(n\)&nbsp;times. To do this, create an additional node that is linked to each node with edge weight 0 and store for each node a height&nbsp;\(h(x)\), where&nbsp;\(h(x)\)&nbsp;is equal to the shortest path from the new node n to the node x (might be negative). The new weights are calculated with&nbsp;\(w'(u,v) = w(u,v) + h(u) - h(v)\).}}</div><div><br></div><div><b>Uses</b>: {{c3::All-to-all shortest paths in directed graphs without negative cycles.}}</div>
Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::2._Johnson's_Algorithm PlsFix::DELETE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: cKo%p6:M08
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm PlsFix::DUPLICATE
Runtime of
Prim

Runtime: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}

Approach:

Uses: Runtime: {{c1::
\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Prim</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::We start at a given vertex. To this subtree we add one-by-one the cheapest edge connecting the subtree to another component until all vertices are connected. The implementation is very similar to Dijkstra.}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}<b>Runtime</b>: {{c1::</div><div>\( \mathcal{O}((|E| + |V|) \cdot \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::We start at a given vertex. To this subtree we add one-by-one the cheapest edge connecting the subtree to another component until all vertices are connected. The implementation is very similar to Dijkstra.}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}</div>
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::2._Prim's_Algorithm PlsFix::DUPLICATE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: eGQw>urFaH
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm PlsFix::DELETE
Runtime of
Dijkstra

Runtime: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|) \)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Dijkstra</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}((|E| + |V|) \cdot \log|V|) \)}}</div><div><br></div><div><b>Approach</b>: {{c2::Put the starting node into the queue, take it out, and set the distance for all adjacent nodes and put them into the queue. Repeat (we always take cheapest vertex from the queue first, min heap), update distances and only put nodes into the queue if they weren't visited before.}}</div><div><br></div><div><b>Uses</b>: {{c3::Minimal-cost paths in non-negative weighted directed graphs}}</div>
Tags: ETH::1._Semester::A&D::10._Shortest_Paths::1._Dijkstra's_Algorithm PlsFix::DELETE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: j#w5w>dS6
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm PlsFix::DELETE
Runtime of
Bellman-Ford

Runtime: :\( \mathcal{O}(|E| \cdot |V|)\)}}

Approach: Initiate all distances with  \(\infty\) . Then go \(|V| - 1\) times through every edge, and test for all (u,v) in E if \(\text{dist}[v] > \text{dist}[u] + w(u,v)\). If yes, update the distance. If after \(|V| - 1\) iterations an edge can still be relaxed (in a last iteration), then there exists a negative cycle

Uses: Detect negative cycles, find minimal-cost paths in weighted graphs with negative weights}}
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Bellman-Ford</b></div><div style="text-align: center; "><br></div><div><b>Runtime</b>: :\( \mathcal{O}(|E| \cdot |V|)\)}}</div><div><br></div><div><b>Approach</b>: Initiate all distances with  \(\infty\) . Then go&nbsp;\(|V| - 1\)&nbsp;times through every edge, and test for all (u,v) in E if&nbsp;\(\text{dist}[v] &gt; \text{dist}[u] + w(u,v)\). If yes, update the distance. If after&nbsp;\(|V| - 1\)&nbsp;iterations an edge can still be relaxed (in a last iteration), then there exists a negative cycle</div><div><br></div><div><b>Uses</b>: Detect negative cycles, find minimal-cost paths in weighted graphs with negative weights}}</div>
Tags: ETH::1._Semester::A&D::10._Shortest_Paths::2._Bellman-Ford_Algorithm PlsFix::DELETE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: jcougdQ#0G
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm PlsFix::DUPLICATE
Runtime of
Kruskal

Runtime: {{c1::\( \mathcal{O}(|E| \log |E| + |E| \log|V|)\)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Kruskal</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}(|E| \log |E| + |E| \log|V|)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::Sort the edges by weight and add them one-by-one as long as they are in different components (which can be checked efficiently with Union Find).}}</div><div><br></div><div><b>Uses</b>: {{c3::Find MST in weighted, undirected graph}}</div>
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::3._Kruskal's_Algorithm PlsFix::DUPLICATE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: nfdJ7OmBdJ
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm PlsFix::DELETE
Runtime of
Floyd-Warshall

Runtime: {{c1::\( \mathcal{O}(|V|^3)\)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>Floyd-Warshall</b></div><div style="text-align: center; "><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}(|V|^3)\)}}</div><div><br></div><div><b>Approach</b>: {{c2::3D DP: It is based on a triple-nested <code>for</code>-loop with the following recursion:&nbsp;\(d[u][v] = \min(d[u][v], d[u][i] + d[i][v])\).}}</div><div><br></div><div><b>Uses</b>: {{c3::All-to-all shortest path in directed graph without negative cycles.}}</div>
Tags: ETH::1._Semester::A&D::12._All-Pair_Shortest_Paths::1._Floyd-Warshall_Algorithm PlsFix::DELETE

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

Deck: ETH::1. Semester::A&D
Note Type: Algorithms
GUID: u%cN;v|jjQ
added

Previous

Note did not exist

New Note

Front

Back

ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search PlsFix::DELETE
Runtime of
BFS

Runtime: {{c1::\( \mathcal{O}(|E| + |V|) \)}}

Approach:

Uses:
?


Field-by-field Comparison
Field Before After
Name <div style="text-align: center;"><b>BFS</b></div><div><br></div><div><b>Runtime</b>: {{c1::\( \mathcal{O}(|E| + |V|) \)}}</div><div><br></div><div><b>Approach</b>: {{c2::First go through all direct successors of an edge, then move to a level deeper.}}</div><div><br></div><div><b>Uses</b>: {{c3::Shortest path in unweighted graphs, cycle detection, test if graph is bipartite, path finding}}</div>
Tags: ETH::1._Semester::A&D::09._Graph_Search::2._Breadth_First_Search PlsFix::DELETE

Note 10: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Classic
GUID: DzikGL21jO
modified

Before

Front

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Ist die Menge \(A \neq \emptyset\) nach oben / unten unbeschränkt, so definieren wir infimum und supremum:

Back

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Ist die Menge \(A \neq \emptyset\) nach oben / unten unbeschränkt, so definieren wir infimum und supremum:
\(\sup(A) = \infty\) oder \(\inf(A) = -\infty\)

After

Front

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Ist die Menge \(A \neq \emptyset\) nach oben/unten unbeschränkt, so definieren wir supremum/infinum:

Back

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Ist die Menge \(A \neq \emptyset\) nach oben/unten unbeschränkt, so definieren wir supremum/infinum:
\(\sup(A) = \infty\)/\(\inf(A) = -\infty\)
Field-by-field Comparison
Field Before After
Front <div>Ist die Menge \(A \neq \emptyset\) nach oben / unten unbeschränkt, so definieren wir infimum und supremum:</div> <div>Ist die Menge \(A \neq \emptyset\) nach oben/unten unbeschränkt, so definieren wir supremum/infinum:</div>
Back \(\sup(A) = \infty\) oder \(\inf(A) = -\infty\) \(\sup(A) = \infty\)/\(\inf(A) = -\infty\)
Tags: ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen

Note 11: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: s{-]C1^cF3
modified

Before

Front

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Das minimum / maximum können nicht gleich \(\infty\) or \(-\infty\) sein, because laut Archimedischem Prinzip gibt es immer größere / kleinere natürliche Zahl.

Back

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Das minimum / maximum können nicht gleich \(\infty\) or \(-\infty\) sein, because laut Archimedischem Prinzip gibt es immer größere / kleinere natürliche Zahl.

After

Front

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Das Minimum/Maximum kann nicht  \(\infty\) oder \(-\infty\) sein, weil es laut Archimedischem Prinzip immer größere/kleinere natürliche Zahlen gibt.

Back

ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen
Das Minimum/Maximum kann nicht  \(\infty\) oder \(-\infty\) sein, weil es laut Archimedischem Prinzip immer größere/kleinere natürliche Zahlen gibt.
Field-by-field Comparison
Field Before After
Text <div>Das minimum / maximum <b>können nicht</b>&nbsp;gleich {{c1:: \(\infty\) or \(-\infty\)}} sein, because {{c1:: laut Archimedischem Prinzip gibt es immer größere / kleinere natürliche Zahl}}.</div> <div>Das Minimum/Maximum <b>kann nicht</b>&nbsp;{{c1:: \(\infty\)&nbsp;oder&nbsp;\(-\infty\)}} sein, weil {{c1::es laut Archimedischem Prinzip immer größere/kleinere natürliche Zahlen gibt}}.</div>
Tags: ETH::2._Semester::Analysis::1._Logik,_Mengen,_Zahlen::3._Zahlen

Note 12: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: Fn?QX?wZyt
modified

Before

Front

ETH::2._Semester::PProg::03._Java_Threads::1._Multitasking ETH::2._Semester::PProg::Terminology
A context switch denotes {c2::the action of {switching a computation unit from one computation to another}}. 

Back

ETH::2._Semester::PProg::03._Java_Threads::1._Multitasking ETH::2._Semester::PProg::Terminology
A context switch denotes {c2::the action of {switching a computation unit from one computation to another}}. 
Typically refers to switching between processes, but can also refer to switching between threads.

Depending on the size of the context, a context switch might be computationally expensive.

After

Front

ETH::2._Semester::PProg::03._Java_Threads::1._Multitasking ETH::2._Semester::PProg::Terminology
A context switch denotes the action of switching a computation unit from one computation to another. 

Back

ETH::2._Semester::PProg::03._Java_Threads::1._Multitasking ETH::2._Semester::PProg::Terminology
A context switch denotes the action of switching a computation unit from one computation to another. 
Typically refers to switching between processes, but can also refer to switching between threads.

Depending on the size of the context, a context switch might be computationally expensive.

Field-by-field Comparison
Field Before After
Text A {{c1::context switch}} denotes {c2::the action of {switching a computation unit from one computation to another}}.&nbsp; A {{c1::context switch}} denotes {{c2::the action of switching a computation unit from one computation to another}}.&nbsp;
Tags: ETH::2._Semester::PProg::03._Java_Threads::1._Multitasking ETH::2._Semester::PProg::Terminology
↑ Top