Exercise 7.1-2
What value of q does PARTITION return when all elements in the array $A[p \ldots r]$ have the same value? Modify PARTITION so that $q = (p+r)/2$ when all elements in the array $A[p \ldots r]$ have the same value.
Solution:
When all the elements have the same value, PARTITION will return r. We modify line 4 to "do if (A[j] < x) or (A[j] == x and j mod 2 == 0)", so that PARTITION will return $q = (p+r)/2$.
Exercise 7.1-3
Give a brief argument that the running time of PARTITION on a subarray of size n is $\Theta(n)$.
Solution:
From line 3 to line 6, we can see that we have a constant number of operations within each loop.
Exercise 7.1-4
How would you modify QUICKSORT to sort into nonincreasing order?
Solution:
We could modify line 4 to "do if $A[j] \geq x$".
2010年6月28日 星期一
[Algo] 7.1 Description of quicksort
quicksort 的原理
一樣是 divide and conquer 的方法，假設 $A[p \ldots r]$ 是我們想要做排序的 array，那我們先找一個 element 來當作基準值(pivot)，把 $A[p \ldots r]$ 分成 $A[p \ldots q-1]$，$A[q]$，$A[q+1, \ldots r]$ 三部份，其中 $A[p \ldots q-1]$ 為所有比 $A[q]$ 小的 elements，$A[q+1, \ldots r]$ 為比 $A[q]$ 大的 elements。接著 $A[p \ldots q-1]$ 跟 $A[q+1 \ldots r]$ 這兩個 subarrays 再繼續用這個方法分下去，(找出一個 pivot，然後把 array 分成比 pivot 小的放一邊，比 pivot 大的放另外一邊)分到最後當 arrary 的 size 只剩3個 elements 的時候，其實我們這時候就可以說是到了 recursion 的終點了，整個排序也就完成了。
quicksort 的 pseudocode
@{
\proc{Quicksort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \proc{Partition}(A, p, r)
\li \;\;\;\;\proc{Quicksort}(A, p, q - 1)
\li \;\;\;\;\proc{Quicksort}(A, q + 1, r)
}@
PARTITION 解說
(1) 直接律定 array 的最後一個 element $A[r]$ 為 pivot
(2) 從 $A[p]$ 開始 scan 到 $A[r-1]$，在每個 loop 都保持這樣的 property：
(a) $A[p \ldots i]$ 都是比 pivot 小的 elements
(b) $A[i+1 \ldots j-1]$ 都是比 pivot 大的 elements
(3) 最後把 pivot 放到分界點 $A[i+1]$
對 $A[p \ldots r]$ 執行 PARTITION 的 running time 是 $\Theta(n)$，其中 $n = r - p + 1$。
一樣是 divide and conquer 的方法，假設 $A[p \ldots r]$ 是我們想要做排序的 array，那我們先找一個 element 來當作基準值(pivot)，把 $A[p \ldots r]$ 分成 $A[p \ldots q-1]$，$A[q]$，$A[q+1, \ldots r]$ 三部份，其中 $A[p \ldots q-1]$ 為所有比 $A[q]$ 小的 elements，$A[q+1, \ldots r]$ 為比 $A[q]$ 大的 elements。接著 $A[p \ldots q-1]$ 跟 $A[q+1 \ldots r]$ 這兩個 subarrays 再繼續用這個方法分下去，(找出一個 pivot，然後把 array 分成比 pivot 小的放一邊，比 pivot 大的放另外一邊)分到最後當 arrary 的 size 只剩3個 elements 的時候，其實我們這時候就可以說是到了 recursion 的終點了，整個排序也就完成了。
quicksort 的 pseudocode
@{
\proc{Quicksort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \proc{Partition}(A, p, r)
\li \;\;\;\;\proc{Quicksort}(A, p, q - 1)
\li \;\;\;\;\proc{Quicksort}(A, q + 1, r)
}@
@{
\proc{Partition}(A, p, r)
\li x = A[r]
\li i = p - 1
\li \For j = p \;\textbf{to}\;r - 1
\li \;\;\;\;\If A[j] \leq x
\li \;\;\;\;\;\;\;\;i = i + 1
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[j]
\li \textup{exchange}\;A[i+1]\;\textup{and}\;A[r]
\li \Return i + 1
}@
\proc{Partition}(A, p, r)
\li x = A[r]
\li i = p - 1
\li \For j = p \;\textbf{to}\;r - 1
\li \;\;\;\;\If A[j] \leq x
\li \;\;\;\;\;\;\;\;i = i + 1
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[j]
\li \textup{exchange}\;A[i+1]\;\textup{and}\;A[r]
\li \Return i + 1
}@
PARTITION 解說
(1) 直接律定 array 的最後一個 element $A[r]$ 為 pivot
(2) 從 $A[p]$ 開始 scan 到 $A[r-1]$，在每個 loop 都保持這樣的 property：
(a) $A[p \ldots i]$ 都是比 pivot 小的 elements
(b) $A[i+1 \ldots j-1]$ 都是比 pivot 大的 elements
(3) 最後把 pivot 放到分界點 $A[i+1]$
對 $A[p \ldots r]$ 執行 PARTITION 的 running time 是 $\Theta(n)$，其中 $n = r - p + 1$。
2010年6月19日 星期六
[Algo] Problem 6
Problem 6-1 Building a heap using insertion
The procdure BUILD-MAX-HEAP in section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:
\\ 1\;\;\textit{heap-size}[A] = 1\\ 2\;\;\textbf{for}\;i = 2 \;\textbf{to}\;\textit{length}[A]\\ 3\;\;\;\;\;\;\textsc{Max-Heap-Insert}(A, A[i]) "\textsc{Build-Max-Heap}^{'}(A)\\ 1\;\;\textit{heap-size}[A] = 1\\ 2\;\;\textbf{for}\;i = 2 \;\textbf{to}\;\textit{length}[A]\\ 3\;\;\;\;\;\;\textsc{Max-Heap-Insert}(A, A[i])")
a. Do the procedure BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build an n-element heap.
Solution:
a. Given an array A = <2, 3, 1, 4, 5>, procedure BUILD-MAX-HEAP will give the output A = <5, 4, 1, 2, 3> and procedure BUILD-MAX-HEAP' will give the output A = <5, 4, 1, 3, 2>
b.Obviously, the upper bound is $O(n \lg n)$ due to calling procedure MAX-HEAP-INSERT (n-1) times. For the lower bound, consider the worst case which is input in increasing order. Each inserted item goes along a path from leaf to root. Since the depth is $\lfloor \lg i \rfloor$, the total time is:
$\sum_{i = 1}^{n-1} \Theta(\lfloor \lg i \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg \lceil n/2\rceil \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n/2) \rfloor)$
$ = \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n) - 1 \rfloor) \geq n/2 \cdot \Theta(\lg n) = \Omega(n \lg n)$
Thus, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build a n-element heap.
Problem 6-2 Analysis of d-ary heaps
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
a. How would you represent a d-ary heap in an array?
b. What is the height of a d-ary heap of n elements in terms of n and d?
c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A, i, k), which first sets A[i] $\leftarrow$ max(A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.
Solution:
a. Given an index i, we want to find its kth-child ($1 \leq k \leq d$). We can view $i = 1 + d + d^2 + \cdots + d^n + p = \frac{d^{n+1} - 1}{d - 1} + p$, where $1 \leq p \leq d^{n+1}$. The index of k-th child of A[i] is:
$i + (d^{n+1} - p) + (p-1)d + k = \frac{d^{n+1} - 1}{d - 1} + p + d^{n+1} - p + (i - \frac{d^{n+1} - 1}{d - 1} - 1)d + k$
$= \frac{d^{n+1} - 1}{d - 1} + d^{n+1} + id - \frac{d^{n + 2} - d}{d - 1} - d + k = id -d + 1 + k$
Therefore, we show how to get the index of k-th child of A[i]. Next we show how to get the index of parent of A[i]. We know nodes A[j] where $id - d + 1 + 1 \leq j \leq id - d + 1 + d$ have the same parent $i$. Trivially we know that $\lfloor \frac{j + (d - 2)}{d}\rfloor$ is the index of their parent.
b. Let h be the height of a d-ary heap of n elements. Then we can obtain:
$1 + d + d^2 + \cdots + d^{h-1} +1 \leq n \leq 1 + d + d^2 + \cdots + d^h$
$\Rightarrow \frac{d^h - 1}{d - 1} < n \leq \frac{d^{h+1} - 1}{d - 1}$
$\Rightarrow d^h - 1 < (d - 1)n \leq d^{h + 1} - 1$
$\Rightarrow d^h \leq (d-1)n < d^{h+1}$
$\Rightarrow h \leq \log_d ((d-1)n) < h + 1$
$\Rightarrow h = \lfloor \log_d (d-1)n \rfloor$
c. We can develop a generalized version of EXTRACT-MAX in a manner as binary version. However, it should compare all its d children instead of 2 children.
@{
\proc{D-Ary-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{D-Ary-Max-Heapify}(A, 1)
\li \Return max
}@
The procedure D-ARY-EXTRACT-MAX implements the EXTRACT-MAX operation. The running time of D-ARY-EXTRACT-MAX is $O(d \log_d (d-1)n)$. Since each time we call D-ARY-MAX-HEAPIFY, it would check all its d children ($O(d)$). In the worst-case, the item will go down to a leaf, so takes $O( \log_d (d-1)n) * O(d) = O(d \log_d (d-1)n)$ time.
d. We can implement a generalized version of INSERT by updating operation PARENT with the operation which we derived in problem a. The running time is $O(\log_d (d-1)n)$
e. D-ARY-HEAP-INCREASE-KEY can be implemented as a slight modification of HEAP-INCREASE-KEY. The running time is $O(\log_d (d-1)n)$.
Problem 6-3 Young tableaus
An $m \times n$ Young tableau is an $m \times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be $\infty$, which we treat as nonexistent element. Thus, a Young tableau can be used to hold $r \leq mn$ finite numbers.
a. Draw a $4 \times 4$ Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.
b. Argue that an $m \times n$ Young tableau Y is empty if $Y[1, 1] = \infty$. Argue that Y is full (contains mn elements) if $Y[m, n] < \infty$.
c. Give an algorithm to implement EXTRACT-MIN on a nonempty $m \times n$ Young tableau that runs in $O(m + n)$ time. Your algorithm should use a recursive subroutine that solves an $m \times n$ problem by recursively solving either an $(m-1) \times n$ or an $m \times (n-1)$ subproblem. (Hint: Think about MAX-HEAPIFY.) Define $T(p)$, where $p = m + n$, to be the maximum running time of EXTRACT-MIN on any $m \times n$ Young tableau. Give and solve a recurrence for $T(p)$ that yields the $O(m + n)$ time bound.
d. Show how to insert a new element into a nonfull $m \times n$ Young tableau in $O(m + n)$ time.
e. Using no other sorting method as a subroutine, show how to use an $n \times n$ Young tableau to sort $n^2$ numbers in $O(n^3)$ time.
f. Give an $O(m+n)$-time algorithm to determine whether a given number is stored in a given $m \times n$ Young tableau.
Solution:
a.
There are other answers.
b.
$Y[1, 1] = \infty$
If there are some element in $Y$, it should be larger than $\infty$. That's a contradiction.
$Y[m, n] < \infty$
If $Y$ is not full, then there should be some elements which is $\infty$. But $Y[m, n] < \infty$, it is a contradiction.
c.
@{
\proc{Young-Tableau-Extract-Min}(Y, m, n)
\li min = Y[1, 1]
\li Y[1, 1] = \infty
\li \proc{Young-Tableau-Min-Heapify}(Y, 1, 1, m, n)
\li \Return min
}@
We can see that in the worst-case, the item in $Y[1, 1]$ has to be moved to $Y[m, n]$. There are m movements in vertical direction and n movements in horizontal direction. Each time we call YOUNG-TABLEAU-MIN-HEAPIFY, it will decrease one movement, therefore, its running time is $O(m + n)$. We can express the equation in such form:
$T(p) \leq T(p - 1) + \Theta(1) \Rightarrow T(p) = O(p)$
d.
@{
\proc{Young-Tableau-Insert-Bottom-Up}(Y, i, j, m, n)
\li \If i - 1 \geq 1\;\textup{and}\;Y[i -1 , j] > Y[i, j]
\li \;\;\;\;largest = [i - 1, j]
\li \Else
\li \;\;\;\;largest = [i , j]
\li \If j - 1 \geq 1 \;\textup{and}\;Y[i, j - 1] < Y[largest]
\li \;\;\;\;largest = [i, j - 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j]\;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Insert-Bottom-Up}(Y, largest, m , n)
}@
@{
\proc{Young-Tableau-Insert}(Y, m, n, key)
\li Y[m, n] = key
\li \proc{Young-Tableau-Insert-Bottom-Up}(Y, m, n, m, n)
}@
We insert an item into Young tableau in a bottom-up manner, and the running time is still $O(m + n)$.
e. Just run YOUNG-TABLEAU-EXTRACT-MIN iteratively for $n^2$ times, we can get the sequence in increasing sorted order. The running time is $n^2O(n + n) = O(n^3)$.
f. Consider the diagonal elements $Y[i, i]$, where $ 1 \leq i \leq min\{m, n\}$. We find the given number in these diagonal elements. If we can find it, it's done, otherwise we get two elemets $Y[j, j]$ and $Y[j+1, j+1]$ such that $Y[j, j] < x < Y[j+1, j+1]$, where x is the given number. Note that every $Y[p, q]$ where $j+1 \leq p$ and $j+1 \leq q$ are greater than $Y[j+1, j+1]$ and every $Y[r, s]$ where $r \leq j$ and $s \leq j$ are less than $Y[j, j]$. So we just try to search the other two blocks recursively. The running time can be written as:
$T(p) = 2T(p/2) + O(\log p)$
Using master theorem, we can derive that $T(p) = O(m + n)$
The procdure BUILD-MAX-HEAP in section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:
a. Do the procedure BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build an n-element heap.
Solution:
a. Given an array A = <2, 3, 1, 4, 5>, procedure BUILD-MAX-HEAP will give the output A = <5, 4, 1, 2, 3> and procedure BUILD-MAX-HEAP' will give the output A = <5, 4, 1, 3, 2>
b.Obviously, the upper bound is $O(n \lg n)$ due to calling procedure MAX-HEAP-INSERT (n-1) times. For the lower bound, consider the worst case which is input in increasing order. Each inserted item goes along a path from leaf to root. Since the depth is $\lfloor \lg i \rfloor$, the total time is:
$\sum_{i = 1}^{n-1} \Theta(\lfloor \lg i \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg \lceil n/2\rceil \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n/2) \rfloor)$
$ = \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n) - 1 \rfloor) \geq n/2 \cdot \Theta(\lg n) = \Omega(n \lg n)$
Thus, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build a n-element heap.
Problem 6-2 Analysis of d-ary heaps
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
a. How would you represent a d-ary heap in an array?
b. What is the height of a d-ary heap of n elements in terms of n and d?
c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A, i, k), which first sets A[i] $\leftarrow$ max(A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.
Solution:
a. Given an index i, we want to find its kth-child ($1 \leq k \leq d$). We can view $i = 1 + d + d^2 + \cdots + d^n + p = \frac{d^{n+1} - 1}{d - 1} + p$, where $1 \leq p \leq d^{n+1}$. The index of k-th child of A[i] is:
$i + (d^{n+1} - p) + (p-1)d + k = \frac{d^{n+1} - 1}{d - 1} + p + d^{n+1} - p + (i - \frac{d^{n+1} - 1}{d - 1} - 1)d + k$
$= \frac{d^{n+1} - 1}{d - 1} + d^{n+1} + id - \frac{d^{n + 2} - d}{d - 1} - d + k = id -d + 1 + k$
Therefore, we show how to get the index of k-th child of A[i]. Next we show how to get the index of parent of A[i]. We know nodes A[j] where $id - d + 1 + 1 \leq j \leq id - d + 1 + d$ have the same parent $i$. Trivially we know that $\lfloor \frac{j + (d - 2)}{d}\rfloor$ is the index of their parent.
@{
\proc{Child}(i, k)
\li \Return i \times d - d + 1 + k
}@
@{
\proc{Parent}(i)
\li \Return \lfloor \frac{i + (d - 2)}{d}\rfloor
}@
\proc{Child}(i, k)
\li \Return i \times d - d + 1 + k
}@
@{
\proc{Parent}(i)
\li \Return \lfloor \frac{i + (d - 2)}{d}\rfloor
}@
b. Let h be the height of a d-ary heap of n elements. Then we can obtain:
$1 + d + d^2 + \cdots + d^{h-1} +1 \leq n \leq 1 + d + d^2 + \cdots + d^h$
$\Rightarrow \frac{d^h - 1}{d - 1} < n \leq \frac{d^{h+1} - 1}{d - 1}$
$\Rightarrow d^h - 1 < (d - 1)n \leq d^{h + 1} - 1$
$\Rightarrow d^h \leq (d-1)n < d^{h+1}$
$\Rightarrow h \leq \log_d ((d-1)n) < h + 1$
$\Rightarrow h = \lfloor \log_d (d-1)n \rfloor$
c. We can develop a generalized version of EXTRACT-MAX in a manner as binary version. However, it should compare all its d children instead of 2 children.
@{
\proc{D-Ary-Max-Heapify}(A, i)
\li largest = i
\li \For j = 1 \;\textbf{to}\;k
\li \;\;\;\;p = i \times d - d + 1 + j
\li \;\;\;\;\If A[p] > A[largest]
\li \;\;\;\;\;\;\;\;largest = p
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \proc{D-Ary-Max-Heapify}(A, largest)
}@
\proc{D-Ary-Max-Heapify}(A, i)
\li largest = i
\li \For j = 1 \;\textbf{to}\;k
\li \;\;\;\;p = i \times d - d + 1 + j
\li \;\;\;\;\If A[p] > A[largest]
\li \;\;\;\;\;\;\;\;largest = p
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \proc{D-Ary-Max-Heapify}(A, largest)
}@
@{
\proc{D-Ary-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{D-Ary-Max-Heapify}(A, 1)
\li \Return max
}@
The procedure D-ARY-EXTRACT-MAX implements the EXTRACT-MAX operation. The running time of D-ARY-EXTRACT-MAX is $O(d \log_d (d-1)n)$. Since each time we call D-ARY-MAX-HEAPIFY, it would check all its d children ($O(d)$). In the worst-case, the item will go down to a leaf, so takes $O( \log_d (d-1)n) * O(d) = O(d \log_d (d-1)n)$ time.
d. We can implement a generalized version of INSERT by updating operation PARENT with the operation which we derived in problem a. The running time is $O(\log_d (d-1)n)$
e. D-ARY-HEAP-INCREASE-KEY can be implemented as a slight modification of HEAP-INCREASE-KEY. The running time is $O(\log_d (d-1)n)$.
@{
\proc{D-Ary-Heap-Increase-Key}(A, i, k)
\li A[i] = \textup{max}(A[i], k)
\li \While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}
(i)]
\li i = \proc{Parent}(i)
}@
\proc{D-Ary-Heap-Increase-Key}(A, i, k)
\li A[i] = \textup{max}(A[i], k)
\li \While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}
(i)]
\li i = \proc{Parent}(i)
}@
Problem 6-3 Young tableaus
An $m \times n$ Young tableau is an $m \times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be $\infty$, which we treat as nonexistent element. Thus, a Young tableau can be used to hold $r \leq mn$ finite numbers.
a. Draw a $4 \times 4$ Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.
b. Argue that an $m \times n$ Young tableau Y is empty if $Y[1, 1] = \infty$. Argue that Y is full (contains mn elements) if $Y[m, n] < \infty$.
c. Give an algorithm to implement EXTRACT-MIN on a nonempty $m \times n$ Young tableau that runs in $O(m + n)$ time. Your algorithm should use a recursive subroutine that solves an $m \times n$ problem by recursively solving either an $(m-1) \times n$ or an $m \times (n-1)$ subproblem. (Hint: Think about MAX-HEAPIFY.) Define $T(p)$, where $p = m + n$, to be the maximum running time of EXTRACT-MIN on any $m \times n$ Young tableau. Give and solve a recurrence for $T(p)$ that yields the $O(m + n)$ time bound.
d. Show how to insert a new element into a nonfull $m \times n$ Young tableau in $O(m + n)$ time.
e. Using no other sorting method as a subroutine, show how to use an $n \times n$ Young tableau to sort $n^2$ numbers in $O(n^3)$ time.
f. Give an $O(m+n)$-time algorithm to determine whether a given number is stored in a given $m \times n$ Young tableau.
Solution:
a.
There are other answers.
b.
$Y[1, 1] = \infty$
If there are some element in $Y$, it should be larger than $\infty$. That's a contradiction.
$Y[m, n] < \infty$
If $Y$ is not full, then there should be some elements which is $\infty$. But $Y[m, n] < \infty$, it is a contradiction.
c.
@{
\proc{Young-Tableau-Min-Heapify}(Y, i, j, m, n)
\li \If i + 1 \leq m\;\textup{and}\;Y[i + 1, j] < Y[i, j]
\li \;\;\;\;largest = [i + 1, j]
\li \Else
\li \;\;\;\;largest = [i, j]
\li \If j + 1 \leq n \;\textup{and}\;Y[i, j+ 1] < Y[largest]
\li \;\;\;\;largest = [i, j + 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j] \;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Min-Heapify}(Y, largest, m, n)
}@
\proc{Young-Tableau-Min-Heapify}(Y, i, j, m, n)
\li \If i + 1 \leq m\;\textup{and}\;Y[i + 1, j] < Y[i, j]
\li \;\;\;\;largest = [i + 1, j]
\li \Else
\li \;\;\;\;largest = [i, j]
\li \If j + 1 \leq n \;\textup{and}\;Y[i, j+ 1] < Y[largest]
\li \;\;\;\;largest = [i, j + 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j] \;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Min-Heapify}(Y, largest, m, n)
}@
@{
\proc{Young-Tableau-Extract-Min}(Y, m, n)
\li min = Y[1, 1]
\li Y[1, 1] = \infty
\li \proc{Young-Tableau-Min-Heapify}(Y, 1, 1, m, n)
\li \Return min
}@
We can see that in the worst-case, the item in $Y[1, 1]$ has to be moved to $Y[m, n]$. There are m movements in vertical direction and n movements in horizontal direction. Each time we call YOUNG-TABLEAU-MIN-HEAPIFY, it will decrease one movement, therefore, its running time is $O(m + n)$. We can express the equation in such form:
$T(p) \leq T(p - 1) + \Theta(1) \Rightarrow T(p) = O(p)$
d.
@{
\proc{Young-Tableau-Insert-Bottom-Up}(Y, i, j, m, n)
\li \If i - 1 \geq 1\;\textup{and}\;Y[i -1 , j] > Y[i, j]
\li \;\;\;\;largest = [i - 1, j]
\li \Else
\li \;\;\;\;largest = [i , j]
\li \If j - 1 \geq 1 \;\textup{and}\;Y[i, j - 1] < Y[largest]
\li \;\;\;\;largest = [i, j - 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j]\;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Insert-Bottom-Up}(Y, largest, m , n)
}@
@{
\proc{Young-Tableau-Insert}(Y, m, n, key)
\li Y[m, n] = key
\li \proc{Young-Tableau-Insert-Bottom-Up}(Y, m, n, m, n)
}@
We insert an item into Young tableau in a bottom-up manner, and the running time is still $O(m + n)$.
e. Just run YOUNG-TABLEAU-EXTRACT-MIN iteratively for $n^2$ times, we can get the sequence in increasing sorted order. The running time is $n^2O(n + n) = O(n^3)$.
f. Consider the diagonal elements $Y[i, i]$, where $ 1 \leq i \leq min\{m, n\}$. We find the given number in these diagonal elements. If we can find it, it's done, otherwise we get two elemets $Y[j, j]$ and $Y[j+1, j+1]$ such that $Y[j, j] < x < Y[j+1, j+1]$, where x is the given number. Note that every $Y[p, q]$ where $j+1 \leq p$ and $j+1 \leq q$ are greater than $Y[j+1, j+1]$ and every $Y[r, s]$ where $r \leq j$ and $s \leq j$ are less than $Y[j, j]$. So we just try to search the other two blocks recursively. The running time can be written as:
$T(p) = 2T(p/2) + O(\log p)$
Using master theorem, we can derive that $T(p) = O(m + n)$
2010年6月18日 星期五
[Algo] Exercise 6.5
Exercise 6.5-3
Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
@{
\proc{Heap-Decrease-Key}(A, i, key)
\li \If key > A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is larger than current key"}
\li A[i] = key
\li \While i > 1 \;\textup{and}\;A[\proc{Parent}](i) > A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;i = \proc{Parent}(i)
}@
@{
\proc{Min-Heap-Insert}(A, key)
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li A[\textit{heap-size}[A]] = \infty
\li \proc{Heap-Decrease-Key}(A, \textit{heap-size}[A], key)
}@
Exercise 6.5-4
Why do we bother setting the key of the inserted node to $-\infty$ in line 2 of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
To make sure that the inserted value is at least as large as current key value.
Exercise 6.5-6
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
FIFO queue：when an element is inserted, it is given a value according to the inserting order. The later the element is inserted, the larger the value is given. Then we can implement a FIFO queue with a min-priority queue.
stack：Just like FIFO queue, when an element is inserted, it is given a value according to the inserting order. Then we can implement a stack with a max-priority queue.
Exercise 6.5-7
The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in $O(\lg n)$ time for an n-element max-heap.
We assume that index i is never out of array boundary. The idea is we copy the value of A[heap-size[A]] to the deleted node A[i]. It may violate the heap priority, so we adopt the idea of HEAP-INCREASE-KEY. Otherwise, we call MAX-HEAPIFY to make the heap-priority hold.
Exercise 6.5-8
Give an $O(n \lg k)$-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)
We extract the 1st element from all k sorted lists to build a k-element heap. Then we call EXTRACT-MIN to obtain the smallest element, and extract the 2nd element from the list where the smallest element came from into the heap. After inserting a new element into the heap, we call MIN-HEAPIFY to make the min-heap priority hold. Continuing the process can yield a sorted list. The running time is clearly $nO(\lg k) = O(n \lg k)$.
Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
@{
\proc{Heap-Minimum}(A)
\li \Return A[1]
}@
\proc{Heap-Minimum}(A)
\li \Return A[1]
}@
@{
\proc{Heap-Extract-Min}(A)
\li \If \textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li min = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{Min-Heapify}(A, 1)
\li \Return min
}@
\proc{Heap-Extract-Min}(A)
\li \If \textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li min = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{Min-Heapify}(A, 1)
\li \Return min
}@
@{
\proc{Heap-Decrease-Key}(A, i, key)
\li \If key > A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is larger than current key"}
\li A[i] = key
\li \While i > 1 \;\textup{and}\;A[\proc{Parent}](i) > A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;i = \proc{Parent}(i)
}@
@{
\proc{Min-Heap-Insert}(A, key)
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li A[\textit{heap-size}[A]] = \infty
\li \proc{Heap-Decrease-Key}(A, \textit{heap-size}[A], key)
}@
Exercise 6.5-4
Why do we bother setting the key of the inserted node to $-\infty$ in line 2 of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
To make sure that the inserted value is at least as large as current key value.
Exercise 6.5-6
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
FIFO queue：when an element is inserted, it is given a value according to the inserting order. The later the element is inserted, the larger the value is given. Then we can implement a FIFO queue with a min-priority queue.
stack：Just like FIFO queue, when an element is inserted, it is given a value according to the inserting order. Then we can implement a stack with a max-priority queue.
Exercise 6.5-7
The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in $O(\lg n)$ time for an n-element max-heap.
We assume that index i is never out of array boundary. The idea is we copy the value of A[heap-size[A]] to the deleted node A[i]. It may violate the heap priority, so we adopt the idea of HEAP-INCREASE-KEY. Otherwise, we call MAX-HEAPIFY to make the heap-priority hold.
@{
\proc{Heap-Delete}(A, i)
\li A[i] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li key = A[i]
\li \If key < A[\proc{Parent}(i)]
\li \;\;\;\;\proc{Max-Heapify}(A, i)
\li \Else
\li \;\;\;\;\While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < key
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;\;\;\;\;i = \proc{Parent}(i)
}@
\proc{Heap-Delete}(A, i)
\li A[i] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li key = A[i]
\li \If key < A[\proc{Parent}(i)]
\li \;\;\;\;\proc{Max-Heapify}(A, i)
\li \Else
\li \;\;\;\;\While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < key
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;\;\;\;\;i = \proc{Parent}(i)
}@
Exercise 6.5-8
Give an $O(n \lg k)$-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)
We extract the 1st element from all k sorted lists to build a k-element heap. Then we call EXTRACT-MIN to obtain the smallest element, and extract the 2nd element from the list where the smallest element came from into the heap. After inserting a new element into the heap, we call MIN-HEAPIFY to make the min-heap priority hold. Continuing the process can yield a sorted list. The running time is clearly $nO(\lg k) = O(n \lg k)$.
2010年6月17日 星期四
[Algo] 6.5 Priority queues
priority queue
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.
max-priority queue operations
INSERT(S, x)：insert the element x into the set S ($S \leftarrow S \cup \{x\}$)
MAXIMUM(S)：returns the element of S with the largest key
EXTRACT-MAX(S)：removes and returns the element of S with the largest key
INCREASE-KEY(S, x, k)：increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value
max-priority implementation
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.
max-priority queue operations
INSERT(S, x)：insert the element x into the set S ($S \leftarrow S \cup \{x\}$)
MAXIMUM(S)：returns the element of S with the largest key
EXTRACT-MAX(S)：removes and returns the element of S with the largest key
INCREASE-KEY(S, x, k)：increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value
max-priority implementation
@{
\proc{Heap-Maximum}(A)
\li \Return A[1]
}@
HEAP-MAXIMUM 可以實做 MAXIMUM，而且 running time 是 $\Theta(1)$\proc{Heap-Maximum}(A)
\li \Return A[1]
}@
@{
\proc{Heap-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{Max-Heapify}(A, 1)
\li \Return max
}@
HEAP-EXTRACT-MAX 可以實做 EXTRACT-MAX，running time 是 $O(\lg n)$\proc{Heap-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{Max-Heapify}(A, 1)
\li \Return max
}@
@{
\proc{Heap-Increase-Key}(A, i, key)
\li \If key < A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is smaller than current key"}
\li A[i] = key
\li \While i > 1 \;\textup{and}\;A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;i = \proc{Parent}(i)
}@
\proc{Heap-Increase-Key}(A, i, key)
\li \If key < A[i]
\li \;\;\;\;\textbf{error}\;\textup{"new key is smaller than current key"}
\li A[i] = key
\li \While i > 1 \;\textup{and}\;A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}(i)]
\li \;\;\;\;i = \proc{Parent}(i)
}@
HEAP-INCREASE-KEY 可以實做 INCREASE-KEY。因為 A[i] 的 value 被增加後可能會破壞掉原本 max-heap 的架構，所以我們應該重新再 heapify 一次，但是這邊採用比較簡單的作法，如果 A[i] 比 A[PARENT(i)] 還大的話，那我們就交換 A[i] 跟 A[PARENT(i)]，由下往上比對上去，所以最多只要比對到 root 而已，所以 running time 是 $O(\lg n)$。
@{
\proc{Max-Heap-Insert}(A, key)
\li \textit{heap-size}[A] = \textit{heap-size}[A] + 1
\li A[\textit{heap-size}[A]] = -\infty
\li \proc{Heap-Increase-Key}(A, \textit{heap-size}[A], key)
}@
\proc{Max-Heap-Insert}(A, key)
\li \textit{heap-size}[A] = \textit{heap-size}[A] + 1
\li A[\textit{heap-size}[A]] = -\infty
\li \proc{Heap-Increase-Key}(A, \textit{heap-size}[A], key)
}@
MAX-HEAP-INSERT 可以實做 INSERT。running time 是 $O(\lg n)$。
[Algo] Exercise 6.4
Exercise 6.4-3
What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?
increasing order: Even though it is in increasing order, it must be trasnformed into a max-heap. And each time we call MAX-HEAPIFY it must traverse from the root to leaves, so it takes $O(n\lg n)$ time to run heapsort.
decreasing order: Though it takes less time to run BUILD-MAX-HEAP, but it still takes $O(\lg n)$ time to call MAX-HEAPIFY. Thus it takes $O(n \lg n)$ time to run heapsort.
Exercise 6.4-4
Show that the worst-case running time of heapsort is $\Omega(n \lg n)$.
HEAPSORT 的 worst-case 發生在第 5 行反覆 call MAX-HEAPIFY 的時候 MAX-HEAPIFY都是 worst-case，根據 Exercise 6.2-6，MAX-HEAPIFY 的 worst-case running time 是 $\Omega(\lg n)$，所以 HEAPSORT 的 worst-case running time is $\Omega(n \lg n)$。
Exercise 6.4-5
Show that when all elements are distinct, the best-case running timeof heapsort is $\Omega(n \lg n)$.
What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?
increasing order: Even though it is in increasing order, it must be trasnformed into a max-heap. And each time we call MAX-HEAPIFY it must traverse from the root to leaves, so it takes $O(n\lg n)$ time to run heapsort.
decreasing order: Though it takes less time to run BUILD-MAX-HEAP, but it still takes $O(\lg n)$ time to call MAX-HEAPIFY. Thus it takes $O(n \lg n)$ time to run heapsort.
Exercise 6.4-4
Show that the worst-case running time of heapsort is $\Omega(n \lg n)$.
HEAPSORT 的 worst-case 發生在第 5 行反覆 call MAX-HEAPIFY 的時候 MAX-HEAPIFY都是 worst-case，根據 Exercise 6.2-6，MAX-HEAPIFY 的 worst-case running time 是 $\Omega(\lg n)$，所以 HEAPSORT 的 worst-case running time is $\Omega(n \lg n)$。
Exercise 6.4-5
Show that when all elements are distinct, the best-case running timeof heapsort is $\Omega(n \lg n)$.
2010年6月16日 星期三
[Algo] 6.4 The heapsort algorithm
heapsort的原理
我們有了 BUILD-MAX-HEAP 這個 subroutine 之後，因為 max-heap property，A[1] 一定是最大的 element，所以拿掉 A[1] 之後，我們再次把它建構成一個 max-heap 就可以得到第二大的 element，藉由這樣的方法我們就可以依序得到由大到小的排序了。
heapsort 的 pseudocode
@{
\proc{Heapsort}(A)
\li \proc{Build-Max-Heap}(A)
\li \For i = \;\textit{length}[A] \;\textbf{downto}\;2
\li \;\;\;\;\textup{exchange}\;A[1]\;\textup{and}\;A[i]
\li \;\;\;\;\textit{heap-size}[A] = \;\textit{heap-size}[A] - 1
\li \;\;\;\;\proc{Max-Heapify}(A, 1)
}@
heapsort 的 running time
BUILD-MAX-HEAP 花費 $O(n)$ 的時間，接著 $n-1$ 次的 MAX-HEAPIFY，總共花費 $O(n \lg n)$ 的時間。
我們有了 BUILD-MAX-HEAP 這個 subroutine 之後，因為 max-heap property，A[1] 一定是最大的 element，所以拿掉 A[1] 之後，我們再次把它建構成一個 max-heap 就可以得到第二大的 element，藉由這樣的方法我們就可以依序得到由大到小的排序了。
heapsort 的 pseudocode
@{
\proc{Heapsort}(A)
\li \proc{Build-Max-Heap}(A)
\li \For i = \;\textit{length}[A] \;\textbf{downto}\;2
\li \;\;\;\;\textup{exchange}\;A[1]\;\textup{and}\;A[i]
\li \;\;\;\;\textit{heap-size}[A] = \;\textit{heap-size}[A] - 1
\li \;\;\;\;\proc{Max-Heapify}(A, 1)
}@
heapsort 的 running time
BUILD-MAX-HEAP 花費 $O(n)$ 的時間，接著 $n-1$ 次的 MAX-HEAPIFY，總共花費 $O(n \lg n)$ 的時間。
[Algo] Exercise 6.3
Exercise 6.3-2
Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from $\lfloor length[A]/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor length[A]/2 \rfloor$?
When MAX-HEAPIFY is called, it is assumed that the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps. If we call MAX-HEAPIFY starting from 1, we cannot guarantee that the binary tree rooted at A[2] and the binary tree rooted at A[3] are both max-heaps. Apparently we violate the assumption of MAX-HEAPIFY.
Exercise 6.3-3
Show that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height h in any n-element heap.
我們用歸納法的方式來證明。
當 h = 0 時，根據 Exercise 6.1-7，我們知道 leaf 的 index 是從 $\lfloor n/2 \rfloor + 1$ 到 n，所以總共有 $n - (\lfloor n/2 \rfloor + 1) + 1 = n - \lfloor n/2 \rfloor \leq \frac{n + 1}{2} \leq \lceil n/2 \rceil$ 個 leaves，很明顯符合題目的要求。
Let $S_h$ be the # of nodes of height h，而且假設 h = k 時原式是成立的。
$\Rightarrow S_{k+1} = \lceil \frac{S_k}{2} \rceil \leq \lceil \frac{n/2^{k+1}}{2}\rceil = \lceil \frac{n}{2^{k+2}} \rceil$
顯然，我們可以從 $S_k$ 成功推導到 $S_{k+1}$。最後當 $h = \lfloor \lg n \rfloor$ 時，因為 $2^h \leq n \leq 2^{h+1} - 1$，所以 $\lceil n/2^{h+1} \rceil \leq \lceil \frac{2^{h+1}-1}{2^{h+1}} \rceil \leq 1$，代表當 h 最後等於 $\lfloor \lg n \rfloor$ 時，原式依然是成立的。所以我們可以成功證明題目所要求的。
Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from $\lfloor length[A]/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor length[A]/2 \rfloor$?
When MAX-HEAPIFY is called, it is assumed that the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps. If we call MAX-HEAPIFY starting from 1, we cannot guarantee that the binary tree rooted at A[2] and the binary tree rooted at A[3] are both max-heaps. Apparently we violate the assumption of MAX-HEAPIFY.
Exercise 6.3-3
Show that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height h in any n-element heap.
我們用歸納法的方式來證明。
當 h = 0 時，根據 Exercise 6.1-7，我們知道 leaf 的 index 是從 $\lfloor n/2 \rfloor + 1$ 到 n，所以總共有 $n - (\lfloor n/2 \rfloor + 1) + 1 = n - \lfloor n/2 \rfloor \leq \frac{n + 1}{2} \leq \lceil n/2 \rceil$ 個 leaves，很明顯符合題目的要求。
Let $S_h$ be the # of nodes of height h，而且假設 h = k 時原式是成立的。
$\Rightarrow S_{k+1} = \lceil \frac{S_k}{2} \rceil \leq \lceil \frac{n/2^{k+1}}{2}\rceil = \lceil \frac{n}{2^{k+2}} \rceil$
顯然，我們可以從 $S_k$ 成功推導到 $S_{k+1}$。最後當 $h = \lfloor \lg n \rfloor$ 時，因為 $2^h \leq n \leq 2^{h+1} - 1$，所以 $\lceil n/2^{h+1} \rceil \leq \lceil \frac{2^{h+1}-1}{2^{h+1}} \rceil \leq 1$，代表當 h 最後等於 $\lfloor \lg n \rfloor$ 時，原式依然是成立的。所以我們可以成功證明題目所要求的。
[Algo] 6.3 Building a heap
Building max-heap
一旦我們有了 MAX-HEAPIFY 這個 subroutine 之後，我們就可以把一個 array 建造成一個 max-heap。因為 MAX-HEAPIFY(A, i) 需要 A[i] 下面的兩個 child 都是 max-heap，所以我們一定得採取 bottom-up 的方式來建造 max-heap。
根據 Exercise 6.1-7，我們可以知道從 $\lfoor n/2 \rfloor + 1$ 到 n 都是 leaves，所以我們可以把每個 leaf 都當作一個長度為 1 的 heap，這樣我們就可以 call MAX-HEAPIFY了。
Running time
在分析 BUILD-MAX-HEAP 之前，根據 Exercise 6.3-3 告訴我們：一個 n-element heap 最多只有$\lceil n/2^{h+1} \rceil$個 node 的 height 為 h，證明的部份我們稍後再提。
因為 MAX-HEAPIFY 的 running time 為$O(h)$，所以整個 BUILD-MAX-HEAP 的 running time 我們可以整理成這樣：
$\sum_{h = 0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h})$
因為$\sum_{h = 0}^\infty \frac{h}{2^h} = \frac{1/2}{(1 - 1/2)^2} = 2$，所以 BUILD-MAX-HEAP 的 running time 可以表達成$O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h}) = O(n\sum_{h = 0}^\infty \frac{h}{2^h}) = O(n)$，是個 linear time 的 subroutine。
一旦我們有了 MAX-HEAPIFY 這個 subroutine 之後，我們就可以把一個 array 建造成一個 max-heap。因為 MAX-HEAPIFY(A, i) 需要 A[i] 下面的兩個 child 都是 max-heap，所以我們一定得採取 bottom-up 的方式來建造 max-heap。
@{
\proc{Build-Max-Heap}(A)
\li \textit{heap-size}[A] = \;\textit{length}[A]
\li \For i = \lfloor length[A]/2 \rfloor \;\textbf{downto}\; 1
\li \;\;\;\;\proc{Max-Heapify}(A, i)
}@
\proc{Build-Max-Heap}(A)
\li \textit{heap-size}[A] = \;\textit{length}[A]
\li \For i = \lfloor length[A]/2 \rfloor \;\textbf{downto}\; 1
\li \;\;\;\;\proc{Max-Heapify}(A, i)
}@
根據 Exercise 6.1-7，我們可以知道從 $\lfoor n/2 \rfloor + 1$ 到 n 都是 leaves，所以我們可以把每個 leaf 都當作一個長度為 1 的 heap，這樣我們就可以 call MAX-HEAPIFY了。
Running time
在分析 BUILD-MAX-HEAP 之前，根據 Exercise 6.3-3 告訴我們：一個 n-element heap 最多只有$\lceil n/2^{h+1} \rceil$個 node 的 height 為 h，證明的部份我們稍後再提。
因為 MAX-HEAPIFY 的 running time 為$O(h)$，所以整個 BUILD-MAX-HEAP 的 running time 我們可以整理成這樣：
$\sum_{h = 0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h})$
因為$\sum_{h = 0}^\infty \frac{h}{2^h} = \frac{1/2}{(1 - 1/2)^2} = 2$，所以 BUILD-MAX-HEAP 的 running time 可以表達成$O(n\sum_{h = 0}^{\lfloor \lg n \rfloor} \frac{h}{2^h}) = O(n\sum_{h = 0}^\infty \frac{h}{2^h}) = O(n)$，是個 linear time 的 subroutine。
2010年6月9日 星期三
[Algo] Exercise 6.2
Exercise 6.2-2
Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?
@{
\proc{Min-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \;\textit{heap-size}[A]\;\textup{and}\;A[l] < A[i]
\li \;\;\;\;smallest = l
\li \Else
\li \;\;\;\;smallest = i
\li \If r \leq \;\textit{heap-size}[A]\;\textup{and}\;A[r] < A[smallest]
\li \;\;\;\;smallest = r
\li \If smallest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[smallest]
\li \;\;\;\;\proc{Min-Heapify}(A, smallest)
}@
Its running time is the same as subroutine MAX-HEAPIFY, $O(\lg n)$
Exercise 6.2-3
What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?
It will do nothing, because it satisfies the max-heap property.
Exercise 6.2-4
What is the effect of calling MAX-HEAPIFY(A, i) for i > heap-size[A]/2?
From exercise 6.1-7, we know they are leaves of the heap, and for a leaf, there is no child. MAX-HEAPIFY will do nothing and just return.
Exercise 6.2-5
The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
@{
\proc{Iterative-Max-Heapify}(A, i)
\li \While i \leq \;\textit{heap-size}[A]
\li \;\;\;\;l = \proc{Left}(i)
\li \;\;\;\;r = \proc{Right}(i)
\li \;\;\;\;\If l \leq \;\textit{heap-size}[A] \;\textup{and}\; A[l] > A[i]
\li \;\;\;\;\;\;\;\;largest = l
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;largest = i
\li \;\;\;\;\If r \leq \;\textit{heap-size}[A] \;\textup{and}\; A[r] > A[largest]
\li \;\;\;\;\;\;\;\;largest = r
\li \;\;\;\;\If largest \not= i
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;\textup{break the loop}
}@
Exercise 6.2-6
Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is $\Omega(\lg n)$. (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)
For a heap with n nodes, the worst-case is that a node value causing MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf. The running time is $\Theta(1)$ for fixing up the relationships among the elements A[i], A[LEFT(i)] and A[RIGHT(i)]. If the height of a heap is h, the running time is $(h + 1)\cdot\Theta(1) = \Theta(h) = \Theta(\lg n)$. So we prove that it requires $\Omega(\lg n)$ time.
Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?
@{
\proc{Min-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \;\textit{heap-size}[A]\;\textup{and}\;A[l] < A[i]
\li \;\;\;\;smallest = l
\li \Else
\li \;\;\;\;smallest = i
\li \If r \leq \;\textit{heap-size}[A]\;\textup{and}\;A[r] < A[smallest]
\li \;\;\;\;smallest = r
\li \If smallest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[smallest]
\li \;\;\;\;\proc{Min-Heapify}(A, smallest)
}@
Exercise 6.2-3
What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?
It will do nothing, because it satisfies the max-heap property.
Exercise 6.2-4
What is the effect of calling MAX-HEAPIFY(A, i) for i > heap-size[A]/2?
From exercise 6.1-7, we know they are leaves of the heap, and for a leaf, there is no child. MAX-HEAPIFY will do nothing and just return.
Exercise 6.2-5
The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
@{
\proc{Iterative-Max-Heapify}(A, i)
\li \While i \leq \;\textit{heap-size}[A]
\li \;\;\;\;l = \proc{Left}(i)
\li \;\;\;\;r = \proc{Right}(i)
\li \;\;\;\;\If l \leq \;\textit{heap-size}[A] \;\textup{and}\; A[l] > A[i]
\li \;\;\;\;\;\;\;\;largest = l
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;largest = i
\li \;\;\;\;\If r \leq \;\textit{heap-size}[A] \;\textup{and}\; A[r] > A[largest]
\li \;\;\;\;\;\;\;\;largest = r
\li \;\;\;\;\If largest \not= i
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;\textup{break the loop}
}@
Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is $\Omega(\lg n)$. (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)
For a heap with n nodes, the worst-case is that a node value causing MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf. The running time is $\Theta(1)$ for fixing up the relationships among the elements A[i], A[LEFT(i)] and A[RIGHT(i)]. If the height of a heap is h, the running time is $(h + 1)\cdot\Theta(1) = \Theta(h) = \Theta(\lg n)$. So we prove that it requires $\Omega(\lg n)$ time.
2010年6月8日 星期二
[Algo] 6.2 Maintaining the heap property
MAX-HEAPIFY 的用途
這個 subroutine 是用來整理 heap 裡的 element 位置，讓 heap 遵守 max-heap property。這個 subroutine 的 input 是一個 array A 跟一個 array index i。call 這個 subroutine 的時候是假設以 LEFT(i) 跟 RIGHT(i) 為 root 的 subtree 都是標準的 max-heap，我們要做的就是把 A[i] 這個 node 擺到以它為 root 的 subtree 裡面到一個適當的位置。
這個 subroutine 是用來整理 heap 裡的 element 位置，讓 heap 遵守 max-heap property。這個 subroutine 的 input 是一個 array A 跟一個 array index i。call 這個 subroutine 的時候是假設以 LEFT(i) 跟 RIGHT(i) 為 root 的 subtree 都是標準的 max-heap，我們要做的就是把 A[i] 這個 node 擺到以它為 root 的 subtree 裡面到一個適當的位置。
@{
\proc{Max-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \textit{heap-size}[A] \;\textup{and}\;A[l] > A[i]
\li \;\;\;\;largest = l
\li \Else
\li \;\;\;\;largest = i
\li \If r \leq \textit{heap-size}[A] \;\textup{and}\;A[r] > A[largest]
\li \;\;\;\;largest = r
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\proc{Max-Heapify}(A, largest)
}@
\proc{Max-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \textit{heap-size}[A] \;\textup{and}\;A[l] > A[i]
\li \;\;\;\;largest = l
\li \Else
\li \;\;\;\;largest = i
\li \If r \leq \textit{heap-size}[A] \;\textup{and}\;A[r] > A[largest]
\li \;\;\;\;largest = r
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\proc{Max-Heapify}(A, largest)
}@
MAX-HEAPIFY 的圖解
MAX-HEAPIFY 的精神
一開始先比較A[i], A[LEFT(i)], A[RIGHT(i)]這三者之間誰是最大的，因為 root 必須是這棵 subtree 中最大的 element，所以我們把這三者最大的 node 拿來當作新的 root，當然 A[i] 就往下跳，變成更小的 subtree 的 root 了。這個 subroutine MAX-HEAPIFY 就得以繼續遞迴的 call 下去，整個過程可以看上圖得知。
MAX-HEAPIFY 的 running time
首先在第 1~9 行裡面都是在找出這三者之間的大小關係，所以我們可以把它的 running time 視為$\Theta(1)$。重點是 recurrsively call MAX-HEAPIFY 這個 subroutine 的 running time。worst-case 發生在整棵 tree 是呈現半滿的狀態，而且這某半邊的 subtree 是棵 complete 的 binary tree，這個時候這某半邊的 subtree 的 size 是整棵 tree 的 $2n/3$。所以我們可以得到這個遞迴式：$T(n) \leq T(2n/3) + \Theta(1)$，根據 master theorem，我們可以知道 $T(n) = O(\lg n) = O(h)$
MAX-HEAPIFY 的精神
一開始先比較A[i], A[LEFT(i)], A[RIGHT(i)]這三者之間誰是最大的，因為 root 必須是這棵 subtree 中最大的 element，所以我們把這三者最大的 node 拿來當作新的 root，當然 A[i] 就往下跳，變成更小的 subtree 的 root 了。這個 subroutine MAX-HEAPIFY 就得以繼續遞迴的 call 下去，整個過程可以看上圖得知。
MAX-HEAPIFY 的 running time
首先在第 1~9 行裡面都是在找出這三者之間的大小關係，所以我們可以把它的 running time 視為$\Theta(1)$。重點是 recurrsively call MAX-HEAPIFY 這個 subroutine 的 running time。worst-case 發生在整棵 tree 是呈現半滿的狀態，而且這某半邊的 subtree 是棵 complete 的 binary tree，這個時候這某半邊的 subtree 的 size 是整棵 tree 的 $2n/3$。所以我們可以得到這個遞迴式：$T(n) \leq T(2n/3) + \Theta(1)$，根據 master theorem，我們可以知道 $T(n) = O(\lg n) = O(h)$
[Algo] Exercise 6.1
Exercise 6.1-1
What are the minimum and maximum numbers of elements in a heap of height h?
(1) minimum
$1 + 2 + 2^2 + \cdots + 2^{h-1} + 1 = \frac{2^h - 1}{2-1} + 1 = 2^h$
(2) maximum
$1 + 2 + 2^2 + \cdots + 2^h = \frac{2^{h+1} - 1}{2-1} = 2^{h+1} - 1$
Exercise 6.1-2
Show that an n-element heap has height $\lfloor \lg n \rfloor$.
Let h be the height of an n-element heap. From exercise 6.1-1, we know $2^h \leq n < 2^{h+1}$. We can obtain $h \leq \lg n < h+1$, thus $h = \lfloor \lg n \rfloor$
Exercise 6.1-3
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occuring anywhere in that subtree.
如果最大的 element 不是出現在 subtree 的 root 的話，那就會違背 max-heap property。
Exercise 6.1-4
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
因為 max-heap property，最小的 node 一定會出現在 leaf 裡面，但不保證是最後一個 leaf。
Exercise 6.1-5
Is an array that is in sorted order a min-heap?
yes, 但是 min-heap 不一定是 in sorted order。
Exercise 6.1-6
Is the sequence <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> a max-heap?
No, 畫圖出來就知道了。6 的 right child 是 7。
Exercise 6.1-7
Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n$.
最後一個 node 必為leaf，而且他的 parent(index: $\lfloor n/2 \rfloor$)必為 array 中最後一個非 leaf 的 node，所以從這個 node 之後的所有 node就是 leaf 了。
What are the minimum and maximum numbers of elements in a heap of height h?
(1) minimum
$1 + 2 + 2^2 + \cdots + 2^{h-1} + 1 = \frac{2^h - 1}{2-1} + 1 = 2^h$
(2) maximum
$1 + 2 + 2^2 + \cdots + 2^h = \frac{2^{h+1} - 1}{2-1} = 2^{h+1} - 1$
Exercise 6.1-2
Show that an n-element heap has height $\lfloor \lg n \rfloor$.
Let h be the height of an n-element heap. From exercise 6.1-1, we know $2^h \leq n < 2^{h+1}$. We can obtain $h \leq \lg n < h+1$, thus $h = \lfloor \lg n \rfloor$
Exercise 6.1-3
Show that in any subtree of a max-heap, the root of the subtree contains the largest value occuring anywhere in that subtree.
如果最大的 element 不是出現在 subtree 的 root 的話，那就會違背 max-heap property。
Exercise 6.1-4
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
因為 max-heap property，最小的 node 一定會出現在 leaf 裡面，但不保證是最後一個 leaf。
Exercise 6.1-5
Is an array that is in sorted order a min-heap?
yes, 但是 min-heap 不一定是 in sorted order。
Exercise 6.1-6
Is the sequence <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> a max-heap?
No, 畫圖出來就知道了。6 的 right child 是 7。
Exercise 6.1-7
Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n$.
最後一個 node 必為leaf，而且他的 parent(index: $\lfloor n/2 \rfloor$)必為 array 中最後一個非 leaf 的 node，所以從這個 node 之後的所有 node就是 leaf 了。
[Algo] 6.1 Heaps
heap 的定義
The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. 這個 heap 不是指 memory layout 中的 heap，在這裡它是個特別的 data structure，但它僅僅是個 array 而已，雖然形狀看起來像棵 binary tree。我們在探討 heap 的特性時是把它想像成一顆 binary tree，但是他儲存的方式是個 array。但是 heap 當然可以是個 d-ary tree，不一定非得要是 binary tree。
heap 的 attribute
令 A 為一個 array 可以用來代表一個 heap，我們可以把 array A 視為一個 object，一個有heap特性的 object，接下來我們來看這個 object 有哪些 attribute：
(1) length[A]：array A 裡面中的 element 的個數
(2) heap-size[A]：array A 中被儲存為 heap 裡面的 element 個數
當然，我們可以從這兩個 attributes 得到一些特性：
(i)heap-size[A] $\leq$ length[A]
以及
(ii)A[1 ... heap-size[A]]裡面的 element 才是 heap 裡面的 element。
heap 的圖解
heap procedurestree 的 root 為 A[1]，給定一個 index i，我們可以得到它的 parent, left child, right child：
@{
\proc{Parent}(i)
\li \Return $\lfloor i/2 \rfloor$
}@
@{
\proc{Left}(i)
\li \Return $2i$
}@
@{
\proc{Right}(i)
\li \Return $2i + 1$
}@
heap property
有兩種不同的 binary heap：
(1) max-heap
(i) max-heap property：for every node other than the root, A[PARENT(i)] $\geq$ A[i]，注意的是左右 sibling 是沒有誰必須大於誰的規定
(ii) root 是整個 heap 裡面最大的 element
(iii) 任何一個 node 底下的 subtree 裡，都是這個 node 的值最大
(2) min-heap
min-heap 基本上跟 max-heap 的性質類似，只不過大小顛倒相反而已。
heap height 的定義
(1) We define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf.
(2) We define the height of the heap to be the height of its root.
所以 heap 的 height 都是由 leaf 往上數上來的，leaf 的 height 都是 0，上圖的 heap 的 height 是 3，值是 8 的那個 node 的 height 是 1。
一個有 n 個 element 的 binary heap，他的 height 是$\Theta(\lg n)$，所有 basic operations 的 running time 都是跟這個 heap 的 height 有關係，所以都是 $O(\lg n)$。
The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. 這個 heap 不是指 memory layout 中的 heap，在這裡它是個特別的 data structure，但它僅僅是個 array 而已，雖然形狀看起來像棵 binary tree。我們在探討 heap 的特性時是把它想像成一顆 binary tree，但是他儲存的方式是個 array。但是 heap 當然可以是個 d-ary tree，不一定非得要是 binary tree。
heap 的 attribute
令 A 為一個 array 可以用來代表一個 heap，我們可以把 array A 視為一個 object，一個有heap特性的 object，接下來我們來看這個 object 有哪些 attribute：
(1) length[A]：array A 裡面中的 element 的個數
(2) heap-size[A]：array A 中被儲存為 heap 裡面的 element 個數
當然，我們可以從這兩個 attributes 得到一些特性：
(i)heap-size[A] $\leq$ length[A]
以及
(ii)A[1 ... heap-size[A]]裡面的 element 才是 heap 裡面的 element。
heap 的圖解
heap procedures
@{
\proc{Parent}(i)
\li \Return $\lfloor i/2 \rfloor$
}@
@{
\proc{Left}(i)
\li \Return $2i$
}@
@{
\proc{Right}(i)
\li \Return $2i + 1$
}@
heap property
有兩種不同的 binary heap：
(1) max-heap
(i) max-heap property：for every node other than the root, A[PARENT(i)] $\geq$ A[i]，注意的是左右 sibling 是沒有誰必須大於誰的規定
(ii) root 是整個 heap 裡面最大的 element
(iii) 任何一個 node 底下的 subtree 裡，都是這個 node 的值最大
(2) min-heap
min-heap 基本上跟 max-heap 的性質類似，只不過大小顛倒相反而已。
heap height 的定義
(1) We define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf.
(2) We define the height of the heap to be the height of its root.
所以 heap 的 height 都是由 leaf 往上數上來的，leaf 的 height 都是 0，上圖的 heap 的 height 是 3，值是 8 的那個 node 的 height 是 1。
一個有 n 個 element 的 binary heap，他的 height 是$\Theta(\lg n)$，所有 basic operations 的 running time 都是跟這個 heap 的 height 有關係，所以都是 $O(\lg n)$。
[Algo] Problem 5
Problem 5-1 Probabilistic counting
With a b-bit counter, we can ordinarily only count up to $2^b - 1$. With R. Morris's probabilistic counting, we can count up to a much larger value at the expense of some loss of precision.
We let a counter value of i represent a count of $n_i$ for $i = 0, 1, \ldots , 2^b-1$, where the $n_i$ form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0, representing a count of $n_0 = 0$. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If $i = 2^b - 1$, then an overflow error is reported. Otherwise, the counter is increased by 1 with probability $1/(n_{i+1} - n_i)$, and it remains unchanged with probability $1 - 1/(n_{i+1} - n_i)$.
If we select $n_i = i$ for all $i \geq 0$, then the counter is an ordinary one. More interesting situations arise if we select, say, $n_i = 2^{i - 1}$ for $i > 0$ or $n_i = F_i$ (the ith Fibonacci number-see Section 3.2).
For this problem, assume that $n_{2^b - 1}$ is large enough that the probability of an overflow error is negligible.
a. Show that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n.
b. The analysis of the variance of the count represented by the counter depends on the sequence of the $n_i$. Let us consider a simple case: $n_i = 100i$ for all $i \geq 0$. Estimate the variance in the value represented by the register after n INCREMENT operations have been performed.
a. 令 $X$ 為經過 n 次 INCREMENT operation 後 counter 所代表的值的 random variable，$X_i$為經過第 i 次 INCREMENT operation 的 counter 所代表值的增加量的random variable。注意：唯有把增加量當作一個 random variable，我們才有辦法利用到$E[X] = E[X_1 + X_2 + \cdots ]$的特性。所以我們可以得到：
 \times \frac{1}{n_2 - n_1} + (n_3 - n_2) \times \frac{1}{n_3 - n_2} + \cdots + (n_{i+1} - n_i) \times \frac{1}{n_{i+1} - n_i}\\ &= 1 + 1 + \cdots + 1\\ &= n \end{align*} "\begin{align*} E[X] &= 0 + E[X_1] + E[X_2] + \cdots + E[X_n]\\ &= (n_2 - n_1) \times \frac{1}{n_2 - n_1} + (n_3 - n_2) \times \frac{1}{n_3 - n_2} + \cdots + (n_{i+1} - n_i) \times \frac{1}{n_{i+1} - n_i}\\ &= 1 + 1 + \cdots + 1\\ &= n \end{align*}")
b. 根據上題我們可以假設類似的條件，令$X$為經過 n 次 INCREMENT operations 後 counter所代表的值的 random variable，$X_i$為經過第 i 次 INCREMENT operation 的 counter 所代表值的增加量的random variable。因為任兩個 random variable $X_i$, $X_j$都是彼此獨立的，所以我們也可以利用這個特性：
$Var(X) = Var(X_1) + Var(X_2) + \cdots + Var(X_n)$ 來計算 $Var(X)$。
 &= E[X_i^2] - E^2[X_i] \\ &= (n_{i+1} - n_i)^2 \cdot \frac{1}{n_{i+1} - n_i} - 1^2 \\ &= 100^2 \cdot \frac{1}{100} - 1 = 99\\ \end{align*} "\begin{align*} Var(X_i) &= E[X_i^2] - E^2[X_i] \\ &= (n_{i+1} - n_i)^2 \cdot \frac{1}{n_{i+1} - n_i} - 1^2 \\ &= 100^2 \cdot \frac{1}{100} - 1 = 99\\ \end{align*}")
 &= Var(X_1) + Var(X_2) + \cdots + Var(X_n)\\ &= 99 + 99 + \cdots + 99 \\ &= 99n \end{align*} "\begin{align*} \Rightarrow Var(X) &= Var(X_1) + Var(X_2) + \cdots + Var(X_n)\\ &= 99 + 99 + \cdots + 99 \\ &= 99n \end{align*}")
