Anki Deck Changes

Commit: 0d864ed3 - fixed a&d card, removed unused clozes

Author: tprazak <t.prazak@gmail.com>

Date: 2026-02-23T23:17:12+01:00

Changes: 10 note(s) changed (1 added, 1 modified, 8 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{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.  }}

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{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.  }}
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{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> 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>
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%
deleted

Deleted 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:
?


Current

Note has been deleted

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,?%
deleted

Deleted 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:
?


Current

Note has been deleted

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
deleted

Deleted 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:
?


Current

Note has been deleted

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
deleted

Deleted 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:
?


Current

Note has been deleted

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
deleted

Deleted 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}}
?


Current

Note has been deleted

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
deleted

Deleted 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:
?


Current

Note has been deleted

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
deleted

Deleted 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:
?


Current

Note has been deleted

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
deleted

Deleted 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:
?


Current

Note has been deleted

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::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: g+Va^lhr7q
added

Previous

Note did not exist

New Note

Front

ETH::2._Semester::PProg::Terminology
The scheduler interrupts/pauses/sends to sleep the currently running process (or thread), performs a context switch, and selects the next process (or thread) to run.

Back

ETH::2._Semester::PProg::Terminology
The scheduler interrupts/pauses/sends to sleep the currently running process (or thread), performs a context switch, and selects the next process (or thread) to run.
Field-by-field Comparison
Field Before After
Text The scheduler {{c1::interrupts/pauses/sends to sleep the currently running process (or thread)}}, {{c2::performs a context switch}}, and {{c3::selects the next process (or thread) to run}}.
Tags: ETH::2._Semester::PProg::Terminology
↑ Top