Algo HW

gistfile1.md

{ "metadata": { "name": "Algo HW4" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": "6.1-2" }, { "cell_type": "markdown", "metadata": {}, "source": "The assertion is obvious for heaps with height $0$, so we may assume heaps which we are considering have height $\geq 1$.
\nObserve that if there are $m$ nodes in level of height $h-1$, then there are at most $2m$ nodes in level of height $h$. And there is only $1$ node in height $0$ (the root of heap), it decuces that we have $2^h$ nodes in height $h$. Note that any node exists in level of hieght $h$ implies that all levels from $0$ to $h-1$ are full (ie. every node in level of height $< h-1$ has two children). Therefore, a heap with height $h$ has $n = \sum_{k=0}^{h-1}{2^k} + N_h$ nodes, where $1 \leq N_h \leq 2^h$ means number of nodes in level of height $h$. Then we have\n$$2^h = \sum_{k=0}^{h-1}{2^k} + 1 \leq n \leq \sum_{k=0}^{h-1}{2^k} + 2^h = 2^{h+1}-1$$\nThis completes the proof." }, { "cell_type": "markdown", "metadata": {}, "source": "
6-3" }, { "cell_type": "markdown", "metadata": {}, "source": "b.\n
\nLet $A[1...m][1...n]$ be a Young tableau as input data. We may assume that $m \geq 1$ and $n \geq 1$. As the following algorithm, we can observe that we do $1$ swap in Extract-Min, and call Re-Youngnify with a matrix which is either $A[2...m][1...n]$ or $A[1...m][2...n]$. Since Re-Youngnify is recursive and it does at most $1$ recursive function call, the recursive relation of Re-Youngnify's time consumption is either $T(m, n) = \Theta(1) + T(m-1,n)$ or $T(m, n) = \Theta(1) + T(m,n-1)$. It's not difficult to see Re-Youngnify has $O(m+n)$ time complexity and hence Extract-Min also.
\n
\nExtract-Min($A$, $m$, $n$):
\n  min = $A[1][1]$
\n  $A[1][1] = \infty$
\n
\n  // Check $m>1$ for avoiding illegal access
\n  if $m > 1$:
\n    // Check $n>1$ for avoiding illegal access
\n    if $n > 1$:
\n      if $A[1][2] < A[2][1]$:
\n        swap $A[1][2]$, $A[1][1]$
\n        Re-Youngnify( $A$, $1$, $m$, $2$, $n$ )
\n    else:
\n      swap $A[2][1]$, $A[1][1]$
\n      Re-Youngnify( $A$, $2$, $m$, $1$, $n$ )
\n  else:
\n    // Check $n>1$ for avoiding illegal access
\n    if $n > 1$:
\n      swap $A[1][2]$, $A[1][1]$
\n      Re-Youngnify( $A$, $1$, $m$, $2$, $n$ )
\n  return min
\n\n// Input data is $A[p_1...r_1][p_2...r_2]$
\nRe-Youngnify($A$, $p_1$, $r_1$, $p_2$, $r_2$):
\n  // Check range
\n  if $p_1 < r_1$:
\n    if $A[p_1+1][p_2] < A[p_1][p_2]$:
\n      // Check range
\n      if $p_2 < r_2$:
\n        if $A[p_1][p_2+1] < A[p_1+1][p_2]$:
\n          swap $A[p_1][p_2+1]$, $A[p_1][p_2]$
\n          Re-Youngnify( $A$, $p_1$, $r_1$, $p_2+1$, $r_2$ )
\n      else:
\n        swap $A[p_1+1][p_2]$, $A[p_1][p_2]$
\n        Re-Youngnify( $A$, $p_1+1$, $r_1$, $p_2$, $r_2$ )
\n  else:
\n    // Check range
\n    if $p_2 < r_2$:
\n      if $A[p_1][p_2+1] < A[p_1][p_2]$:
\n        swap $A[p_1][p_2+1]$, $A[p_1][p_2]$
\n        Re-Youngnify( $A$, $p_1$, $r_1$, $p_2+1$, $r_2$ )
" }, { "cell_type": "markdown", "metadata": {}, "source": "e.
\nAs our analysis in b. , we can extract the minimal value in $O(m+n)$ time from a $m \times n$ Young's tableau. So, for a $n \times n$ Young's tableau, we can do $n^2$ times extraction in $O( n^2 \cdot (n+n) ) = O(n^3)$ time to get a sorted sequence." }, { "cell_type": "markdown", "metadata": {}, "source": "
7.4-2" }, { "cell_type": "markdown", "metadata": {}, "source": "Observe that the recursive relation of quicksort's time consumption is $T(n) = \Theta(n) + T(n_1) + T(n_2)$ with $n = n_1 + n_2 + 1$, where $\Theta(n)$ term denotes the partition operation. To obtain the best case, it's not difficult to see that the recurrence tree has minimal height with $n_1$, $n_2$ are exactly about $\frac{n}{2}$, ie. $T(n) = \Theta(n) + 2T(\frac{n}{2})$. Therefore, by Master Theorem, we have $T(n) = \Theta(n \lg{n})$, hence $T(n) = \Omega(n \lg{n})$." }, { "cell_type": "markdown", "metadata": {}, "source": "
7-1" }, { "cell_type": "markdown", "metadata": {}, "source": "a.
\nWhen HOARE-PARTITION starts:
\n$x = 13$
\n$i = 0$
\n$j = 13$
\n$A = [13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$

\n\nWhen iteration 1 terminates:
\n$x = 13$
\n$i = 1$
\n$j = 11$
\n$A = [6, 19, 9, 5, 12, 8, 7, 4, 11, 2, 13, 21]$

\n\nWhen iteration 2 terminates:
\n$x = 13$
\n$i = 2$
\n$j = 10$
\n$A = [6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21]$

\n\nWhen iteration 3 terminates:
\n$x = 13$
\n$i = 10$
\n$j = 9$
\n$A = [6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21]$
\nThen the comparison $i<j$ gets FALSE and HOARE-PARTITION return 9." }, { "cell_type": "markdown", "metadata": {}, "source": "b.
\nVariable $i$ starts from $p-1$ and be imposed at least $1$ time increment operation before we do access $A[i]$, so we will never access $A$ with index $i < p$. And, variable $j$ starts from $r+1$ and be imposed at least $1$ time decrement operation before we do access $A[j]$, so we will never access $A$ with index $j > r$. On the other hand, when $i \geq j$, HOARE-PARTITION terminates. If $i$ == $j$, then we get $i \leq r$ and $j \geq p$.\n\nTo complete the proof, observe that (to get clearer explanation, see Initialization and Maintenance parts in d.) there are at least $1$ time decrement operation being imposed on $j$ and $x < A[k]$ for $j+1 \leq k \leq r$, in every loop iteration(loop in lines 4-13). Similarly, there are at least $1$ time increment operation being imposed on $i$ and $A[k] < x$ for $p \leq k \leq i-1$, in every loop iteration(loop in lines 4-13).\n\nIf $i > r$ occurs, we must have $j$ == $r$ (since $i > r \implies A[r] < x$ and $j < r \implies A[r] \geq x$, but they are mutually exclusive), that implies current iteration is the first iteration. But the assignment $x = A[p]$ before loop starts will lead a contradiction. Therefore, we must have $i \leq r$.\n\nOn the other hand, if $j < p$ occurs, we must have $i$ == $p$ (since $j < p \implies A[p] > x$ and $i > p \implies A[p] \leq x$, but they are mutually exclusive), that implies current iteration is the first iteration. But the assignment $x = A[p]$ before loop starts will lead a contradiction. Therefore, we must have $j \geq p$." }, { "cell_type": "markdown", "metadata": {}, "source": "c.
\nAs we have discussed in b. , we already have $p \leq i, j \leq r$, so the only part need to be proved is $j \neq r$.
\nAssuming the return value $j$ is equal to $r$, it implies $i \geq j$ in the final iteration (of loop in lines 4-13), hence $A[p]< x $ and $i$ == $r$. But $A[p] &lt; x$ means the content at index $p$ had been modified and the current iteration (of loop in lines 4-13) is not the first iteration. Since every iteration (of loop in lines 4-13) impose at least $1$ time decrement operation on $j$, we must have $j &lt; r$ and a contradiction occurs. This completes the proof." }, { "cell_type": "markdown", "metadata": {}, "source": "d.
\nWe use loop invariant to prove the assertion.
\n\nLoop Invariant (loop in lines 4-13):
\nAt the start of each loop iteration, $A[k] \leq x$ for $p \leq k \leq i$ and $x \leq A[k]$ for $j \leq k \leq r$.  $()$
\n\nInitialization:
\nWhen the first iteration starts, $()$ holds obviously since $A[p...i]$ and $A[j...r]$ are empty.\n
\n\nMaintenance:
\nLet variable $i$ == $i'$, variable $j$ == $j'$ and $()$ holds for value $i'$, $j'$ when current iteration starts. (Be careful with the meaning difference between variable $i$, $j$ and value of $i$, $j$)\nConsidering the evolution of variable $i$ and the evolution of variable $j$. Variable $i$'s incremental process get paused when $A[i] \geq x$; variable $j$'s decremental process get paused when $A[j] \leq x$. So far, $A[k] \leq x$ for $p \leq k \leq i-1$ and $x \leq A[k]$ for $j+1 \leq k \leq r$ (ie. $()$ holds for $i-1$, $j+1$). If $i \geq j$, then HOARE-PARTITION terminates. If $i &lt; j$, then swap operation occurs and $()$ holds for current value of $i$, $j$ after swap operation.\n
\n\nTermination:
\nWhen the loop terminates, we have $i \geq j$.
\nIn case of $i > j$, $()$ holds for $i-1$, $j+1$ and the assertion follows.\nIn case of $i$ == $j$, $(*)$ holds for $i-1$, $j+1$, combining this with $A[i]$ == $A[j] \leq x$ will complete the proof.
" }, { "cell_type": "markdown", "metadata": {}, "source": "
" } ], "metadata": {} } ] }