Problem 5-2 Searching an unsorted array
This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements.
Consider the following randomized strategy: pick a random index i into A. If $A[i] = x$, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that $A[j] = x$ or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once.
a. Write pseudocode for a procedure RANDOM-SEARCH to implement the strategy above. Be sure that your algorithm terminates when all indices into A have been picked.
b. Suppose that there is exactly one index i such that $A[i] = x$. What is the expected number of indices into A that must be picked before x is found and RANDOM-SEARCH terminates?
c. Generalizing your solution to part (b), suppose that there are $k \geq 1$ indices i such that $A[i] = x$. What is the expected number of indices into A that must be picked before x is found and RANDOM-SEARCH terminates? Your answer should be a function of n and k.
d. Suppose that there are no indices i such that $A[i] = x$. What is the expected number of indices into A that must be picked before all elements of A have been checked and RANDOM-SEARCH terminates?
Now consider a deterministic linear search algorithm, which we refer to as DETERMINISTIC-SEARCH. Specifically, the algorithm searches A for x in order, considering $A[1], A[2], A[3], \ldots, A[n]$ until either $A[i] = x$ is found or the end of the array is reached. Assume that all possible permutations of the input array are equally likely.
e. Suppose that there is exactly one index i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
f. Generalizing your solution to part (e), suppose that there are $k \geq 1$ indices i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH? Your answer should be a function of n and k.
g. Suppose that there are no indices i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuted array.
h. Letting k be the number of indices i such that $A[i] = k$, give the worst-case and expected running times of SCRAMBLE-SEARCH for the cases in which $k = 0$ and $k = 1$. Generalize your solution to handle the case in which $k \geq 1$.
i. Which of the three searching algorithms would you use? Explain your answer.
With a b-bit counter, we can ordinarily only count up to $2^b - 1$. With R. Morris's probabilistic counting, we can count up to a much larger value at the expense of some loss of precision.
We let a counter value of i represent a count of $n_i$ for $i = 0, 1, \ldots , 2^b-1$, where the $n_i$ form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0, representing a count of $n_0 = 0$. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If $i = 2^b - 1$, then an overflow error is reported. Otherwise, the counter is increased by 1 with probability $1/(n_{i+1} - n_i)$, and it remains unchanged with probability $1 - 1/(n_{i+1} - n_i)$.
If we select $n_i = i$ for all $i \geq 0$, then the counter is an ordinary one. More interesting situations arise if we select, say, $n_i = 2^{i - 1}$ for $i > 0$ or $n_i = F_i$ (the ith Fibonacci number-see Section 3.2).
For this problem, assume that $n_{2^b - 1}$ is large enough that the probability of an overflow error is negligible.
a. Show that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n.
b. The analysis of the variance of the count represented by the counter depends on the sequence of the $n_i$. Let us consider a simple case: $n_i = 100i$ for all $i \geq 0$. Estimate the variance in the value represented by the register after n INCREMENT operations have been performed.
a. 令 $X$ 為經過 n 次 INCREMENT operation 後 counter 所代表的值的 random variable，$X_i$為經過第 i 次 INCREMENT operation 的 counter 所代表值的增加量的random variable。注意：唯有把增加量當作一個 random variable，我們才有辦法利用到$E[X] = E[X_1 + X_2 + \cdots ]$的特性。所以我們可以得到：
b. 根據上題我們可以假設類似的條件，令$X$為經過 n 次 INCREMENT operations 後 counter所代表的值的 random variable，$X_i$為經過第 i 次 INCREMENT operation 的 counter 所代表值的增加量的random variable。因為任兩個 random variable $X_i$, $X_j$都是彼此獨立的，所以我們也可以利用這個特性：
$Var(X) = Var(X_1) + Var(X_2) + \cdots + Var(X_n)$ 來計算 $Var(X)$。
Problem 5-2 Searching an unsorted array
This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements.
Consider the following randomized strategy: pick a random index i into A. If $A[i] = x$, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that $A[j] = x$ or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once.
a. Write pseudocode for a procedure RANDOM-SEARCH to implement the strategy above. Be sure that your algorithm terminates when all indices into A have been picked.
b. Suppose that there is exactly one index i such that $A[i] = x$. What is the expected number of indices into A that must be picked before x is found and RANDOM-SEARCH terminates?
c. Generalizing your solution to part (b), suppose that there are $k \geq 1$ indices i such that $A[i] = x$. What is the expected number of indices into A that must be picked before x is found and RANDOM-SEARCH terminates? Your answer should be a function of n and k.
d. Suppose that there are no indices i such that $A[i] = x$. What is the expected number of indices into A that must be picked before all elements of A have been checked and RANDOM-SEARCH terminates?
Now consider a deterministic linear search algorithm, which we refer to as DETERMINISTIC-SEARCH. Specifically, the algorithm searches A for x in order, considering $A[1], A[2], A[3], \ldots, A[n]$ until either $A[i] = x$ is found or the end of the array is reached. Assume that all possible permutations of the input array are equally likely.
e. Suppose that there is exactly one index i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
f. Generalizing your solution to part (e), suppose that there are $k \geq 1$ indices i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH? Your answer should be a function of n and k.
g. Suppose that there are no indices i such that $A[i] = x$. What is the expected running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuted array.
h. Letting k be the number of indices i such that $A[i] = k$, give the worst-case and expected running times of SCRAMBLE-SEARCH for the cases in which $k = 0$ and $k = 1$. Generalize your solution to handle the case in which $k \geq 1$.
i. Which of the three searching algorithms would you use? Explain your answer.
a.
@{
\proc{Random-Search}(A, n, x)
\li check = 0
\li \textup{create arrays}\;C[1..n]
\li \For i = 1 \;\To n
\li \;\;\;\;C[i] = \;\textup{false}
\li \While check \not= n
\li \;\;\;\;index = \proc{Random}(1, n)
\li \;\;\;\;\If A[index] = x
\li \;\;\;\;\;\;\;\;\Return \textup{true}
\li \;\;\;\;\Elif C[index] = \;\textup{false}
\li \;\;\;\;\;\;\;\;C[index] = \;\textup{true}
\li \;\;\;\;\;\;\;\;check = check + 1
\li \Return \textup{false}
}@
b.
^{i-1} \cdot \frac{1}{n} \cdot i\\ &= \frac{1}{n-1}\sum_{i = 1}^\infty (\frac{n-1}{n})^i \cdot i\\ &= \frac{1}{n-1} \cdot \frac{\frac{n-1}{n}}{(1 - \frac{n-1}{n})^2}\;\;\textup{(By Taylor theorem)}\\ &= n \end{align*} "\begin{align*} E[X] &= \sum_{i = 1}^\infty (\frac{n-1}{n})^{i-1} \cdot \frac{1}{n} \cdot i\\ &= \frac{1}{n-1}\sum_{i = 1}^\infty (\frac{n-1}{n})^i \cdot i\\ &= \frac{1}{n-1} \cdot \frac{\frac{n-1}{n}}{(1 - \frac{n-1}{n})^2}\;\;\textup{(By Taylor theorem)}\\ &= n \end{align*}")
c.
^{i-1} \cdot \frac{k}{n} \cdot i\\ &= \frac{k}{n-k}\sum_{i = 1}^\infty i \cdot (\frac{n-k}{n})^i\\ &= \frac{k}{n-k} \cdot \frac{\frac{n-k}{n}}{(1 - \frac{n-k}{n})^2}\;\;\textup{(By Taylor theorem)}\\ &= \frac{n}{k} \end{align*} "\begin{align*} E[X] &= \sum_{i = 1}^\infty (\frac{n-k}{n})^{i-1} \cdot \frac{k}{n} \cdot i\\ &= \frac{k}{n-k}\sum_{i = 1}^\infty i \cdot (\frac{n-k}{n})^i\\ &= \frac{k}{n-k} \cdot \frac{\frac{n-k}{n}}{(1 - \frac{n-k}{n})^2}\;\;\textup{(By Taylor theorem)}\\ &= \frac{n}{k} \end{align*}")
d.
Just like the coupon collector's problem, in order to "collect" each of $n$ different indices, it must acquire approximately $n\ln n$ randomly obtained indices to succeed.
e.
$E[X] = \sum_{i = 1}^n i \cdot \frac{1}{n} = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}$
The worst-case running time of DETERMINISTIC-SEARCH is n.
f.
The expected running time is $\frac{n+1}{k+1}$.(From wikipedia)
The worst case is that all element x are put to the end of array A. So the worst-case running time is $n - k + 1$.
g.
The expected running time of DETERMINISTIC-SEARCH is n. It is the very worst-case.
h.
(1) k = 0
It is the very worst-case, and the expected running time of SCRAMBLE-SEARCH is the sum of the cost of shuffling the array and the cost of running DETERMINISTIC-SEARCH, $n + n = 2n$
(2) k = 1
The worst-case is that x is moved to the end of A after shuffling. The expected running time is $n + \frac{n+1}{2} = \frac{3n + 1}{2}$
(3) generalized case
The worst case is that all x are moved to the end of A after shuffling. The expected running time is $n + \frac{n+1}{k+1}$
@{
\proc{Random-Search}(A, n, x)
\li check = 0
\li \textup{create arrays}\;C[1..n]
\li \For i = 1 \;\To n
\li \;\;\;\;C[i] = \;\textup{false}
\li \While check \not= n
\li \;\;\;\;index = \proc{Random}(1, n)
\li \;\;\;\;\If A[index] = x
\li \;\;\;\;\;\;\;\;\Return \textup{true}
\li \;\;\;\;\Elif C[index] = \;\textup{false}
\li \;\;\;\;\;\;\;\;C[index] = \;\textup{true}
\li \;\;\;\;\;\;\;\;check = check + 1
\li \Return \textup{false}
}@
b.
c.
d.
Just like the coupon collector's problem, in order to "collect" each of $n$ different indices, it must acquire approximately $n\ln n$ randomly obtained indices to succeed.
e.
$E[X] = \sum_{i = 1}^n i \cdot \frac{1}{n} = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}$
The worst-case running time of DETERMINISTIC-SEARCH is n.
f.
The expected running time is $\frac{n+1}{k+1}$.(From wikipedia)
The worst case is that all element x are put to the end of array A. So the worst-case running time is $n - k + 1$.
g.
The expected running time of DETERMINISTIC-SEARCH is n. It is the very worst-case.
h.
(1) k = 0
It is the very worst-case, and the expected running time of SCRAMBLE-SEARCH is the sum of the cost of shuffling the array and the cost of running DETERMINISTIC-SEARCH, $n + n = 2n$
(2) k = 1
The worst-case is that x is moved to the end of A after shuffling. The expected running time is $n + \frac{n+1}{2} = \frac{3n + 1}{2}$
(3) generalized case
The worst case is that all x are moved to the end of A after shuffling. The expected running time is $n + \frac{n+1}{k+1}$
2010年6月1日 星期二
[Algo] Exercise 5.4
Exercise 5.4-1
How many people must there be in a room before the probability that someone has the same birthday as you do is at least 1/2? How many people must there be before the probability that at least two people have a birthday on July 4 is greater than 1/2?
(1)
$1 - (364/365)^{n-1} \geq 1/2 \Rightarrow 1/2 \geq (364/365)^{n-1}$
$\Rightarrow \ln 1/2 \geq (n-1) \ln(364/365) \Rightarrow n-1 \leq \frac{\ln 1/2}{\ln 364/365}$
$n-1 \leq 252.6519\ldots \Rightarrow n \leq 253$
Thus there must be 252 other people such that the probability that someone has the same birthday is at least 1/2.
(2)
用 1 減掉("都沒有人的生日是7/4的機率" + "只有一個人的生日是7/4的機率")就是我們所求：
$1 - (364/365)^n - C^n_1(1/365)(364/365)^{n-1} \geq 1/2$
We can use computer to solve this equation, and while $n \geq 613$ this inequality holds.
Exercise 5.4-2
Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?
By pigeon's rule, we can conclude that at most b + 1 tosses there must be a bin containing two balls. Thus, we can obtain the expected number of ball tosses by the definition:
$E[X] = \sum_{i = 2}^{b + 1}i\mbox{p}(i)$
where i is the number of ball tosses.
We can obtain that $$\mbox{p}(i) = \frac{P^b_{i-1}(i-1)}{b^{i}}$$, and the expected number of ball tosses is
$\sum_{i=2}^{b+1}\frac{P^b_{i-1}\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}\frac{b(b-1)(b-2)\cdots(b-i)\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}(\frac{b}{b})\cdot(\frac{b-1}{b})\cdots(\frac{b-i}{b})\cdot i(i-1)$
Exercise 5.4-3
For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.
The birthday paradox holds even when the birthdays are only pairwise independent. (當裡面有雙胞胎的時候，這時候生日可能就不是獨立事件了) 在分析 birthday paradox 的時候，我們會用到獨立這個條件的只有這個地方：
$\mbox{Pr}\{b_i=b_j\}=\sum_{r=1}^n\mbox{Pr}\{b_i=r\quad\mbox{and}\quad b_j=r\}$
Obviously, it involves only two variables $b_i$ and $b_j$. Thus, pairwise independence is sufficient.
Exercise 5.4-4
How many people should be invited to a party in order to make it likely that there are three people with the same birthday?
Suppose that there are k people invited, and all years have n( = 365) days.
$$\mbox{Pr\{there are exactly 3 people with the same birthday\}} = \frac{n \cdot C^{n-1}_{k-3} \cdot \frac{k!}{3!}}{n^k}$$
$$\mbox{Pr\{there are at least 3 people with the same birthday\}} = 1 - \frac{P^n_k}{n^k} - \frac{n \cdot C^{n-1}_{k-2} \cdot \frac{k!}{2!}}{n^k}$$
Exercise 5.4-5
What is the probability that a k-string over a set of size n is actually a k-permutation? How does this question relate to the birthday paradox?
(1) $$\frac{P^n_k}{n^k} = 1\cdot(\frac{n-1}{n})\cdot(\frac{n-1}{n})\cdots(\frac{n-k+1}{n})$$
(2) n is the days all year have, k is how many people are invited to the party, and k-permutation denotes all people have distinct birthdays, no one has the same birthday as the other's.
Exercise 5.4-6
Suppose that n balls are tossed into n bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?
(1) Let $X$ be the random variable of empty bins. By the linearity property of expected number, we can obtain that$\mbox{E}[X] = \mbox{E}[X_1 + X_2 + \cdots X_n]$, where $X_i$ is the indicator random variable.
$X_i$ = I{bin i is empty}
$\mbox{E}[X_i] = \mbox{Pr}\{$bin i is empty$\} = (\frac{n-1}{n})^n$
$$\Rightarrow\mbox{E}[X]=n\cdot(\frac{n-1}{n})^n=\frac{(n-1)^n}{n^{n-1}}$$
(2) Same as the above, let $X$ be the random variable of bins with exactly one ball, and $X_i$ is the indicator random variable.
$X_i$ = I{bin i contains exactly one ball}
How many people must there be in a room before the probability that someone has the same birthday as you do is at least 1/2? How many people must there be before the probability that at least two people have a birthday on July 4 is greater than 1/2?
(1)
$1 - (364/365)^{n-1} \geq 1/2 \Rightarrow 1/2 \geq (364/365)^{n-1}$
$\Rightarrow \ln 1/2 \geq (n-1) \ln(364/365) \Rightarrow n-1 \leq \frac{\ln 1/2}{\ln 364/365}$
$n-1 \leq 252.6519\ldots \Rightarrow n \leq 253$
Thus there must be 252 other people such that the probability that someone has the same birthday is at least 1/2.
(2)
用 1 減掉("都沒有人的生日是7/4的機率" + "只有一個人的生日是7/4的機率")就是我們所求：
$1 - (364/365)^n - C^n_1(1/365)(364/365)^{n-1} \geq 1/2$
We can use computer to solve this equation, and while $n \geq 613$ this inequality holds.
Exercise 5.4-2
Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?
By pigeon's rule, we can conclude that at most b + 1 tosses there must be a bin containing two balls. Thus, we can obtain the expected number of ball tosses by the definition:
$E[X] = \sum_{i = 2}^{b + 1}i\mbox{p}(i)$
where i is the number of ball tosses.
We can obtain that $$\mbox{p}(i) = \frac{P^b_{i-1}(i-1)}{b^{i}}$$, and the expected number of ball tosses is
$\sum_{i=2}^{b+1}\frac{P^b_{i-1}\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}\frac{b(b-1)(b-2)\cdots(b-i)\cdot i(i-1)}{b^i}$
$=\sum_{i=2}^{b+1}(\frac{b}{b})\cdot(\frac{b-1}{b})\cdots(\frac{b-i}{b})\cdot i(i-1)$
Exercise 5.4-3
For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.
The birthday paradox holds even when the birthdays are only pairwise independent. (當裡面有雙胞胎的時候，這時候生日可能就不是獨立事件了) 在分析 birthday paradox 的時候，我們會用到獨立這個條件的只有這個地方：
$\mbox{Pr}\{b_i=b_j\}=\sum_{r=1}^n\mbox{Pr}\{b_i=r\quad\mbox{and}\quad b_j=r\}$
Obviously, it involves only two variables $b_i$ and $b_j$. Thus, pairwise independence is sufficient.
Exercise 5.4-4
How many people should be invited to a party in order to make it likely that there are three people with the same birthday?
Suppose that there are k people invited, and all years have n( = 365) days.
$$\mbox{Pr\{there are exactly 3 people with the same birthday\}} = \frac{n \cdot C^{n-1}_{k-3} \cdot \frac{k!}{3!}}{n^k}$$
$$\mbox{Pr\{there are at least 3 people with the same birthday\}} = 1 - \frac{P^n_k}{n^k} - \frac{n \cdot C^{n-1}_{k-2} \cdot \frac{k!}{2!}}{n^k}$$
Exercise 5.4-5
What is the probability that a k-string over a set of size n is actually a k-permutation? How does this question relate to the birthday paradox?
(1) $$\frac{P^n_k}{n^k} = 1\cdot(\frac{n-1}{n})\cdot(\frac{n-1}{n})\cdots(\frac{n-k+1}{n})$$
(2) n is the days all year have, k is how many people are invited to the party, and k-permutation denotes all people have distinct birthdays, no one has the same birthday as the other's.
Exercise 5.4-6
Suppose that n balls are tossed into n bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?
(1) Let $X$ be the random variable of empty bins. By the linearity property of expected number, we can obtain that$\mbox{E}[X] = \mbox{E}[X_1 + X_2 + \cdots X_n]$, where $X_i$ is the indicator random variable.
$X_i$ = I{bin i is empty}
$\mbox{E}[X_i] = \mbox{Pr}\{$bin i is empty$\} = (\frac{n-1}{n})^n$
$$\Rightarrow\mbox{E}[X]=n\cdot(\frac{n-1}{n})^n=\frac{(n-1)^n}{n^{n-1}}$$
(2) Same as the above, let $X$ be the random variable of bins with exactly one ball, and $X_i$ is the indicator random variable.
$X_i$ = I{bin i contains exactly one ball}
$\mbox{E}[X_i]=\mbox{Pr}\{$ bin i contains exactly one ball $\}=\frac{(n-1)^{n-1}\cdot n}{n^n}$
$$\Rightarrow\mbox{E}[X]=n\cdot\frac{(n-1)^{n-1}\cdot n}{n^n}=\frac{(n-1)^{n-1}}{n^{n-2}}$$
Exercise 5.4-7
Sharpen the lower bound on streak length by showing that in n flips of a pair coin, the probability is less than $1/n$ that no streak longer than $\lg n - 2\lg\lg n$ consecutive heads occurs.
Exercise 5.4-7
Sharpen the lower bound on streak length by showing that in n flips of a pair coin, the probability is less than $1/n$ that no streak longer than $\lg n - 2\lg\lg n$ consecutive heads occurs.
訂閱：
文章 (Atom)