345 lines
24 KiB
HTML
345 lines
24 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.4-6 *</h2>
|
|||
|
|
<p>Give an $O(n\lg n)$-time algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers. ($\textit{Hint:}$ Observe that the last element of a candidate subsequence of length $i$ is at least as large as the last element of a candidate subsequence of length $i - 1$. Maintain candidate subsequences by linking them through the input sequence.)</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>The algorithm $\text{LONG-MONOTONIC}(A)$ returns the longest monotonically increasing subsequence of $A$, where $A$ has length $n$.</p>
|
|||
|
|
<p>The algorithm works as follows: a new array B will be created such that $B[i]$ contains the last value of a longest monotonically increasing subsequence of length $i$. A new array $C$ will be such that $C[i]$ contains the monotonically increasing subsequence of length $i$ with smallest last element seen so far.</p>
|
|||
|
|
<p>To analyze the runtime, observe that the entries of $B$ are in sorted order, so we can execute line 9 in $O(\lg n)$ time. Since every other line in the for-loop takes constant time, the total run-time is $O(n\lg n)$.</p>
|
|||
|
|
<pre lang="cpp"><code>LONG-MONOTONIC(A)
|
|||
|
|
let B[1..n] be a new array where every value = ∞
|
|||
|
|
let C[1..n] be a new array
|
|||
|
|
L = 1
|
|||
|
|
for i = 1 to n
|
|||
|
|
if A[i] < B[1]
|
|||
|
|
B[1] = A[i]
|
|||
|
|
C[1].head.key = A[i]
|
|||
|
|
else
|
|||
|
|
let j be the largest index of B such that B[j] < A[i]
|
|||
|
|
B[j + 1] = A[i]
|
|||
|
|
C[j + 1] = C[j]
|
|||
|
|
INSERT(C[j + 1], A[i])
|
|||
|
|
if j + 1 > L
|
|||
|
|
L = L + 1
|
|||
|
|
print C[L]
|
|||
|
|
</code></pre>
|
|||
|
|
</details>
|
|||
|
|
<h2>4.3-2</h2>
|
|||
|
|
<p>Show that the solution of $T(n) = T(\lceil n / 2 \rceil) + 1$ is $O(\lg n)$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>We guess $T(n) \le c\lg(n - a)$,</p>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{aligned}
|
|||
|
|
T(n) & \le c\lg(\lceil n / 2 \rceil - a) + 1 \\
|
|||
|
|
& \le c\lg((n + 1) / 2 - a) + 1 \\
|
|||
|
|
& = c\lg((n + 1 - 2a) / 2) + 1 \\
|
|||
|
|
& = c\lg(n + 1 - 2a) - c\lg 2 + 1 & (c \ge 1) \\
|
|||
|
|
& \le c\lg(n + 1 - 2a) & (a \ge 1) \\
|
|||
|
|
& \le c\lg(n - a),
|
|||
|
|
\end{aligned}
|
|||
|
|
$$</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>16.3-9</h2>
|
|||
|
|
<p>Show that no compression scheme can expect to compress a file of randomly chosen $8$-bit characters by even a single bit. ($\textit{Hint:}$ Compare the number of possible files with the number of possible encoded files.)</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>If every possible character is equally likely, then, when constructing the Huffman code, we will end up with a complete binary tree of depth $7$. This means that every character, regardless of what it is will be represented using $7$ bits.</p>
|
|||
|
|
<p>This is exactly as many bits as was originally used to represent those characters,
|
|||
|
|
so the total length of the file will not decrease at all.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>22.5-4</h2>
|
|||
|
|
<p>Prove that for any directed graph $G$, we have $((G^\text T)^{\text{SCC}})^\text T = G^{\text{SCC}}$. That is, the transpose of the component graph of $G^\text T$ is the same as the component graph of $G$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>First observe that $C$ is a strongly connected component of $G$ if and only if it is a strongly connected component of $G^\text T$. Thus the vertex sets of $G^{\text{SCC}}$ and $(G^\text T)^{\text{SCC}}$ are the same, which implies the vertex sets of $((G^\text T)^\text{SCC})^\text T$ and $G^{\text{SCC}}$ are the same. It suffices to show that their edge sets are the same. Suppose $(v_i, v_j)$ is an edge in $((G^\text T)^{\text{SCC}})^\text T$. Then $(v_j, v_i)$ is an edge in $(G^\text T)^{\text{SCC}}$. Thus there exist $x \in C_j$ and $y \in C_i$ such that $(x, y)$ is an edge of $G^\text T$, which implies $(y, x)$ is an edge of $G$. Since components are preserved, this means that $(v_i, v_j)$ is an edge in $G^{\text{SCC}}$. For the opposite implication we simply note that for any graph $G$ we have $(G^\text T)^{\text T} = G$.</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>26.4-1</h2>
|
|||
|
|
<p>Prove that, after the procedure $\text{INITIALIZE-PREFLOW}(G, S)$ terminates, we have $s.e \le -|f^*|$, where $f^*$ is a maximum flow for $G$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>(Removed)</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>26.1-5</h2>
|
|||
|
|
<p>State the maximum-flow problem as a linear-programming problem.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{array}{ll}
|
|||
|
|
\max & \sum\limits_{v \in V} f(s, v) - \sum\limits_{v \in V} f(v, s) \\
|
|||
|
|
s.t. & 0 \le f(u, v) \le c(u, v) \\
|
|||
|
|
& \sum\limits_{v \in V} f(v, u) - \sum\limits_{v \in V} f(u, v) = 0
|
|||
|
|
\end{array}
|
|||
|
|
$$</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>22.3-3</h2>
|
|||
|
|
<p>Show the parenthesis structure of the depth-first search of Figure 22.4.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>The parentheses structure of the depth-first search of Figure 22.4 is $(u(v(y(xx)y)v)u)(w(zz)w)$.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>24.3-7</h2>
|
|||
|
|
<p>Let $G = (V, E)$ be a weighted, directed graph with positive weight function $w: E \rightarrow \{1, 2, \ldots, W\}$ for some positive integer $W$, and assume that no two vertices have the same shortest-path weights from source vertex $s$. Now suppose that we define an unweighted, directed graph $G' = (V \cup V', E')$ by replacing each edge $(u, v) \in E$ with $w(u, v)$ unit-weight edges in series. How many vertices does $G'$ have? Now suppose that we run a breadth-first search on $G'$. Show that the order in which the breadth-first search of $G'$ colors vertices in $V$ black is the same as the order in which Dijkstra's algorithm extracts the vertices of $V$ from the priority queue when it runs on $G$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>$V + \sum_{(u, v) \in E} w(u, v) - E$.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>12.2-2</h2>
|
|||
|
|
<p>Write recursive versions of $\text{TREE-MINIMUM}$ and $\text{TREE-MAXIMUM}$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<pre lang="cpp"><code>TREE-MINIMUM(x)
|
|||
|
|
if x.left != NIL
|
|||
|
|
return TREE-MINIMUM(x.left)
|
|||
|
|
else return x
|
|||
|
|
</code></pre>
|
|||
|
|
<pre lang="cpp"><code>TREE-MAXIMUM(x)
|
|||
|
|
if x.right != NIL
|
|||
|
|
return TREE-MAXIMUM(x.right)
|
|||
|
|
else return x
|
|||
|
|
</code></pre>
|
|||
|
|
</details>
|
|||
|
|
<h2>26.3-4 *</h2>
|
|||
|
|
<p>A <strong><em>perfect matching</em></strong> is a matching in which every vertex is matched. Let $G = (V, E)$ be an undirected bipartite graph with vertex partition $V = L \cup R$, where $|L| = |R|$. For any $X \subseteq V$, define the <strong><em>neighborhood</em></strong> of $X$ as</p>
|
|||
|
|
<blockquote>
|
|||
|
|
<p>$$N(X) = \{y \in V: (x, y) \in E \text{ for some } x \in X\},$$</p>
|
|||
|
|
<p>that is, the set of vertices adjacent to some member of $X$. Prove <strong><em>Hall's theorem</em></strong>: there exists a perfect matching in $G$ if and only if $|A| \le |N(A)|$ for every subset $A \subseteq L$.</p>
|
|||
|
|
</blockquote>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>First suppose there exists a perfect matching in $G$. Then for any subset $A \subseteq L$, each vertex of $A$ is matched with a neighbor in $R$, and since it is a matching, no two such vertices are matched with the same vertex in $R$. Thus, there are at least $|A|$ vertices in the neighborhood of $A$.</p>
|
|||
|
|
<p>Now suppose that $|A| \le |N(A)|$ for all $A \subseteq L$. Run Ford-Fulkerson on the corresponding flow network. The flow is increased by $1$ each time an augmenting path is found, so it will suffice to show that this happens $|L|$ times. Suppose the while loop has run fewer than $L$ times, but there is no augmenting path. Then fewer than $L$ edges from $L$ to $R$ have flow $1$.</p>
|
|||
|
|
<p>Let $v_1 \in L$ be such that no edge from $v_1$ to a vertex in $R$ has nonzero flow. By assumption, $v_1$ has at least one neighbor $v_1' \in R$. If any of $v_1$'s neighbors are connected to $t$ in $G_f$ then there is a path, so assume this is not the case. Thus, there must be some edge $(v_2, v_1)$ with flow $1$. By assumption, $N(\{v_1, v_2\}) \ge 2$, so there must exist $v_2' \ne v_1'$ such that $v_2'\in N(\{v_1, v_2 \})$. If $(v_2', t)$ is an edge in the residual network we're done since $v_2'$ must be a neighbor of $v_2$, so $s$, $v_1$, $v_1'$, $v_2$, $v_2'$, and $t$ is a path in $G_f$. Otherwise $v_2'$ must have a neighbor $v_3 \in L$ such that $(v_3, v_2')$ is in $G_f$. Specifically, $v_3 \ne v_1$ since $(v_3, v_2')$ has flow $1$, and $v_3 \ne v_2$ since $(v_2, v_1')$ has flow $1$, so no more flow can leave $v_2$ without violating conservation of flow. Again by our hypothesis, $N(\{v_1, v_2, v_3\}) \ge 3$, so there is another neighbor $v_3' \in R$.</p>
|
|||
|
|
<p>Continuing in this fashion, we keep building up the neighborhood $v_i'$, expanding each time we find that $(v_i', t)$ is not an edge in $G_f$. This cannot happen $L$ times, since we have run the Ford-Fulkerson while-loop fewer than $|L|$ times, so there still exist edges into $t$ in $G_f$. Thus, the process must stop at some vertex $v_k'$, and we obtain an augmenting path</p>
|
|||
|
|
<p>$$s, v_1, v_1', v_2, v_2', v_3, \ldots, v_k, v_k', t,$$</p>
|
|||
|
|
<p>contradicting our assumption that there was no such path. Therefore the while loop runs at least $|L|$ times. By Corollary 26.3 the flow strictly increases each time by $f_p$. By Theorem 26.10 $f_p$ is an integer. In particular, it is equal to $1$. This implies that $|f| \ge |L|$. It is clear that $|f| \le |L|$, so we must have $|f| = |L|$. By Corollary 26.11 this is the cardinality of a maximum matching. Since $|L| = |R|$, any maximum matching must be a perfect matching.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>4.4-3</h2>
|
|||
|
|
<p>Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n / 2 + 2) + n$. 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 $4^{\lg n} = n^2$ leaves.</p>
|
|||
|
|
<p>The total cost over all nodes at depth $i$, for $i = 0, 1, 2, \ldots, \lg n - 1$, is $4^i(n / 2^i + 2) = 2^i n + 2 \cdot 4^i$.</p>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{aligned}
|
|||
|
|
T(n) & = \sum_{i = 0}^{\lg n - 1} (2^i n + 2 \cdot 4^i) + \Theta(n^2) \\
|
|||
|
|
& = \sum_{i = 0}^{\lg n - 1} 2^i n + \sum_{i = 0}^{\lg n - 1} 2 \cdot 4^i + \Theta(n^2) \\
|
|||
|
|
& = \frac{2^{\lg n} - 1}{2 - 1}n + 2 \cdot \frac{4^{\lg n} - 1}{4 - 1} + \Theta(n^2) \\
|
|||
|
|
& = (2^{\lg n} - 1)n + \frac{2}{3} (4^{\lg n} - 1) + \Theta(n^2) \\
|
|||
|
|
& = (n - 1)n + \frac{2}{3}(n^2 - 1) + \Theta(n^2) \\
|
|||
|
|
& = \Theta(n^2).
|
|||
|
|
\end{aligned}
|
|||
|
|
$$</p>
|
|||
|
|
</li>
|
|||
|
|
<li>
|
|||
|
|
<p>We guess $T(n) \le c(n^2 - dn)$,</p>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{aligned}
|
|||
|
|
T(n) & = 4T(n / 2 + 2) + n \\
|
|||
|
|
& \le 4c[(n / 2 + 2)^2 - d(n / 2 + 2)] + n \\
|
|||
|
|
& = 4c(n^2 / 4 + 2n + 4 - dn / 2 - 2d) + n \\
|
|||
|
|
& = cn^2 + 8cn + 16c - 2cdn - 8cd + n \\
|
|||
|
|
& = cn^2 - cdn + 8cn + 16c - cdn - 8cd + n \\
|
|||
|
|
& = c(n^2 - dn) - (cd - 8c - 1)n - (d - 2) \cdot 8c \\
|
|||
|
|
& \le c(n^2 - dn),
|
|||
|
|
\end{aligned}
|
|||
|
|
$$</p>
|
|||
|
|
<p>where the last step holds for $cd - 8c - 1 \ge 0$.</p>
|
|||
|
|
</li>
|
|||
|
|
</ul>
|
|||
|
|
</details>
|
|||
|
|
<h2>22.2-3</h2>
|
|||
|
|
<p>Show that using a single bit to store each vertex color suffices by arguing that the $\text{BFS}$ procedure would produce the same result if lines 5 and 14 were removed.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>The textbook introduces the $\text{GRAY}$ color for the pedagogical purpose to distinguish between the $\text{GRAY}$ nodes (which are enqueued) and the $\text{BLACK}$ nodes (which are dequeued).</p>
|
|||
|
|
<p>Therefore, it suffices to use a single bit to store each vertex color.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>16.2-4</h2>
|
|||
|
|
<p>Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate $m$ miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections.) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations.</p>
|
|||
|
|
<blockquote>
|
|||
|
|
<p>The professor's goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time.</p>
|
|||
|
|
</blockquote>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>The greedy solution solves this problem optimally, where we maximize distance we can cover from a particular point such that there still exists a place to get water before we run out. The first stop is at the furthest point from the starting position which is less than or equal to $m$ miles away. The problem exhibits optimal substructure, since once we have chosen a first stopping point $p$, we solve the subproblem assuming we are starting at $p$. Combining these two plans yields an optimal solution for the usual cut-and-paste reasons. Now we must show that this greedy approach in fact yields a first stopping point which is contained in some optimal solution. Let $O$ be any optimal solution which has the professor stop at positions $o_1, o_2, \dots, o_k$. Let $g_1$ denote the furthest stopping point we can reach from the starting point. Then we may replace $o_1$ by $g_2$ to create a modified solution $G$, since $o_2 - o_1 < o_2 - g_1$. In other words, we can actually make it to the positions in $G$ without running out of water. Since $G$ has the same number of stops, we conclude that $g_1$ is contained in some optimal solution. Therefore the greedy strategy works.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>4.3-6</h2>
|
|||
|
|
<p>Show that the solution to $T(n) = 2T(\lfloor n / 2 \rfloor + 17) + n$ is $O(n\lg n)$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>We guess $T(n) \le c(n - a)\lg(n - a)$,</p>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{aligned}
|
|||
|
|
T(n) & \le 2c(\lfloor n / 2 \rfloor + 17 - a)\lg(\lfloor n / 2 \rfloor + 17 - a) + n \\
|
|||
|
|
& \le 2c(n / 2 + 17 - a)\lg(n / 2 + 17 - a) + n \\
|
|||
|
|
& = c(n + 34 - 2a)\lg\frac{n + 34 - 2a}{2} + n \\
|
|||
|
|
& = c(n + 34 - 2a)\lg(n + 34 - 2a) - c(n + 34 - 2a) + n & (c > 1, n > n_0 = f(a)) \\
|
|||
|
|
& \le c(n + 34 - 2a)\lg(n + 34 - 2a) & (a \ge 34) \\
|
|||
|
|
& \le c(n - a)\lg(n - a).
|
|||
|
|
\end{aligned}
|
|||
|
|
$$</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>16.3-3</h2>
|
|||
|
|
<p>What is an optimal Huffman code for the following set of frequencies, based on</p>
|
|||
|
|
<blockquote>
|
|||
|
|
<p>the first $8$ Fibonacci numbers?</p>
|
|||
|
|
<p>$$a:1 \quad b:1 \quad c:2 \quad d:3 \quad e:5 \quad f:8 \quad g:13 \quad h:21$$</p>
|
|||
|
|
<p>Can you generalize your answer to find the optimal code when the frequencies are the first $n$ Fibonacci numbers?</p>
|
|||
|
|
</blockquote>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{array}{c|l}
|
|||
|
|
a & 1111111 \\
|
|||
|
|
b & 1111110 \\
|
|||
|
|
c & 111110 \\
|
|||
|
|
d & 11110 \\
|
|||
|
|
e & 1110 \\
|
|||
|
|
f & 110 \\
|
|||
|
|
g & 10 \\
|
|||
|
|
h & 0
|
|||
|
|
\end{array}
|
|||
|
|
$$</p>
|
|||
|
|
<p><strong>GENERALIZATION</strong></p>
|
|||
|
|
<p>In what follows we use $a_i$ to denote $i$-th Fibonacci number. To avoid any confusiion we stress that we consider Fibonacci's sequence beginning $1$, $1$, i.e. $a_1 = a_2 = 1$.</p>
|
|||
|
|
<p>Let us consider a set of $n$ symbols $\Sigma = \{c_i ~|~ 1 \le i \le n \}$ such that for each $i$ we have $c_i.freq = a_i$. We shall prove that the Huffman code for this set of symbols given by the run of algorithm HUFFMAN from CLRS is the following code:</p>
|
|||
|
|
<ul>
|
|||
|
|
<li>$code(c_n) = 0$</li>
|
|||
|
|
<li>$code(c_{i - 1}) = 1code(c_i)$ for $2 \le i \le n - 1$ (i.e. we take a code for symbol $c_i$ and add $1$ to the beginning)</li>
|
|||
|
|
<li>$code(c_1) = 1^{n - 1}$</li>
|
|||
|
|
</ul>
|
|||
|
|
<p>By $code(c)$ we mean the codeword assigned to the symbol $c_i$ by the run of HUFFMAN($\Sigma$) for any $c \in \Sigma$.</p>
|
|||
|
|
<p>First we state two technical claims which can be easily proven using the proper induction. Following good manners of our field we leave the proofs to the reader :-)</p>
|
|||
|
|
<ul>
|
|||
|
|
<li>(HELPFUL CLAIM 1) $ (\forall k \in \mathbb{N}) ~ \sum\limits_{i = 1}^{k} a_i = a_{k + 2} - 1$</li>
|
|||
|
|
<li>(HELPFUL CLAIM 2) Let $z$ be an inner node of tree $T$ constructed by the algorithm HUFFMAN. Then $z.freq$ is sum of frequencies of all leafs of the subtree of $T$ rooted in $z$.</li>
|
|||
|
|
</ul>
|
|||
|
|
<p>Consider tree $T_n$ inductively defined by</p>
|
|||
|
|
<ul>
|
|||
|
|
<li>$T_2.left = c_2$, $T_2.right = c_1$ and $T_2.freq = c_1.freq + c_2.freq = 2$</li>
|
|||
|
|
<li>$(\forall i; 3 \le i \le n) ~ T_i.left = c_i$, $T_i.right = T_{i - 1}$ and $T_i.freq = c_i.freq + T_{i - 1}.freq$</li>
|
|||
|
|
</ul>
|
|||
|
|
<p>We shall prove that $T_n$ is the tree produced by the run of HUFFMAN($\Sigma$).</p>
|
|||
|
|
<p><strong>KEY CLAIM:</strong> $T_{i + 1}$ is exactly the node $z$ constructed in $i$-th run of the for-cycle of HUFFMAN($\Sigma$) and the content of the priority queue $Q$ just after $i$-th run of the for-cycle is exactly $Q = (a_{i + 2}, T_{i + 1}, a_{i + 3}, \dots, a_n)$ with $a_{i + 2}$ being the minimal element for each $1 \le i < n$. (Since we prefer not to overload our formal notation we just note that for $i = n - 1$ we claim that $Q = (T_n)$ and our notation grasp this fact in a sense.)</p>
|
|||
|
|
<p><strong>PROOF OF KEY CLAIM</strong> by induction on $i$.</p>
|
|||
|
|
<ul>
|
|||
|
|
<li>for $i = 1$ we see that the characters with lowest frequencies are exactly $c_1$ and $c_2$, thus obviously the algorithm HUFFMAN($\Sigma$) constructs $T_2$ in the first run of its for-cycle. Also it is obvious that just after this run of the for-cycle we have $Q = (a_3, T_{2}, a_4, \dots, a_n)$.</li>
|
|||
|
|
<li>for $2 \le i < n$ we suppose that our claim is true for all $j < i$ and prove the claim for $i$. Since the claim is true for $i - 1$, we know that just before $i-th$ execution of the for-cycle we have the following content of the priority queue $Q=(a_{i + 1}, T_i, a_{i + 2}, \dots, a_n)$. Thus line 5 of HUFFMAN extracts $a_{i + 1}$ and sets $z.left = a_{i + 1}$ and line 6 of HUFFMAN extracts $T_i$ and sets $z.right = T_i$. Now we can see that indeed $z$ is exactly $T_{i + 1}$. Using (CLAIM 2) and observing the way $T_{i + 1}$ is defined we get that $z.freq = T_{i + 1}.freq = \sum\limits_{i=1}^{i + 1} a_i$. Thus using (CLAIM 1) one can see that $a_{i + 2} < T_{i + 1}.freq < a_{i + 3}$. Therefore for the content of the priority queue $Q$ just after the $i$-th execution of the for-cycle we have $Q=(a_{i + 2}, T_{i + 2}, a_{i + 3}, \dots, a_n)$.</li>
|
|||
|
|
</ul>
|
|||
|
|
<p><strong>KEY CLAIM</strong> tells us that just after the last execution of the for-cycle we have $Q = (T_n)$ and therefore the line 9 of HUFFMAN returns $T_n$ as the result. One can easily see that the code given in the beginning is exactly the code which corresponds to the code-tree $T_n$.</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>34.1-6</h2>
|
|||
|
|
<p>Show that the class $P$, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if $L_1, L_2 \in P$, then $L_1 \cup L_2 \in P$, $L_1 \cap L_2 \in P$, $L_1L_2 \in P$, $\bar L_1 \in P$, and $L_1^* \in P$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>(Omit!)</p>
|
|||
|
|
</details>
|
|||
|
|
<h2>16.5-1</h2>
|
|||
|
|
<p>Solve the instance of the scheduling problem given in Figure 16.7, but with each penalty $w_i$ replaced by $80 - w_i$.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>$$
|
|||
|
|
\begin{array}{c|ccccccc}
|
|||
|
|
a_i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
|
|||
|
|
\hline
|
|||
|
|
d_i & 4 & 2 & 4 & 3 & 1 & 4 & 6 \\
|
|||
|
|
w_i & 10 & 20 & 30 & 40 & 50 & 60 & 70
|
|||
|
|
\end{array}
|
|||
|
|
$$</p>
|
|||
|
|
<p>We begin by just greedily constructing the matroid, adding the most costly to leave incomplete tasks first. So, we add tasks $7, 6, 5, 4, 3$. Then, in order to schedule tasks $1$ or $2$ we need to leave incomplete more important tasks. So, our final schedule is $\langle 5, 3, 4, 6, 7, 1, 2 \rangle$ to have a total penalty of only $w_1 + w_2 = 30$.</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>12.3-2</h2>
|
|||
|
|
<p>Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.</p>
|
|||
|
|
<details>
|
|||
|
|
<summary>Solution</summary>
|
|||
|
|
<p>Number of nodes examined while searching also includes the node which is searched for, which isn't the case when we inserted it.</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>
|