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:
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)$ 的時間。
訂閱：
文章 (Atom)