\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{5} % Homework number
{7} % Week of semester submitted
{1.0} % Version
\SaveIndent%
\HWInstructions{%
\textbf{Submission instructions as in previous %
\underline{%
\href{https://courses.engr.illinois.edu/cs374/fa2017/hw/hw_00.pdf}{homeworks}%
}.}%
\medskip%
\hrule %
\medskip
}
\newcommand{\IsGood}{\AlgorithmI{is{}Good}\xspace}%
\newcommand{\BogiSort}{\AlgorithmI{bog{}i{}Sort}\xspace}
\newcommand{\ksel}{\Algorithm{$k$Select}}%
\newcommand{\InsertionSort}{\Algorithm{Insertion{}Sort}\xspace}
\newcommand{\Arr}{\texttt{A}}%
\newcommand{\ArrB}{\texttt{B}}%
\newcommand{\Select}{\Algorithm{Select}\xspace}%
\begin{questions}[start=13]
\RestoreIndent%
\medskip%
\item \OLDHWProblem{100}{B{}o{}g{}i sort.}{%
Consider the following exciting sorting algorithm. For
simplicity we will assume that $n$ is always some positive
power of $2$ (i.e. $n = 2^i$, for some positive integer
$i > 0$).
\smallskip%
\centerline{%
\AlgorithmBox{%
\BogiSort{}$(\Arr[0\,..\,n-1]):$ \+\+ \\
\If $n \leq 16$ \Then \+ \\
\InsertionSort{}$\Bigl(\Arr\bigl[0\,..\,n-1\bigr]\Bigr)$
\- \\%
\Else
\texttt{/* $n > 16$ */} \+ \\
\For $i \gets 0$ to $2$ \Do \+ \\
\For $j \gets 2$ down to $i$ \Do\+ \\
\BogiSort{}$\Bigl(\Arr\bigl[jn/4 \ldots(j+2)n/4-1\bigr]
\Bigr)$%
}%
}
\begin{questions}
\item \points{25} Prove that \BogiSort actually sorts its
input. (You can assume that all the numbers in the array
$A$ are distinct.)
\item \points{25} State a recurrence (including the base
case(s)) for the number of comparisons executed by
\BogiSort.
\item \points{25} Solve the recurrence, and prove that your
solution is correct. (Your proof should be self contained
and not use off the shelf tools like the master theorem
[puke]).
\item \points{25} Show that the number of \emph{swaps} executed
by \BogiSort is at most $\binom{n}{2}$.
\end{questions}
} {}{}{}{}%
\medskip%
\item \OLDHWProblem{100}{Pick it up.}{%
You are given an array $\Arr$ with $n$ distinct numbers in it,
and another array $\ArrB$ of ranks $i_1 < i_2 < \ldots
\alpha$. Think about
calling \IsGood as being an expensive operation, that your
algorithm should perform as little as possible.
\begin{questions}
\item \points{20} (Easy.) Show how to compute all the
numbers of $\Arr$ that are good using $O( \log n)$ calls to
\IsGood. What is the running time of your algorithm. (Here,
the solution should be short and simpler than what
follows. (Here, short means a few lines.)
\item \points{40} Show how to find all the elements of
$\Arr$ that are good using $O( \log n)$ calls to \IsGood
and with total running time $O(n)$. (The solution here
should be simpler than the algorithm in (C)).
\item \points{40} \IsGood turns out to be better than good!
Given a set $Y$ of numbers, where $\cardin{Y} \leq k$, the
generalized $\IsGood(Y)$, returns to you (in a single call)
for each number of $Y$ whether it is good or not. As a
function of $n$ and $k$ describe an algorithm that
(asymptotically) performs the minimal number of calls to
the improved \IsGood. For full credit your algorithm should
be as fast as possible. What is the running time of your
algorithm? State the recurrences you used to derive your
bounds. (Hint: Look on other problems in this homework.)
\end{questions}
}{}{}{}%
\end{questions}
\HomeworkEnd{}