The ADT Dictionary implements the following methods:
search(x, W) returns the position of the key x in memory
insert(x, W) Insert the key x into W, as long as it’s not saved there yet
delete(x, W) find and delete the key x from W
Field-by-field Comparison
Field
Before
After
Text
The ADT Dictionary implements the following methods:<br><ul><li>{{c1::<b>search(x, W)</b> returns the position of the key x in memory}}</li><li>{{c2::<b>insert(x, W)</b> Insert the key <b>x</b> into <b>W</b>, as long as it’s not saved there yet}}<br></li><li>{{c3::<b>delete(x, W)</b> find and delete the key <b>x</b> from <b>W</b>}}<br></li></ul>
We can use a binary search tree to implement the dictionary. The tree-condition is for every node, all keys in the left child are smaller than those in the right child.
We can use a binary search tree to implement the dictionary. The tree-condition is for every node, all keys in the left child are smaller than those in the right child.
Field-by-field Comparison
Field
Before
After
Text
We can use a binary search tree to implement the dictionary. The tree-condition is {{c1::for every node, all keys in the left child are smaller than those in the right child}}.
Binary trees are not balanced possible that \(h >> \log_2 n\) Worst case example if inserted in ascending order:
Field-by-field Comparison
Field
Before
After
Front
<b>Worst case</b> for <b>search</b> in a <b>binary tree</b>?
Back
Binary trees are not <b>balanced</b> possible that \(h >> \log_2 n\)<br>Worst case example if inserted in ascending order:<br><b></b><img src="paste-201c49e27928e7a814e89e8de667e07e5c7789ce.jpg">
Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
Insert the new key value as a separator
Rebalance (if necessary, i.e. more than 3 keys)
split node into two nodes (each gets 2 children and 1 seps)
the middle sep is pushed to the parent level (and propagate)
The rebalancing being recursively pushed to the parent limits the operations at the height \(h\) thus we get \(O(\log n)\).
Field-by-field Comparison
Field
Before
After
Text
<b>2-3 Tree</b>: Inserting Steps:<br><ol><li>{{c1::Search for the correct node under which the key is inserted: \(O(\log_2 n)\)}}</li><li>{{c2::Insert the new key value as a <b>separator</b>}}</li><li>{{c3::<b>Rebalance</b> (if necessary, i.e. more than 3 keys)<br></li></ol><ul><li>split node into two nodes (each gets 2 children and 1 seps)</li><li>the middle sep is pushed to the parent level (and propagate)}}</li></ul>
Extra
The rebalancing being recursively pushed to the parent limits the operations at the height \(h\) thus we get \(O(\log n)\).
Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
Remove the leaf with the value and one separator
Rebalance (if necessary, i.e. now 1 key)
Field-by-field Comparison
Field
Before
After
Text
<b>2-3 Tree</b>: Deleting Steps:<br><ol><li>{{c1::Search for the correct node under which the key is inserted: \(O(\log_2 n)\)}}</li><li>{{c2::Remove the leaf with the value and one separator}}</li><li>{{c3::<b>Rebalance</b> (if necessary, i.e. now 1 key)}}</li></ol>
Our current node adopts one of the children. The separators have to be updated (one is given with the adopted child)
Field-by-field Comparison
Field
Before
After
Front
<b>2-3 Tree</b>: Deleting Steps if neighbour has 3 keys:
Back
Our current node adopts one of the children. The separators have to be updated (one is given with the adopted child)<br><img src="paste-bd8f4c10d3d0aaa08619b4e358673f9ff6b134a0.jpg">
the nodes \(u\) and \(v\) are merged to form one new node with 3 children.
The separator from the parent node is pulled down to be the new \(s_2\).
Parent may lose child -> rebalance there (can go up to the root). If root has 1 child -> root replaced by child.
Field-by-field Comparison
Field
Before
After
Front
2-3 Tree: Deleting Steps if neighbour has 2 keys:
Back
<ol><li>the nodes \(u\) and \(v\) are <b>merged</b> to form one new node with <b>3 children</b>.</li><li>The separator from the parent node is pulled down to be the new \(s_2\).</li></ol>Parent may lose child -> rebalance there (can go up to the root).<br>If root has 1 child -> root replaced by child.<br><img src="paste-fcffee6f619138677fc86eb74beebfaa266c8cfe.jpg">
Steps of giving a DP solution:<br><ol><li>{{c1::Define the DP table (dimensions, index, range; meaning of entry): ex: <b>DP[1..n+1][1..k+1]</b>}}</li><li>{{c2::Computation of Entry (Base Case, recursive formula, pay attention to bounds!)}}</li><li>{{c3::Calculation Order (what depends on what entries, what variable incremented first)}}</li><li>{{c4::Extract Solution (How to get final solution out)}}</li><li>{{c5::Running time proof}}</li></ol>
Differences between Subarray vs. Subsequence vs. Subset:
subarray: continous partition of the original
subsequence: non-continous partition
subset any subset (order does not matter)
Back
ETH::1._Semester::A&D::06._Dynamic_Programming
Differences between Subarray vs. Subsequence vs. Subset:
subarray: continous partition of the original
subsequence: non-continous partition
subset any subset (order does not matter)
Field-by-field Comparison
Field
Before
After
Text
Differences between Subarray vs. Subsequence vs. Subset:<br><ul><li><b>subarray</b>: {{c1:: continous partition of the original}}</li><li><b>subsequence</b>: {{c2:: non-continous partition}}</li><li><b>subset</b> {{c3:: any subset (order does not matter)}}</li></ul>
Table: DP[1..n]<br>Define the "randmax": \( R_j := \max_{1 \leq i \leq j} \sum_{k = i}^j A[k] \) (maximale summe eines teilarrays das an j endet.<br><ul><li>Base Case: \(R_1 = A[1]\)</li><li>Recursion is \(R_j = \max \{ A[j], R_{j - 1} + A[j]
\}\)<br>Thus either our current subarray contains the element at j, or not and we start with it again.</li></ul>
Minimal jumps to get from beginning of array to the end.<br><br>Variable switch: cells which we can reach in \(k\) jumps. Solution is smallest \(k\) for which \(M[k] \geq n\).<br><br>We look at all \(i\) we can reach with exactly \(k-1\) jumps:<br><ul><li>Base Case: \(M[0] = A[0]\), \(M[1] = A[1] + 1\)</li><li>Recursion: \( M[k] = \max \{i + A[i] \ | \ M[k - 2] \leq i \leq M[k - 1]\} \)</li></ul><div>We look exactly 1 at every \(i\), thus \(O(n)\)</div>
<div>DP-Table: <code>DP[0..n][0..m]</code> for \(n, m\) lengths of the strings</div><div><br></div><div><div>longest common subsequence that two strings share. For example TIGER and ZIEGE share IGE as a LGT.</div></div><div><br></div><div>
<div>This gives us the following recursion: \[L(i,j) = \begin{cases} 0, & i = 0 \text{ oder } j = 0 \\ L(i-1, j-1) + 1, & X_i = Y_j \\ \max(L(i-1,j), L(i,j-1)), & X_i \neq Y_j \end{cases}\]</div></div>
Backtracking can find the solution of the problem from the DP table. From the recursion and it's behaviour we find the "path"
Field-by-field Comparison
Field
Before
After
Front
Backtracking in DP Problems
Back
Backtracking can find the solution of the problem from the DP table. From the recursion and it's behaviour we find the "path"<br><br><img src="paste-c186a33203c3cb874cfeb7870ee1a4c5d52bf205.jpg">
Minimum amount of edits (insert, delete, replace) to go from s1 to s2 -> LGT gives us the ED.<br><br>Three cases for \(a_i\) last char of \(a\):<br><ul><li>deleted: \(ED(i, j) = 1 + ED(i - 1, j)\) (if deleted, it doesn't matter when)<br><img src="paste-254e45a17676954472f6aebe7c8c4f0517b3d6b5.jpg"></li><li>ends up in \(1, \dots, j-1\): no char \(a_k, k < i\) can be behind \(a_i\) (suboptimal as it would cost 2): \(E1+ ED(i, j -1)\)<br><img src="paste-fae70ea53a12531dc9ac1ac30b00512b6f0c150e.jpg"></li><li>ends up at \(b_j\): cannot insert char behind \(a_i\) thus: \(ED(i-1, j -1) \) if \(a_i = b_j\) else \(1 + ED(i-1, k-1)\) <br><img src="paste-3027dc66600e0cb2f8e3a1b12c8a1be248f13f5c.jpg"> </li></ul>
We want to find the subset \(I \subseteq \{1, \dots, n\}\) such that \(\sum_{i \in I} A[i] = b\) (must not exist for all \(b\)).<br><br>\(T(i,s)\) is 1 if there exists a subset from 1 to i that sums to s<br><ul><li>Base Case: T(0, 0) = 1 as we can use </li><li>Recursion: \( T(i, s) = T(i - 1, s) \ \lor \ T(i - 1, s - A[i]) \)</li></ul><div>Either we use A[i] or we don't.</div>
Subset problem choosing the maximum staying under a weight \(W\).<br>The greedy algorithm fails as a local optimum is not global here.<br><br>Base Cases: \(dp[0][w] = 0, \quad dp[i][0] = 0\)<br>If item weight > max allowed left, don't take it. Otherwise get the max from using it or not:<br>\(dp[i][w] = \begin{cases} dp[i-1][w], & w_i > w \\ \max(dp[i-1][w], dp[i-1][w-w_i] + v_i), & \text{sonst} \end{cases}\)
runtime dependent on a number \(W\) (like in knapsack) which is not correlated polynomially to input length but exponentially.
The DP-table get's 10x for \(W = 10 \rightarrow 100\) but the input size (binary) only grows from \(\log_2(10) \approx 3 \rightarrow \approx 6\) so x2.
Field-by-field Comparison
Field
Before
After
Front
What is pseudo-polynomial time?
Back
runtime dependent on a number \(W\) (like in knapsack) which is not correlated polynomially to input length but exponentially.<br><br>The DP-table get's 10x for \(W = 10 \rightarrow 100\) but the input size (binary) only grows from \(\log_2(10) \approx 3 \rightarrow \approx 6\) so x2.
How can we make Knapsack polynomial using approximation?
round the profits and solve the Knapsack problem for these rounded profits:\(\overline{p_i} := K \cdot \lfloor \frac{p_i}{K} \rfloor\). We then only have to compute every K'th entry to the DP-table.
Field-by-field Comparison
Field
Before
After
Front
How can we make Knapsack polynomial using approximation?
Back
round the profits and solve the Knapsack problem for these rounded profits:\(\overline{p_i} := K \cdot \lfloor \frac{p_i}{K} \rfloor\). We then only have to compute every K'th entry to the DP-table.
For an array A[1..n] <b>longest</b> subsequence (non-continuous) that is ascending.<br><br>DP Table with entry \(M(l) = a\) where a ist the smallest possible ending of a LAT with length \(l\).<br><ul><li>Base Cases: \(M[*] = \infty\)</li><li>Recursion: set \(M[k]\) to \(A[i]\) where \(k\) is the index of the next smallest + 1 in \(M\).</li></ul>We can find the smaller with binary search, thus \(\log n \) search for \(n\) elements -> \(\Theta(n \log n)\).<br><img src="paste-1b9069bf0a881a3cd3900a4de699cac89f0498b8.jpg"><br>
\(O(n+m)\)
In an Adjacency Matrix: runtime is \(O(n^2)\) as looping over all edges is \(O(n)\).
In an Adjacency List: we loop \(n\) times over \(O(1 + \deg(u))\). Using the handshake lemma: \(\sum_{u \in V} (1 + \deg(u)) = n + \sum_{u \in V} \deg(u) = n + 2m\)
Field-by-field Comparison
Field
Before
After
Name
Find Closed Eulerian Path
Runtime
\(O(n+m)\)
Approach
We want to be able to find closed walks in a graph. We can then merge them together to form a single closed walk, by exploiting shared vertices.<br><br>Algo:<br><ol><li>Start at vertex \(u_0\) arbitrary</li><li>For loop over edges. If not marked, mark and recurse.</li><li>Append vertex to list after execution</li></ol> Returns a list of vertices in order of a closed walk if there is one.<br><br>Example:<br><img src="paste-a669de30c7bc4a38d788fb96b6b5551a4781ec71.jpg"><br>Output:<br><img src="paste-b453826818903aa4da2ac10897e9dc0e177229b6.jpg">
In an Adjacency Matrix: runtime is \(O(n^2)\) as looping over all edges is \(O(n)\).<br><br>In an Adjacency List: we loop \(n\) times over \(O(1 + \deg(u))\).<br>Using the handshake lemma: \(\sum_{u \in V} (1 + \deg(u)) = n + \sum_{u \in V} \deg(u) = n + 2m\)
Explore as far as possible along each branch before backtracking. Potentially keep track of pre- / post-numbers to make edge classifications.<br><br>We want to find a sink, add it to the list, then backtrack and find the next one.<br><br>The reversed post-order then gives us a toposort.<br><br>Example output:<br><img src="paste-f6163ccea9c72dbfdc9cb9045b600a5a41b8aa6b.jpg">
Pre-/Post-Ordering Classification for an edge \((u, v)\): \(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\): tree edge, as \(v\) is a descendant of \(u\)
Pre-/Post-Ordering Classification for an edge \((u, v)\): \(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\): tree edge, as \(v\) is a descendant of \(u\)
Field-by-field Comparison
Field
Before
After
Text
Pre-/Post-Ordering Classification for an edge \((u, v)\):<br>\(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\): {{c1:: tree edge, as \(v\) is a descendant of \(u\)}}
Pre-/Post-Ordering Classification for an edge \((u, v)\): \(\text{pre}(v) < \text{pre}(u) < \text{post}(u) < \text{post}(v)\): back edge
exists a cycle!
Field-by-field Comparison
Field
Before
After
Text
Pre-/Post-Ordering Classification for an edge \((u, v)\):<br>\(\text{pre}(v) < \text{pre}(u) < \text{post}(u) < \text{post}(v)\): {{c1:: back edge}}
Pre-/Post-Ordering Classification for an edge \((u, v)\): \(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\), but not tree edge: Forward edge
Pre-/Post-Ordering Classification for an edge \((u, v)\): \(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\), but not tree edge: Forward edge
Field-by-field Comparison
Field
Before
After
Text
Pre-/Post-Ordering Classification for an edge \((u, v)\):<br>\(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\), but <b>not tree edge</b>: {{c1:: Forward edge}}
In an undirected graph, what is special about pre/post-ordering:
back-edges = forward-edges
cross edges are not possible
Back
In an undirected graph, what is special about pre/post-ordering:
back-edges = forward-edges
cross edges are not possible
Field-by-field Comparison
Field
Before
After
Text
In an undirected graph, what is special about pre/post-ordering:<br><ul><li><div>{{c2::back-edges = forward-edges}}</div></li><li><div><div>cross edges {{c1::are not possible}}</div></div></li></ul>
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 \((u, v)\):<br><ul><li>{{c1::Overlapping but not Nested Intervals: <img src="paste-b7976dbbff12de2b44594553e0c91633f59e9c05.jpg">}}</li><li>{{c2:: \(\text{pre}(u)<\text{pre}(v)<\text{post}(u)<\text{post}(v)\): <img src="paste-a6fc070f96de8bd2b8148e3891cf956fd611a0a2.jpg"> as visit(u) would call visit(v) before the recursive call ends}}</li></ul>
During the recursive call, if we find an adjacent vertex without a post-number, there's a back-edge (\(\implies\)the recursive call for that edge is still active...)
Field-by-field Comparison
Field
Before
After
Front
Check for cycles in DFS algo:
Back
During the recursive call, if we find an adjacent vertex <b>without a post-number</b>, there's a back-edge (\(\implies\)the recursive call for that edge is still active...)
DFS Runtime: In a sparse graph adjacency list better, in a dense graph adjacency matrix is better.
\(|E| \geq |V|^2 / 10\), then DFS has the same runtime in the worst-case using adjacency matrices or lists as \(|V| + |E| \leq |V| + |V|^2 \)which is \(O(n^2)\).
Field-by-field Comparison
Field
Before
After
Text
DFS Runtime: In a sparse graph {{c1:: adjacency list better}}, in a dense graph {{c1:: adjacency matrix is better}}.
Extra
\(|E| \geq |V|^2 / 10\), then DFS has the same runtime in the worst-case using adjacency matrices or lists as \(|V| + |E| \leq |V| + |V|^2 \)which is \(O(n^2)\).
as visit(u) would call visit(v) before the recursive call ends}}