\documentclass[12pt]{article}
\usepackage{algpseudocode} 
\usepackage{fullpage,url,amssymb,epsfig,color,xspace,tikz,amsmath}
\usetikzlibrary{positioning}
%\usepackage{algpseudocode} 
%\usepackage{algorithmicx}
\usepackage[pdftitle={CS 240 Assignment 2},%
pdfsubject={University of Waterloo, CS 240, Fall 2020},%
pdfauthor={MP}]{hyperref}
\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}
\newcommand{\quesbox}[2]{\begin{center} \framebox[.5\textwidth]{%
\raisebox{-5mm}[0mm][#1]{\begin{minipage}[t]{.45\textwidth}%
{\normalsize\sf #2}{\phantom{ans}}\end{minipage}}} \end{center}}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\renewcommand{\thesubsection}{Problem \arabic{subsection}}
\definecolor{typo}{rgb}{0.75,0,0}
\definecolor{care}{rgb}{0,0,0}
\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS240 Fall 2020}\\
\vspace{2mm}
{\Large\bf Assignment 2}\\
\vspace{3mm}
\textbf{Due Date: Wednesday, Oct 7 at 5pm}
\end{center}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

The integrity of the grade you receive in this course is very important to you and 
the University of Waterloo.  As part of every asessment in this course you must read 
and sign an Academic Integrity Declaration before you start working on the assessment and
submit it \textbf{before the deadline of October 7th} along with your answers to the 
assignment; i.e. \textbf{read, sign and submit A02-AID.txt now or as soon as possible}.
The agreement will indicate what you must do to ensure the integrity of your grade.
If you are having difficulties with the assignment, course staff are there to help
(provided it isn't last minute). \\
~\\
\textbf{The Academic Integrity Declaration must be signed and submitted on time or the
assessment will not be marked.} \\
~\\
Please read
\url{http://www.student.cs.uwaterloo.ca/~cs240/f20/guidelines/guidelines.pdf} for guidelines on submission.  
\textbf{Each question must be submitted individually to MarkUs as a PDF} with the corresponding file names: 
a2q1.pdf, a2q2.pdf, ... , a2q6.pdf . \\
~\\
It is a good idea to submit questions as you go so you aren't trying to create several PDF files at the last minute.
\textbf{Remember, late assignments will not be marked.} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 1
\subsection{[3+3=6 marks]}

\begin{itemize}
\part{a}
Given a heap $H$, suppose we want to search for an item with key $k$ and
minimize (as best we can) the number of entries we check for key $k$.
\begin{itemize}
\item[i)]Describe an efficient algorithm {\textit{heapSearch(H, k)}} that 
searches $H$ for $k$ and returns the index where $k$ is found or $-1$ if not found. 
If the heap contains multiple entries with key $k$, any index where the item has key $k$ is okay.
\item[ii)]For your algorithm, give a lower bound on the best-case runtime and a 
lower bound on the worse-case runtime. Briefly justify the runtimes.
\item[iii)]Are the lower bounds from part ii) actually tight (i.e. the same as the corresponding upper bounds)?
Briefly justify your answer. 
\end{itemize}
\part{b}
Given a heap $H$, suppose we want to remove an {\textit{arbitrary}} item at index $i$.
Describe an efficient algorithm {\textit{heapRemove(H, i)}} that removes the item at index $i$ from heap $H$.
State and justify the algorithm's runtime.

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 2
\subsection{[6 marks]}
Generalize $quickSelect1$ to work on two input arrays. Let the resulting algorithm be called $quickSelect2Arrays(A,B,k)$.
Arrays $A$ and $B$ are of size $n$ and $m$, respectively, and $k\in \{ 0,1,...,n+m-1 \}$. Algorithm $quickSelect2Arrays(A,B,k)$
should return the item that would be in $C[k]$ if $C$ was the array  resulting
from merging arrays $A$ and $B$  and $C$ was sorted in non-decreasing order.


Your algorithm $quickSelect2Arrays(A,B,k)$ must be in-place,   i.e. only $O(1)$ additional space is allowed.
Briefly and informally  (one or two sentences) argue that the time complexity of your algorithm is the same as of $quickSelect1$,
i.e. $O(v)$ in the average case where $v$ is the total number of elements in $A$ and $B$,  i.e. $v=n+m$. \\
Hint: use the same pivot-value for partitioning both arrays.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 3
\subsection{[2+3+3=8]}
A clever student (let's call him Sajed) thinks he can avoid the worst-case
behaviour of QuickSort by employing the following pivot-selection procedure.
First, compute the mean $\bar{M}$ of the elements in the array. Then choose
as the pivot the element $x$ of the array, such that $|x - \bar{M}|$ is minimized,
i.e., pick the element closest to the average value in the array. Everything else
is the same as QuickSort. He calls the modified QuickSort algorithm SSort.
\begin{itemize}
	\part{a} Write down the recurrence for running time $T(n)$ of SSort. 
	In doing so, assume $x$ is placed at index $i$ of the partitioned array.
	The recurrence relation may be expressed in terms of $n$ and $i$.
	
	\part{b} Assume that the elements of the array form an arithmetic sequence
	(i.e., have the form $a$, $a + k$, $a + 2k$, $a + 3k$, \ldots, $a + (n - 1)k)$, 
	scrambled in some order. Show that, under this distribution of array elements, 
	SSort always runs in $\Theta(n \log n)$ time.
	\part{c} Unfortunately, Sajed's scheme is not as clever as it looks. 
	Give an example of an array where SSort achieves its worst case runtime of $\Theta(n^2)$
	and briefly explain why this example requires this time.\\

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 4
\subsection{[8 marks]}
Given an array $A[0\ldots n-1]$ of numbers, such that $A[i] \geq A[i-j]$
for all $0 \leq i \leq n-1$ and $\log n \leq j \leq i$, design an algorithm to 
sort $A$ in $O(n \log \log n)$ time. \\

\noindent {\emph{Hint:}} Partition $A$ into contiguous  blocks of size $(\log n)$; i.e.
the first $(\log n)$ elements are in the first block, the next $(\log n)$ elements are
in the second block, and so on.  Then, establish a connection between the elements
within two blocks, which are separated by another block. 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 5
\subsection{[2+2+4=8 marks]}

Consider the problem of finding the location of a given item $k$ in an array of $n$
distinct integers.  The following randomized algorithm selects a random index and checks
whether its entry is the desired value. If it is, it returns the index; otherwise, it
recursively calls itself. 

Recall that {\textit{random(n)}} returns an integer from the set of $\{ 0, 1, 2, \ldots, n-1\}$ uniformly and at random.


\quesbox{4cm}
{
{\texttt{find-index}}$(A,n,k)$
	\begin{algorithmic}[1]
	\State $i \gets random(n)$
	\If {$A[i] == k$} 
			\State \Return $i$
	\Else
			\State \Return {\texttt{find-index}}$(A,n,k)$.
	\EndIf
	\end{algorithmic}

}

In your answers below, be as precise as possible. You may use order notation when appropriate. 
Briefly justify your answers.
\begin{itemize}
	\part{a} What is the \textbf{best-case} running time of {\texttt{find-index}}? 
	\part{b} What is the \textbf{worst-case} running time of {\texttt{find-index}}? 
	\part{c} Let $T(n)$ be the expected running time of {\texttt{find-index}}. \\
	Write a recurrence relation for $T(n)$ and then solve it. \\
\end{itemize} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Problem 6
\subsection{[3+2+3=8 marks]}

In a game of loonie poker, all bids are placed using the Canadian loonie (one dollar coin).
At the end of the night there is one winner who walks away with all the loonies.
Unfortunately, some of the players were using counterfeit loonies.
Suppose there are $n$ loonies, some of which
are genuine and others that are counterfeit (there is at least one 
of each).
All genuine loonies weigh the same and all counterfeit loonies weigh the
same, but the counterfeit coins weigh less than the genuine coins.  
The goal is to separate the genuine coins from the counterfeit
coins by comparing the weight of pairs of
subsets of the coins using a balance scale.  The balance scale gives
one of the following outcomes:
\begin{itemize}
\item the two subsets of coins weigh the same
\item the subset on the left weighs more than the subset on the right
\item the subset on the right weighs more than the subset on the left
\end{itemize}
\begin{itemize}
\part{a} Give a formula for the precise (not big-Omega) lower bound for
the number of weighings required in the worst case to determine which
coins are genuine and which are counterfeit; i.e. your formula should produce 
an integer value that is the minimum number of weighings necessary in the worst case.
\part{b} Describe an algorithm called \texttt{FindGenuine}
to determine the genuine coins when $n = 4$. Use the names
L1, L2, L3, L4 for the four loonies, and the function
\[ BalanceResult\left( \{ left\_subset; right\_subset\} \right), \]
which returns either ``left weighs more'', ``right weighs more'', 
or ``both weigh the same''.
Your function should return the set of genuine loonies.

Give an exact worst-case analysis of the number of weighings required
by your algorithm.  For full marks, this should match exactly the
lower bound from Part (a) when $n = 4$.
\part{c} Describe an algorithm to determine the genuine
loonies, for any $n$. Use the names L1, L2, ... , L$n$ and
the $BalanceResult$ subroutine from Part (b). Analyze your algorithm by
counting the number of weighings.  Your answer, for this part, should be
$O(a(n))$ where $a(n)$ is the precise cost you found in part (a) of this problem.

\end{itemize}


%%% END OF QUESTIONS %%%
\end{document}
