291 lines
19 KiB
HTML
291 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>24.4-5</h2>
|
||
<p>Show how to modify the Bellman-Ford algorithm slightly so that when we use it to solve a system of difference constraints with $m$ inequalities on $n$ unknowns, the running time is $O(nm)$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>We can follow the advice of problem 14.4-7 and solve the system of constraints on a modified constraint graph in which there is no new vertex $v_0$. This is simply done by initializing all of the vertices to have a $d$ value of $0$ before running the iterated relaxations of Bellman Ford. Since we don't add a new vertex and the $n$ edges going from it to to vertex corresponding to each variable, we are just running Bellman Ford on a graph with $n$ vertices and $m$ edges, and so it will have a runtime of $O(mn)$.</p>
|
||
</details>
|
||
<h2>34.2-11</h2>
|
||
<p>Let $G$ be a connected, undirected graph with at least $3$ vertices, and let $G^3$ be the graph obtained by connecting all pairs of vertices that are connected by a path in $G$ of length at most $3$. Prove that $G^3$ is hamiltonian. ($\textit{Hint:}$ Construct a spanning tree for $G$, and use an inductive argument.)</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>34.2-9</h2>
|
||
<p>Prove that $\text P \subseteq \text{co-NP}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>34.5-5</h2>
|
||
<p>The <strong><em>set-partition problem</em></strong> takes as input a set $S$ of numbers. The question is whether the numbers can be partitioned into two sets $A$ and $\bar A = S - A$ such that $\sum_{x \in A} x = \sum_{x \in \bar A} x$. Show that the set-partition problem is $\text{NP-complete}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>7.1-2</h2>
|
||
<p>What value of $q$ does $\text{PARTITION}$ return when all elements in the array $A[p..r]$ have the same value? Modify $\text{PARTITION}$ so that $q = \lfloor (p + r) / 2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>It returns $r$.</p>
|
||
<p>We can modify $\text{PARTITION}$ by counting the number of comparisons in which $A[j] = A[r]$ and then subtracting half that number from the pivot index.</p>
|
||
</details>
|
||
<h2>22.4-2</h2>
|
||
<p>Give a linear-time algorithm that takes as input a directed acyclic graph $G = (V, E)$ and two vertices $s$ and $t$, and returns the number of simple paths from $s$ to $t$ in $G$. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex $p$ to vertex $v: pov$, $poryv$, $posryv$, and $psryv$. (Your algorithm needs only to count the simple paths, not list them.)</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>The algorithm works as follows. The attribute $u.paths$ of node $u$ tells the number of simple paths from $u$ to $v$, where we assume that $v$ is fixed throughout the entire process. First of all, a topo sort should be conducted and list the vertex between $u$, $v$ as $\{v[1], v[2], \dots, v[k - 1]\}$. To count the number of paths, we should construct a solution from $v$ to $u$. Let's call $u$ as $v[0]$ and $v$ as $v[k]$, to avoid overlapping subproblem, the number of paths between $v_k$ and $u$ should be remembered and used as $k$ decrease to $0$. Only in this way can we solve the problem in $\Theta(V + E)$.</p>
|
||
<p>An bottom-up iterative version is possible only if the graph uses adjacency matrix so whether $v$ is adjacency to $u$ can be determined in $O(1)$ time. But building a adjacency matrix would cost $\Theta(|V|^2)$, so never mind.</p>
|
||
<pre lang="cpp"><code>SIMPLE-PATHS(G, u, v)
|
||
TOPO-SORT(G)
|
||
let {v[1], v[2]..v[k - 1]} be the vertex between u and v
|
||
v[0] = u
|
||
v[k] = v
|
||
for j = 0 to k - 1
|
||
DP[j] = ∞
|
||
DP[k] = 1
|
||
return SIMPLE-PATHS-AID(G, DP, 0)
|
||
</code></pre>
|
||
<pre lang="cpp"><code>SIMPLE-PATHS-AID(G, DP, i)
|
||
if i > k
|
||
return 0
|
||
else if DP[i] != ∞
|
||
return DP[i]
|
||
else
|
||
DP[i] = 0
|
||
for v[m] in G.adj[v[i]] and 0 < m ≤ k
|
||
DP[i] += SIMPLE-PATHS-AID(G, DP, m)
|
||
return DP[i]
|
||
</code></pre>
|
||
</details>
|
||
<h2>4.2-6</h2>
|
||
<p>How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<ul>
|
||
<li>$(kn \times n)(n \times kn)$ produces a $kn \times kn$ matrix. This produces $k^2$ multiplications of $n \times n$ matrices.</li>
|
||
<li>$(n \times kn)(kn \times n)$ produces an $n \times n$ matrix. This produces $k$ multiplications and $k - 1$ additions.</li>
|
||
</ul>
|
||
</details>
|
||
<h2>34.5-6</h2>
|
||
<p>Show that the hamiltonian-path problem is $\text{NP-complete}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>16.2-2</h2>
|
||
<p>Give a dynamic-programming solution to the $0$-$1$ knapsack problem that runs in $O(nW)$ time, where $n$ is the number of items and $W$ is the maximum weight of items that the thief can put in his knapsack.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Suppose we know that a particular item of weight $w$ is in the solution. Then we must solve the subproblem on $n − 1$ items with maximum weight $W − w$. Thus, to take a bottom-up approach we must solve the $0$-$1$ knapsack problem for all items and possible weights smaller than W. We'll build an $n + 1$ by $W + 1$ table of values where the rows are indexed by item and the columns are indexed by total weight. (The first row and column of the table will be a dummy row).</p>
|
||
<p>For row $i$ column $j$, we decide whether or not it would be advantageous to include item i in the knapsack by comparing the total value of of a knapsack including items $1$ through $i − 1$ with max weight $j$, and the total value of including items $1$ through $i − 1$ with max weight $j − i.weight$ and also item $i$. To solve the problem, we simply examine the $n$, $W$ entry of the table to determine the maximum value we can achieve. To read off the items we include, start with entry $n$, $W$. In general, proceed as follows: if entry $i$, $j$ equals entry $i - 1$, $j$, don't include item $i$, and examine entry $i - 1$, $j$ next. If entry $i$, $j$ doesn't equal entry $i − 1$, $j$, include item $i$ and examine entry $i − 1$, $j − i$.weight next. See algorithm below for construction of table:</p>
|
||
<pre lang="cpp"><code>0-1-KNAPSACK(n, W)
|
||
Initialize an (n + 1) by (W + 1) table K
|
||
for i = 1 to n
|
||
K[i, 0] = 0
|
||
for j = 1 to W
|
||
K[0, j] = 0
|
||
for i = 1 to n
|
||
for j = 1 to W
|
||
if j < i.weight
|
||
K[i, j] = K[i - 1, j]
|
||
else
|
||
K[i, j] = max(K[i - 1, j], K[i - 1, j - i.weight] + i.value)
|
||
</code></pre>
|
||
</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.1-1</h2>
|
||
<p>Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge $(u, v)$, and we create a new flow network $G'$ by creating a new vertex $x$ and replacing $(u, v)$ by new edges $(u, x)$ and $(x, v)$ with $c(u, x) = c(x, v) = c(u, v)$. Show that a maximum flow in $G'$ has the same value as a maximum flow in $G$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Suppose the maximum flow of a graph $G = (V, E)$ with source $s$ and destination $t$ is $|f| = \sum{f(s, v)}$, where $v \in V$ are vertices in the maximum flow between $s$ and $t$.</p>
|
||
<p>We know every vertex $v \in V$ must obey the Flow conservation rule. Therefore, if we can add or delete some vertices between $s$ and $t$ without changing $|f|$ or violating the Flow conversation rule, then the new graph $G' = (V', E')$ will have the same maximum flow as the original graph $G$, and that's why we can replace edge $(u, v)$ by new edges $(u, x)$ and $(x, v)$ with $c(u, x) = c(x, v) = c(u, v)$.</p>
|
||
<p>After doing so, vertex $v_1$ and $v_2$ still obey the Flow conservation rule since the values flow in to or flow out of $v_1$ and $v_2$ do not change at all.
|
||
Meanwhile, the value $|f| = \sum{f(s, v)}$ remains the same.</p>
|
||
<p>In fact, we can split any edges in this way, even if two vertex $u$ and $v$ doesn't have any connection between them, we can still add a vertex $y$ and make $c(u, y) = c(y, v) = 0$.</p>
|
||
<p>To conclude, we can transform any graph with or without antiparallel edges into an equivalent graph without antiparallel edges and have the same maximum flow value.</p>
|
||
</details>
|
||
<h2>3.2-8</h2>
|
||
<p>Show that $k\ln k = \Theta(n)$ implies $k = \Theta(n / \lg n)$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>From the symmetry of $\Theta$,</p>
|
||
<p>$$k\ln k = \Theta(n) \Rightarrow n = \Theta(k\ln k).$$</p>
|
||
<p>Let's find $\ln n$,</p>
|
||
<p>$$\ln n = \Theta(\ln(k\ln k)) = \Theta(\ln k + \ln\ln k) = \Theta(\ln k).$$</p>
|
||
<p>Let's divide the two,</p>
|
||
<p>$$\frac{n}{\ln n} = \frac{\Theta(k\ln k)}{\Theta(\ln k)} = \Theta\Big({\frac{k\ln k}{\ln k}}\Big) = \Theta(k).$$</p>
|
||
</details>
|
||
<h2>22.2-6</h2>
|
||
<p>Give an example of a directed graph $G = (V, E)$, a source vertex $s \in V$, and a set of tree edges $E_\pi \subseteq E$ such that for each vertex $v \in V$, the unique simple path in the graph $(V, E_\pi)$ from $s$ to $v$ is a shortest path in $G$, yet the set of edges $E_\pi$ cannot be produced by running $\text{BFS}$ on $G$, no matter how the vertices are ordered in each adjacency list.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Let $G$ be the graph shown in the first picture, $G_\pi = (V, E_\pi)$ be the graph shown in the second picture, and $s$ be the source vertex.</p>
|
||
<p>We could see that $E_\pi$ will never be produced by running BFS on $G$.</p>
|
||
<center>
|
||
|
||
|
||
</center>
|
||
<ul>
|
||
<li>If $y$ precedes $v$ in the $Adj[s]$. We'll dequeue $y$ before $v$, so $u.\pi$ and $x.\pi$ are both $y$. However, this is not the case.</li>
|
||
<li>If $v$ preceded $y$ in the $Adj[s]$. We'll dequeue $v$ before $y$, so $u.\pi$ and $x.\pi$ are both $v$, which again isn't true.</li>
|
||
</ul>
|
||
<p>Nonetheless, the unique simple path in $G_\pi$ from $s$ to any vertex is a shortest path in $G$.</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>26.2-8</h2>
|
||
<p>Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure $\text{FORD-FULKERSON}$ still correctly computes a maximum flow.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Removed)</p>
|
||
</details>
|
||
<h2>26.1-2</h2>
|
||
<p>Extend the flow properties and definitions to the multiple-source, multiple-sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink network obtained by adding a supersource and a supersink, and vice versa.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Capacity constraint: for all $u, v \in V$, we require $0 \le f(u, v) \le c(u, v)$.</p>
|
||
<p>Flow conservation: for all $u \in V - S - T$, we require $\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$.</p>
|
||
</details>
|
||
<h2>34.2-10</h2>
|
||
<p>Prove that if $\text{NP} \ne \text{co-NP}$, then $\text P \ne \text{NP}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>(Omit!)</p>
|
||
</details>
|
||
<h2>12.4-1</h2>
|
||
<p>Prove equation $\text{(12.3)}$.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>Consider all the possible positions of the largest element of the subset of $n + 3$ of size $4$. Suppose it were in position $i + 4$ for some $i \le n − 1$. Then, we have that there are $i + 3$ positions from which we can select the remaining three elements of the subset. Since every subset with different largest element is different, we get the total by just adding them all up (inclusion exclusion principle).</p>
|
||
</details>
|
||
<h2>34.1-3</h2>
|
||
<p>Give a formal encoding of directed graphs as binary strings using an adjacency-matrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>A formal encoding of the adjacency matrix representation is to first encode an integer $n$ in the usual binary encoding representing the number of vertices. Then, there will be $n^2$ bits following. The value of bit $m$ will be $1$ if there is an edge from vertex $\lfloor m / n \rfloor$ to vertex $(m \mod n)$, and $0$ if there is not such an edge.</p>
|
||
<p>An encoding of the adjacency list representation is a bit more finessed. We'll be using a different encoding of integers, call it $g(n)$. In particular, we will place a $0$ immediately after every bit in the usual representation. Since this only doubles the length of the encoding, it is still polynomially related. Also, the reason we will be using this encoding is because any sequence of integers encoded in this way cannot contain the string $11$ and must contain at least one $0$. Suppose that we have a vertex with edges going to the vertices indexed by $i_1, i_2, i_3, \dots, i_k$. Then, the encoding corresponding to that vertex is $g(i_1)11g(i_2)11 \dots 11g(i_k)1111$. Then, the encoding of the entire graph will be the concatenation of all the encodings of the vertices. As we are reading through, since we used this encoding of the indices of the vertices, we won’t ever be confused about where each of the vertex indices ends or when we are moving on to the next vertex's list.</p>
|
||
<p>To go from the list to matrix representation, we can read off all the adjacent vertices, store them, sort them, and then output a row of the adjacency matrix. Since there is some small constant amount of space for the adjacency list representation for each vertex in the graph, the size of the encoding blows up by at most a factor of $O(n)$, which means that the size of the encoding overall is at most squared.</p>
|
||
<p>To go in the other direction, it is just a matter of keeping track of the positions in a given row that have $1$'s, encoding those numerical values in the way described, and doing this for each row. Since we are only increasing the size of the encoding by a factor of at most $O(\lg n)$ (which happens in the dense graph case), we have that both of them are polynomially related.</p>
|
||
</details>
|
||
<h2>16.2-6 *</h2>
|
||
<p>Show how to solve the fractional knapsack problem in $O(n)$ time.</p>
|
||
<details>
|
||
<summary>Solution</summary>
|
||
<p>First compute the value of each item, defined to be it's worth divided by its weight. We use a recursive approach as follows, find the item of median value, which can be done in linear time as shown in chapter 9. Then sum the weights of all items whose value exceeds the median and call it $M$. If $M$ exceeds $W$ then we know that the solution to the fractional knapsack problem lies in taking items from among this collection. In other words, we're now solving the fractional knapsack problem on input of size $n / 2$. On the other hand, if the weight doesn't exceed $W$, then we must solve the fractional knapsack problem on the input of $n / 2$ low-value items, with maximum weight $W − M$. Let $T(n)$ denote the runtime of the algorithm. Since we can solve the problem when there is only one item in constant time, the recursion for the runtime is $T(n) = T(n / 2) + cn$ and $T(1) = d$, which gives runtime of $O(n)$.</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>
|