296 lines
19 KiB
HTML
296 lines
19 KiB
HTML
<!DOCTYPE html>
|
||
|
||
<html>
|
||
<head>
|
||
<meta charset="utf-8">
|
||
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.16.10/dist/katex.min.css" integrity="sha384-wcIxkf4k558AjM3Yz3BBFQUbk/zgIYC2R0QpeeYb+TwlBVMrlgLqwRjRtGZiK7ww" crossorigin="anonymous">
|
||
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.10/dist/katex.min.js" integrity="sha384-hIoBPJpTUs74ddyc4bFZSM1TVlQDA60VBbJS0oA934VSz82sBx1X7kSx2ATBDIyd" crossorigin="anonymous"></script>
|
||
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.10/dist/contrib/auto-render.min.js" integrity="sha384-43gviWU0YVjaDtb/GhzOouOXtZMP/7XUzwPTstBeZFe/+rCMvRwr4yROQP43s0Xk" crossorigin="anonymous" onload="renderMathInElement(document.body);"></script>
|
||
<script>
|
||
document.addEventListener("DOMContentLoaded", function() {
|
||
renderMathInElement(document.body, {
|
||
delimiters: [
|
||
{left: "$$", right: "$$", display: true},
|
||
{left: "$", right: "$", display: false},
|
||
{left: "\\(", right: "\\)", display: false},
|
||
{left: "\\begin{equation}", right: "\\end{equation}", display: true},
|
||
{left: "\\begin{align}", right: "\\end{align}", display: true},
|
||
{left: "\\begin{alignat}", right: "\\end{alignat}", display: true},
|
||
{left: "\\begin{gather}", right: "\\end{gather}", display: true},
|
||
{left: "\\begin{CD}", right: "\\end{CD}", display: true},
|
||
{left: "\\[", right: "\\]", display: true}
|
||
],
|
||
throwOnError : false
|
||
});
|
||
});
|
||
</script>
|
||
<title>Practice Exam</title>
|
||
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
|
||
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
|
||
<style>
|
||
body {
|
||
margin-left: 20%;
|
||
margin-right: 20%;
|
||
}
|
||
|
||
summary {
|
||
font-weight: bold;
|
||
}
|
||
|
||
@media screen and (max-width:1000px) {
|
||
body {
|
||
margin-left: 5%;
|
||
margin-right: 5%;
|
||
}
|
||
}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<h1>Practice Exam</h1>
|
||
<h2>15.3-6</h2>
|
||
<p>Imagine that you wish to exchange one currency for another. You realize that instead of directly exchanging one currency for another, you might be better off making a series of trades through other currencies, winding up with the currency you want. Suppose that you can trade $n$ different currencies, numbered $1, 2, \ldots, n$, where you start with currency $1$ and wish to wind up with currency $n$. You are given, for each pair of currencies $i$ and $j$ , an exchange rate $r_{ij}$, meaning that if you start with $d$ units of currency $i$ , you can trade for $dr_{ij}$ units of currency $j$. A sequence of trades may entail a commission, which depends on the number of trades you make. Let $c_k$ be the commission that you are charged when you make $k$ trades. Show that, if $c_k = 0$ for all $k = 1, 2, \ldots, n$, then the problem of finding the best sequence of exchanges from currency $1$ to currency $n$ exhibits optimal substructure. Then show that if commissions $c_k$ are arbitrary values, then the problem of finding the best sequence of exchanges from currency $1$ to currency $n$ does not necessarily exhibit optimal substructure.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>First we assume that the commission is always zero. Let $k$ denote a currency which appears in an optimal sequence $s$ of trades to go from currency $1$ to currency $n$. $p_k$ denote the first part of this sequence which changes currencies from $1$ to $k$ and $q_k$ denote the rest of the sequence. Then $p_k$ and $q_k$ are both optimal sequences for changing from $1$ to $k$ and $k$ to $n$ respectively. To see this, suppose that $p_k$ wasn't optimal but that $p_k'$ was. Then by changing currencies according to the sequence $p_k'q_k$ we would have a sequence of changes which is better than $s$, a contradiction since $s$ was optimal. The same argument applies to $q_k$.</p>
|
||
<p>Now suppose that the commissions can take on arbitrary values. Suppose we have currencies $1$ through $6$, and $r_{12} = r_{23} = r_{34} = r_{45} = 2$, $r_{13} = r_{35} = 6$, and all other exchanges are such that $r_{ij} = 100$. Let $c_1 = 0$, $c_2 = 1$, and $c_k = 10$ for $k \ge 3$.</p>
|
||
<p>The optimal solution in this setup is to change $1$ to $3$, then $3$ to $5$, for a total cost of $13$. An optimal solution for changing $1$ to $3$ involves changing $1$ to $2$ then $2$ to $3$, for a cost of $5$, and an optimal solution for changing $3$ to $5$ is to change $3$ to $4$ then $4$ to $5$, for a total cost of $5$. However, combining these optimal solutions to subproblems means making more exchanges overall, and the total cost of combining them is $18$, which is not optimal.</p>
|
||
</details>
|
||
<h2>12.2-3</h2>
|
||
<p>Write the $\text{TREE-PREDECESSOR}$ procedure.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<pre lang="cpp"><code>TREE-PREDECESSOR(x)
|
||
if x.left != NIL
|
||
return TREE-MAXIMUM(x.left)
|
||
y = x.p
|
||
while y != NIL and x == y.left
|
||
x = y
|
||
y = y.p
|
||
return y
|
||
</code></pre>
|
||
</details>
|
||
<h2>4.3-7</h2>
|
||
<p>Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 3) + n$ is $T(n) = \Theta(n^{\log_3 4})$. Show that a substitution proof with the assumption $T(n) \le cn^{\log_3 4}$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>We guess $T(n) \le cn^{\log_3 4}$ first,</p>
|
||
<p>$$
|
||
\begin{aligned}
|
||
T(n) & \le 4c(n / 3)^{\log_3 4} + n \\
|
||
& = cn^{\log_3 4} + n.
|
||
\end{aligned}
|
||
$$</p>
|
||
<p>We stuck here.</p>
|
||
<p>We guess $T(n) \le cn^{\log_3 4} - dn$ again,</p>
|
||
<p>$$
|
||
\begin{aligned}
|
||
T(n) & \le 4(c(n / 3)^{\log_3 4} - dn / 3) + n \\
|
||
& = 4(cn^{\log_3 4} / 4 - dn / 3) + n \\
|
||
& = cn^{\log_3 4} - \frac{4}{3}dn + n \\
|
||
& \le cn^{\log_3 4} - dn,
|
||
\end{aligned}
|
||
$$</p>
|
||
<p>where the last step holds for $d \ge 3$.</p>
|
||
</details>
|
||
<h2>16.2-1</h2>
|
||
<p>Prove that the fractional knapsack problem has the greedy-choice property.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Let $I$ be the following instance of the knapsack problem: Let $n$ be the number of items, let $v_i$ be the value of the $i$th item, let $w_i$ be the weight of the $i$th item and let $W$ be the capacity. Assume the items have been ordered in increasing order by $v_i / w_i$ and that $W \ge w_n$.</p>
|
||
<p>Let $s = (s_1, s_2, \ldots, s_n)$ be a solution. The greedy algorithm works by assigning $s_n = \min(w_n, W)$, and then continuing by solving the subproblem</p>
|
||
<p>$$I' = (n - 1, \{v_1, v_2, \ldots, v_{n - 1}\}, \{w_1, w_2, \ldots, w_{n - 1}\}, W - w_n)$$</p>
|
||
<p>until it either reaches the state $W = 0$ or $n = 0$.</p>
|
||
<p>We need to show that this strategy always gives an optimal solution. We prove this by contradiction. Suppose the optimal solution to $I$ is $s_1, s_2, \ldots, s_n$, where $s_n < \min(w_n, W)$. Let $i$ be the smallest number such that $s_i > 0$. By decreasing $s_i$ to $\max(0, W - w_n)$ and increasing $s_n$ by the same amount, we get a better solution. Since this a contradiction the assumption must be false. Hence the problem has the greedy-choice property.</p>
|
||
</details>
|
||
<h2>7.3-2</h2>
|
||
<p>When $\text{RANDOMIZED-QUICKSORT}$ runs, how many calls are made to the random number generator $\text{RANDOM}$ in the worst case? How about in the best case? Give your answer in terms of $\Theta$-notation.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>In the worst case, the number of calls to $\text{RANDOM}$ is</p>
|
||
<p>$$T(n) = T(n - 1) + 1 = n = \Theta(n).$$</p>
|
||
<p>As for the best case,</p>
|
||
<p>$$T(n) = 2T(n / 2) + 1 = \Theta(n).$$</p>
|
||
<p>This is not too surprising, because each third element (at least) gets picked as pivot.</p>
|
||
</details>
|
||
<h2>34.2-3</h2>
|
||
<p>Show that if $\text{HAM-CYCLE} \in P$, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>4.4-2</h2>
|
||
<p>Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n / 2) + n^2$. Use the substitution method to verify your answer.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<ul>
|
||
<li>
|
||
<p>The subproblem size for a node at depth $i$ is $n / 2^i$.</p>
|
||
<p>Thus, the tree has $\lg n + 1$ levels and $1^{\lg n} = 1$ leaf.</p>
|
||
<p>The total cost over all nodes at depth $i$, for $i = 0, 1, 2, \ldots, \lg{n - 1}$, is $1^i (n / 2^i)^2 = (1 / 4)^i n^2$.</p>
|
||
<p>$$
|
||
\begin{aligned}
|
||
T(n) & = \sum_{i = 0}^{\lg n - 1} \Big(\frac{1}{4}\Big)^i n^2 + \Theta(1) \\
|
||
& < \sum_{i = 0}^\infty \Big(\frac{1}{4}\Big)^i n^2 + \Theta(1) \\
|
||
& = \frac{1}{1 - (1 / 4)} n^2 + \Theta(1) \\
|
||
& = \Theta(n^2).
|
||
\end{aligned}
|
||
$$</p>
|
||
</li>
|
||
<li>
|
||
<p>We guess $T(n) \le cn^2$,</p>
|
||
<p>$$
|
||
\begin{aligned}
|
||
T(n) & \le c(n / 2)^2 + n^2 \\
|
||
& = cn^2 / 4 + n^2 \\
|
||
& = (c / 4 + 1)n^2 \\
|
||
& \le cn^2,
|
||
\end{aligned}
|
||
$$</p>
|
||
<p>where the last step holds for $c \ge 4 / 3$.</p>
|
||
</li>
|
||
</ul>
|
||
</details>
|
||
<h2>26.3-3</h2>
|
||
<p>Let $G = (V, E)$ be a bipartite graph with vertex partition $V = L \cup R$, and let $G'$ be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in $G'$ during the execution of $\text{FORD-FULKERSON}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Removed)</p>
|
||
</details>
|
||
<h2>15.1-3</h2>
|
||
<p>Consider a modification of the rod-cutting problem in which, in addition to a price $p_i$ for each rod, each cut incurs a fixed cost of $c$. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>We can modify $\text{BOTTOM-UP-CUT-ROD}$ algorithm from section 15.1 as follows:</p>
|
||
<pre lang="cpp"><code>MODIFIED-CUT-ROD(p, n, c)
|
||
let r[0..n] be a new array
|
||
r[0] = 0
|
||
for j = 1 to n
|
||
q = p[j]
|
||
for i = 1 to j - 1
|
||
q = max(q, p[i] + r[j - i] - c)
|
||
r[j] = q
|
||
return r[n]
|
||
</code></pre>
|
||
<p>We need to account for cost $c$ on every iteration of the loop in lines 5-6 but the last one, when $i = j$ (no cuts).</p>
|
||
<p>We make the loop run to $j - 1$ instead of $j$, make sure $c$ is subtracted from the candidate revenue in line 6, then pick the greater of current best revenue $q$ and $p[j]$ (no cuts) in line 7.</p>
|
||
</details>
|
||
<h2>4.6-3 *</h2>
|
||
<p>Show that case 3 of the master method is overstated, in the sense that the regularity condition $af(n / b) \le cf(n)$ for some constant $c < 1$ implies that there exists a constant $\epsilon > 0$ such that $f(n) = \Omega(n^{\log_b a + \epsilon})$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>$$
|
||
\begin{aligned}
|
||
af(n / b) & \le cf(n) \\
|
||
\Rightarrow f(n / b) & \le \frac{c}{a} f(n) \\
|
||
\Rightarrow f(n) & \le \frac{c}{a} f(bn) \\
|
||
& = \frac{c}{a} \left(\frac{c}{a} f(b^2n)\right) \\
|
||
& = \frac{c}{a} \left(\frac{c}{a}\left(\frac{c}{a} f(b^3n)\right)\right) \\
|
||
& = \left(\frac{c}{a}\right)^i f(b^i n) \\
|
||
\Rightarrow f(b^i n) & \ge \left(\frac{a}{c}\right)^i f(n).
|
||
\end{aligned}
|
||
$$</p>
|
||
<p>Let $n = 1$, then we have</p>
|
||
<p>$$f(b^i) \ge \left(\frac{a}{c}\right)^i f(1) \quad (*).$$</p>
|
||
<p>Let $b^i = n \Rightarrow i = \log_b n$, then substitue back to equation $(*)$,</p>
|
||
<p>$$
|
||
\begin{aligned}
|
||
f(n) & \ge \left(\frac{a}{c}\right)^{\log_b n} f(1) \\
|
||
& \ge n^{\log_b \frac{a}{c}} f(1) \\
|
||
& \ge n^{\log_b a + \epsilon} & \text{ where $\epsilon > 0$ because $\frac{a}{c} > a$ (recall that $c < 1$)} \\
|
||
& = \Omega(n^{\log_b a + \epsilon}).
|
||
\end{aligned}
|
||
$$</p>
|
||
</details>
|
||
<h2>16.4-2 *</h2>
|
||
<p>Given an $m \times n$ matrix $T$ over some field (such as the reals), show that $(S, \mathcal I)$ is a matroid, where $S$ is the set of columns of $T$ and $A \in \mathcal I$ if and only if the columns in $A$ are linearly independent.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Let $c_1, \dots, c_m$ be the columns of $T$. Suppose $C = \{c_{i1}, \dots, c_{ik}\}$ is dependent. Then there exist scalars $d_1, \dots, d_k$ not all zero such that $\sum_{j = 1}^k d_jc_{ij} = 0$. By adding columns to $C$ and assigning them to have coefficient $0$ in the sum, we see that any superset of $C$ is also dependent. By contrapositive, any subset of an independent set must be independent.</p>
|
||
<p>Now suppose that $A$ and $B$ are two independent sets of columns with $|A| > |B|$. If we couldn't add any column of $A$ to be whilst preserving independence then it must be the case that every element of $A$ is a linear combination of elements of $B$. But this implies that $B$ spans a $|A|$-dimensional space, which is impossible. Therefore, our independence system must satisfy the exchange property, so it is in fact a matroid.</p>
|
||
</details>
|
||
<h2>34.4-5</h2>
|
||
<p>Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>22.3-10</h2>
|
||
<p>Modify the pseudocode for depth-first search so that it prints out every edge in the directed graph $G$, together with its type. Show what modifications, if any, you need to make if $G$ is undirected.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>If $G$ is undirected we don't need to make any modifications.</p>
|
||
<p>See the <a href="https://github.com/walkccc/CLRS-cpp/blob/master/Chap22/22.3-10/22.3-10.cpp">C++ demo</a>.</p>
|
||
<pre lang="cpp"><code>DFS-VISIT-PRINT(G, u)
|
||
time = time + 1
|
||
u.d = time
|
||
u.color = GRAY
|
||
for each vertex v ∈ G.Adj[u]
|
||
if v.color == WHITE
|
||
print "(u, v) is a tree edge."
|
||
v.π = u
|
||
DFS-VISIT-PRINT(G, v)
|
||
else if v.color == GRAY
|
||
print "(u, v) is a back edge."
|
||
else if v.d > u.d
|
||
print "(u, v) is a forward edge."
|
||
else
|
||
print "(u, v) is a cross edge."
|
||
u.color = BLACK
|
||
time = time + 1
|
||
u.f = time
|
||
</code></pre>
|
||
</details>
|
||
<h2>24.5-5</h2>
|
||
<p>Let $G = (V, E)$ be a weighted, directed graph with no negative-weight edges. Let $s \in V$ be the source vertex, and suppose that we allow $v.\pi$ to be the predecessor of $v$ on <em>any</em> shortest path to $v$ from source $s$ if $v \in V - \{s\}$ is reachable from $s$, and $\text{NIL}$ otherwise. Give an example of such a graph $G$ and an assignment of $\pi$ values that produces a cycle in $G_\pi$. (By Lemma 24.16, such an assignment cannot be produced by a sequence of relaxation steps.)</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Suppose that we have a grap hon three vertices $\{s, u, v\}$ and containing edges $(s, u), (s, v), (u, v), (v, u)$ all with weight $0$. Then, there is a shortest path from $s$ to $v$ of $s$, $u$, $v$ and a shortest path from $s$ to $u$ of $s$ $v$, $u$. Based off of these, we could set $v.\pi = u$ and $u.\pi = v$. This then means that there is a cycle consisting of $u, v$ in $G_\pi$.</p>
|
||
</details>
|
||
<h2>34.5-7</h2>
|
||
<p>The <strong><em>longest-simple-cycle problem</em></strong> is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is $\text{NP-complete}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>22.5-2</h2>
|
||
<p>Show how the procedure $\text{STRONGLY-CONNECTED-COMPONENTS}$ works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5–7 of $\text{DFS}$ considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>The finishing times of each vertex were computed in exercise 22.3-2. The forest consists of 5 trees, each of which is a chain. We'll list the vertices of each tree in order from root to leaf: $r$, $u$, $q - y - t$, $x - z$, and $s - w - v$.</p>
|
||
</details>
|
||
<h2>26.4-4</h2>
|
||
<p>Suppose that we have found a maximum flow in a flow network $G = (V, E)$ using a push-relabel algorithm. Give a fast algorithm to find a minimum cut in $G$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Removed)</p>
|
||
</details>
|
||
<h2>26.2-1</h2>
|
||
<p>Prove that the summations in equation $\text{(26.6)}$ equal the summations in equation $\text{(26.7)}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Removed)</p>
|
||
</details>
|
||
<h2>12.2-7</h2>
|
||
<p>An alternative method of performing an inorder tree walk of an $n$-node binary search tree finds the minimum element in the tree by calling $\text{TREE-MINIMUM}$ and then making $n - 1$ calls to $\text{TREE-SUCCESSOR}$. Prove that this algorithm runs in $\Theta(n)$ time.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>To show this bound on the runtime, we will show that using this procedure, we traverse each edge twice. This will suffice because the number of edges in a tree is one less than the number of vertices.</p>
|
||
<p>Consider a vertex of a BST, say $x$. Then, we have that the edge between $x.p$ and $x$ gets used when successor is called on $x.p$ and gets used again when it is called on the largest element in the subtree rooted at $x$. Since these are the only two times that that edge can be used, apart from the initial finding of tree minimum. We have that the runtime is $O(n)$. We trivially get the runtime is $\Omega(n)$ because that is the size of the output.</p>
|
||
</details>
|
||
<h2>16.2-7</h2>
|
||
<p>Suppose you are given two sets $A$ and $B$, each containing $n$ positive integers. You can choose to reorder each set however you like. After reordering, let $a_i$ be the $i$th element of set $A$, and let $b_i$ be the $i$th element of set $B$. You then receive a payoff of $\prod_{i = 1}^n a_i^{b_i}$. Give an algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Since an idential permutation of both sets doesn't affect this product, suppose that $A$ is sorted in ascending order. Then, we will prove that the product is maximized when $B$ is also sorted in ascending order. To see this, suppose not, that is, there is some $i < j$ so that $a_i < a_j$ and $b_i > b_j$. Then, consider only the contribution to the product from the indices $i$ and $j$. That is, $a_i^{b_i}a_j^{b_j}$, then, if we were to swap the order of $b_i$ and $b_j$, we would have that contribution be $a_i^{b_j}a_j^{b_i}$. we can see that this is larger than the previous expression because it differs by a factor of $\left(\frac{a_j}{a_i}\right)^{b_i - b_j}$ which is bigger than one. So, we couldn't of maximized the product with this ordering on $B$.</p>
|
||
</details>
|
||
|
||
|
||
<footer>
|
||
<hr>
|
||
<p>
|
||
built by nat, from questions written by Michelle Bodnar and Andrew Lohr (CLRS 3rd Edition), the solutions to which were prepared and organized by <a href="https://pengyuc.com/">Peng-Yu Chen</a> and <a href="https://github.com/walkccc/CLRS/graphs/contributors">contributors to walkccc/CLRS on GitHub</a>.
|
||
</p>
|
||
</footer>
|
||
</body>
|
||
</html>
|