[usth/ICT2.1] Algorithm and Data Structures

1 files changed, 143 insertions, 0 deletions

diff --git a/usth/ICT2.1/labwork/5/README.tex b/usth/ICT2.1/labwork/5/README.tex
new file mode 100644
index 0000000..4c71999
--- /dev/null
+++ b/usth/ICT2.1/labwork/5/README.tex
@@ -0,0 +1,143 @@
+\documentclass[a4paper,12pt]{article}
+\usepackage[english,vietnamese]{babel}
+\usepackage{amsmath}
+\usepackage{hyperref}
+\usepackage{lmodern}
+\usepackage{mathtools}
+
+\title{Algorithms and Data Structures\\ Searching and Sorting}
+\author{Nguyễn Gia Phong---BI9-184}
+\date{\dateenglish\today}
+
+\begin{document}
+\maketitle
+\section{Cocktail Shaker Sort}
+The code is implemented following the cocktail shaker sort's
+pseudocode\footnote{\url{https://en.wikipedia.org/wiki/Cocktail\_shaker\_sort\#Pseudocode}}
+with bubble sort's optimization\footnote{\url{https://en.wikipedia.org/wiki/Bubble\_sort\#Optimizing\_bubble\_sort}}
+whose time complexity is analyzed as follows
+
+\subsection{Best Case}
+For the matter of brevity, we consider all operations on the array's $n$ members
+are in constant time ($\Theta(1)$).  If the array is already sorted, after
+the first \verb|while| loop (line 25), \verb|h| is still \verb|low| and thus
+the \verb|do|--\verb|while| loop is broken.  Since the while loop runs from
+\verb|low + size| to \verb|high - size| by \verb|size| steps, the running time
+is \verb|(high - low - size*2)/size + 1| or \verb|nmemb - 1|.  Therefore
+the best case time complexity is $\Omega(n - 1) = \Omega(n)$.
+
+\subsection{Average Case}
+Assume the average case is when the array is uniformly shuffled, that is,
+every permutation has the equal probability to occur.
+
+Given a permutation of an $n$-element array, consider the positive integer
+$k \le n$ that exactly the last $n - k$ members are continuously in the
+correct positions (as in the ascendingly sorted array).  It is obvious that
+for $k = 1$, the array is sorted and the probability of the permutation
+to appear is $1/n!$.  For $1 < k \le n$, if we fix the last $n - k$ members
+in their right places, out of the $k!$ permutations of the first $k$ elements,
+$(k - 1)!$ ones has the $k$-th greatest at the correct place.  Therefore,
+let $X$ be the number that exactly $n - X$ last elements are in
+the right positions, we have
+\[p_X(k) = \begin{dcases}
+  \frac{1}{n!} &\text{if }k = 1\\
+  \frac{k! - (k - 1)!}{n!} &\text{otherwise}
+\end{dcases}\]
+
+Applying this to the first \verb|while| (line 25) with $n$ and $X - 1$ being
+the number of steps from \verb|low| to \verb|high|, before and after
+\verb|high = h| respectively, the expectation of $X$ is
+\begin{align*}
+  \mathbf E[X] &= \sum_{k=1}^n k p_X(k)\\
+  &= \frac{1}{n!} + \sum_{k=2}^n\frac{k!k - k!}{n!}\\
+  &= \frac{1}{n!} + \sum_{k=3}^{n+1}\frac{k!}{n!}
+   - \sum_{k=2}^n\frac{k!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\
+  &= \frac{1}{n!} + \frac{(n+1)!}{n!}
+   - \frac{2!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\
+  &= n + 1 - \sum_{k=1}^n\frac{k!}{n!}\\
+  &= n - \sum_{k=1}^{n-1}\frac{k!}{n!}
+\end{align*}
+
+Hence after line 28, the newly sorted length of the array is
+\[n - \mathbf E[X - 1] = n - \mathbf E[X] + 1
+  = 1 + \sum_{k=1}^{n-1}\frac{k!}{n!} = \Theta(1)\]
+
+Similarly, line 31 to 35 also sort $\Theta(1)$ element(s), thus each iteration
+of the \verb|do|--\verb|while| loop to sort $\Theta(1)$ members. The overall
+average-case time complexity is
+\begin{align*}
+  T(n) &= \begin{dcases}
+    (n - \Theta(1)) + (n - \Theta(1)) + T(n - \Theta(1)) &\text{if }n > 0\\
+    \Theta(1) &\text{otherwise}
+  \end{dcases}\\
+  &= \begin{dcases}
+    2n - \Theta(1) + T(n - \Theta(1)) &\text{if }n > 0\\
+    \Theta(1) &\text{otherwise}
+  \end{dcases}\\
+  &= \Theta(1) + \sum_{k=1}^m(2k - \Theta(1))
+  = 2\sum_{k=1}^m k - \sum_{k=1}^m\Theta(1)
+  = m^2 + m - \sum_{k=1}^m\Theta(1)
+\end{align*}
+where $m$ satisfies
+\begin{multline*}
+  \exists\{f_k\mid k\in 1\,..\,m\} \subset \Theta(1),\,
+  \sum_{k=1}^m f_k(n) = n
+  \Longrightarrow \sum_{k=1}^m\Theta(1) = \Theta(n)
+  \Longrightarrow m = \Theta(n)\\
+  \Longrightarrow T(n) = \Theta\left(n^2\right) + \Theta(n) - \Theta(n)
+  = \Theta\left(n^1\right)
+\end{multline*}
+
+\subsection{Worst Case}
+If the array is reversely sorted, after each first \verb|while| (line 25),
+\verb|high| is decreased by \verb|size|; and after each second
+\verb|while| (line 32), \verb|low| is increased by \verb|size|.
+For \verb|low + size >= high|, it takes \verb|(high-low-size)/size + 1 >> 1|
+or \verb|nmemb / 2| iterations of the \verb|do|--\verb|while| loop (line 23).
+The overall complexity would then be
+\begin{align*}
+  \sum_{k=1}^{\lfloor n/2\rfloor}(n - 2k + 1 + n - 2k)
+  &= \sum_{k=1}^{\lfloor n/2\rfloor}(2n - 4k + 1)\\
+  &= n^2 + 2\left\lfloor\frac{n}{2}\right\rfloor
+  \left(\left\lfloor\frac{n}{2}\right\rfloor + 1\right)
+  + \left\lfloor\frac{n}{2}\right\rfloor\\
+  &= O\left(n^2\right)
+\end{align*}
+
+\section{Merge Sort}
+As usual, the linked list is implemented using classic Lisp's \verb|cons|-cells.
+The program is thus compiled by
+\begin{verbatim}
+cc construct.c Ex2.c -o Ex2
+\end{verbatim}
+
+To keep the implementation concise, memory safety as well as stack limit
+was not considered.
+
+It is trivial that the time complexity of \verb|merge| is $\Theta(n)$ with
+$n$ being the total length of \verb|left| and \verb|right|.  For \verb|msort|,
+the running time of the \verb|while| loop at line 27 is also $\Theta(n)$, where
+n is the length of the input \verb|list|.  The overall time complexity is
+\[T(n) = \begin{dcases}
+  \Theta(1) &\text{if }n \le 1\\
+  \Theta(n) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
+  + T\left(\left\lceil\frac{n}{2}\right\rceil\right) &\text{otherwise}
+\end{dcases}\]
+
+The recurrence can be stated as
+\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)\]
+\pagebreak
+
+By the master theorem\footnote{Let $a \ge 1$ and $b > 1$ be constants,
+and let $T(n)$ be defined on the nonnegative integers by the recurrence
+\[T(n) = aT\left(\frac{n}{b}\right) + \Theta\left(n^{\log_b a}\right)\]
+where $n/b$ is interpreted as either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$,
+then \[T(n) = \Theta\left(n^{\log_b a}\lg n\right)\]},
+\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta\left(n^{\log_2 2}\right)
+= \Theta\left(n^{\log_2 2}\lg n\right) = \Theta(n\lg n)\]
+
+\section{Copying}
+This report along with the source files are licensed under a
+\href{https://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons
+Attribution-ShareAlike 4.0 International License}.
+\end{document}